线性方程组的直接解法.ppt

二、三对角方程组追赶法上一页下一页返回其中：若A满足Gauss消去法可行的条件，则可用LU分解法求解解方程组Ax=d分为两步，即求解Ly=d和Ux=y，计算公式如下：上一页下一页返回上述方法为求解三对角方程组的追赶法，也称Thomas算法.01追赶法公式简单，计算量和存储量都小，整个求解过程只需要5n-4次乘除运算。02三、平方根法——对称正定矩阵的分解法上一页下一页返回将对称正定阵A做LU分解记为第五章线性方程组的直接解法/*DirectMethordforSolvingLinearSystems*/上一页下一页返回第一节Gauss消去法第二节直接三角分解方法第三节方程组的性态与误差估计求解上一页下一页返回§1Gauss消去法上一页下一页返回一、高斯顺序消去法思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=是一种古老的求解线性方程组的方法,按自然顺序进行消元的方法.例1解方程组上一页下一页返回解：step1消元Step2对上三角形方程进行回代求解,得下面我们来一般性地讨论求解n阶线性方程组的高斯顺序消去法.消元上一页下一页返回将增广矩阵/*augmentedmatrix*/第i行?li1?第1行，得到与(1)式等价的方程组Step1：设，计算因子Step2：一般第k次消元(1≤k≤n-1)上一页下一页返回Step3：继续上述过程,且设aii（i-1）≠0(i=1,2,…,n-1),直到完成第n-1次消元,最后得到与A(0)x=b(0)等价的三角形方程组A(n-1)x=b(n-1).将(1)式化为(2)式的过程称为消元过程.回代定理若A的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/均不为0，则高斯消元无需换行即可进行到底，得到唯一解。注：事实上，只要A非奇异，即A?1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。上一页下一页返回高斯顺序消去法流程图上一页下一页返回FTk=k+1FT消元过程回代过程顺序消去法的缺点为当主元akk(k-1)=0时,消元过程不能继续进行.或者当akk(k-1)≠0时,虽然消元过程可以进行,但若akk(k-1)≈0时,时,会出现很小的数作除数的现象,使舍入误差增大,导致解的严重失真.二、主元素消去法上一页下一页返回例：解方程组/*精确解为*/用Gauss消去法计算：由上例可以看出,为提高算法的数值稳定性,应选取绝对值尽可能大的元素作主元.上一页下一页返回按列部分选主元的消去法也称列主元消去法。解：一些特殊情况,主元就在对角线上,不需选主元.元素满足如下条件的矩阵即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角占优矩阵.例：性质：严格对角占优矩阵必定非奇异.上一页下一页返回三、高斯-约当消去法（求矩阵逆）上一页下一页返回与Gauss消去法的主要区别：?每一步不计算lik，而是先将当前主元akk(k-1)变为1;?把akk(k-1)所在列的上、下元素全消为0;这种方法是不是比Gauss消去法更好?Gauss消去法过程中，消去对角线下方和上方的元素，称这种方法为高斯-约当消去法.这种方法不用回代过程了，看上去是要好些？?运算量/*AmountofComputation*/由于计算机中乘除/*multiplications/divisions*/运算的时间远远超过加减/*additions/subtractions*/运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。?Gauss消去法:Ste