第五章 线性方程组的直接解法ppt课件.ppt

《第五章 线性方程组的直接解法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章线性方程组的直接解法/*DirectMethordforSolvingLinearSystems*/上一页下一页返回第一节Gauss消去法第二节直接三角分解方法第三节方程组的性态与误差估计1求解上一页下一页返回2§1Gauss消去法一、高斯顺序消去法思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=是一种古老的求解线性方程组的方法,按自然顺序进行消元的方法.上一页下一页返回3例1解方程组解：step1消元上一页下一页返回4St

2、ep2对上三角形方程进行回代求解,得下面我们来一般性地讨论求解n阶线性方程组的高斯顺序消去法.上一页下一页返回5消元Step1：设，计算因子将增广矩阵/*augmentedmatrix*/第i行li1第1行，得到与(1)式等价的方程组上一页下一页返回6Step2：一般第k次消元(1≤k≤n-1)上一页下一页返回7上一页下一页返回8Step3：继续上述过程,且设aii（i-1）≠0(i=1,2,…,n-1),直到完成第n-1次消元,最后得到与A(0)x=b(0)等价的三角形方程组A(n-1)x=b(n-1).将(1)式

3、化为(2)式的过程称为消元过程.上一页下一页返回9回代定理若A的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/均不为0，则高斯消元无需换行即可进行到底，得到唯一解。注：事实上，只要A非奇异，即A1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。上一页下一页返回10高斯顺序消去法流程图FTk=k+1FT消元过程回代过程上一页下一页返回11顺序消去法的缺点为当主元akk(k-1)=0时,消元过程不能继续进行.或者当akk(k-1)≠0时,虽然消元

4、过程可以进行,但若akk(k-1)≈0时,时,会出现很小的数作除数的现象,使舍入误差增大,导致解的严重失真.上一页下一页返回12例：解方程组/*精确解为*/用Gauss消去法计算：二、主元素消去法上一页下一页返回13由上例可以看出,为提高算法的数值稳定性,应选取绝对值尽可能大的元素作主元.上一页下一页返回按列部分选主元的消去法也称列主元消去法。14解：上一页下一页返回15一些特殊情况,主元就在对角线上,不需选主元.元素满足如下条件的矩阵即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占

5、优矩阵,简称严格对角占优矩阵.例：性质：严格对角占优矩阵必定非奇异.上一页下一页返回16三、高斯-约当消去法（求矩阵逆）与Gauss消去法的主要区别：每一步不计算lik，而是先将当前主元akk(k-1)变为1;把akk(k-1)所在列的上、下元素全消为0;这种方法是不是比Gauss消去法更好?Gauss消去法过程中，消去对角线下方和上方的元素，称这种方法为高斯-约当消去法.上一页下一页返回这种方法不用回代过程了，看上去是要好些？17运算量/*AmountofComputation*/由于计算机中乘除/*multip

6、lications/divisions*/运算的时间远远超过加减/*additions/subtractions*/运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。Gauss消去法:Stepk：设，计算因子且计算共进行n1步(nk)次(nk)2次(nk)次(nk)(nk+2)次消元时乘除次数：1次(ni+1)次回代时乘除次数：Gauss消去法的总乘除次数为，运算量为级。上一页下一页返回18Gauss-Jordan消去法:运算量约为。故通常只用于求

7、逆矩阵，而不用于解方程组。求逆矩阵即。上一页下一页返回19§2直接三角分解法一、LU分解法/*LUFactorization.*/就n=3的情况分析顺序消去法的消元过程.上一页下一页返回20可见,消元过程相当于下述矩阵乘法运算：由分块乘法可得：直接计算可得由(*)式可得上一页下一页返回21Step1:记M(1)=，则Stepn1:其中M(k)=以上分析推广到n阶线性方程组可得上一页下一页返回22记为L单位下三角阵/*unitarylower-triangularmatrix*/记U=A的LU分解/*LUfactoriz

8、ation*/也称A的Doolittle分解上一页下一页返回23道立特分解法/*DoolittleFactorization*/：——LU分解的紧凑格式/*compactform*/根据矩阵乘法法则,先比较等式两边第1行和第1列元素有：上一页下一页返回24设已定出U的第1行到第k-1行的元素L的第1列到第k-1列的