科学计算与数学建模第5章 小行星轨道方程计算问题-线性方程组求解的直接法-5.3 矩阵的三角分解与Gauss消去法-2017-01.pptx

1、5.3 矩阵的三角分解与Gauss消去法,5.3.1矩阵的三角分解,a11 x1 ,a12 x2 a22 x2,a21 x1 ,an1 x1,a1n xnb1 a2 n xnb2 ,an 2 x2 ann xnbn,Gauss消去法的消元过程是对方程组的增广矩阵进行 除行交换外行的初等变换，将其化成上三角矩阵，回代求 解对应的上三角方程。为了更明晰原方程组的系数矩阵与 消元后上三角方程组的系数矩阵的关系，现在用矩阵理论 进一步来分析Gauss消去法。 设含有n个未知数的线性方程组为,T,T,12n,12n。,nn,其中A aij , X x , x ,x,b b ,b ,b,即,AX b,设G

2、auss消元过程中约化主元素,。,(k ),kk,a,0(k 1, 2n 1),由于对矩阵A实行的初等变换相当于用初等矩阵左乘A，根据 Gauss消去法第1步： A(1) X b(1) A(2) X b(2),则有,其中,2 1,1,1,L,0 ,m n 1,00 m10 01 ,1,（L 为初等三角矩阵）,(1)(2),(1),(2),1,L A,A,L1bb,Gauss消去法第 k 步消元过程：A(k) X b(k),A(k1) X b(k1),(k),k,k,则有L A,L b,(k1) ,(k)(k1),A,b,k1, 2,n 1,1,1,k,L 1,1 , , , ,1 , ,1 m

3、k 1, k mn , k,第 k 列,1,1, L,k , ,1,1 mk 1,k mn,k,第k列,其中 1 , 于是得到,1,n,Ln1Ln2 L2L1AA,U,1,(n),b,Ln1Ln2 L2L1b,从而得,1,2,U,11L1,n1,A LL,LU,1 m21,L m31 , 1,1 m32 mn1mn 2,1 ,L 为由乘数构成的下三角阵，U 为上三角矩阵。可见，用矩,阵理论来分析Gauss消去法得到：在,( k ) kk,a,0, (k 1, 2, n 1),条件下，Gauss消去法实质上就是将A分解成一个单位下三 角矩阵与一个上三角矩阵的乘积，即 A LU。,其中,11,12

4、,1n,a (1),a ( 2 ),a,a (1),a (1) ,a ( 2 ) ,U, , , 222 n ( n ) nn,顺序主子式: A1 （a11）,Ak,a11 ,ak1, ,，(k 1, 2, n) akk ,易证，Gauss消元法过程中，要求,( k ) kk,a,0, (k 1, 2, n 1)与,0,(k 1, 2, n 1) 等价。 a1k ,方程组的系数矩阵A 的顺序主子式 Ak,定理5.2 （矩阵的三角分解）,设，如果,nn,AR,A 可分解为一个单位下三角矩阵与一个上三角矩阵的乘积， 即 A LU ，且分解是唯一的。,i,A 的顺序主子式 det( A ) 0(i

5、1,n 1)， 则,为单位下三角阵，为上三角阵，由假设知,。此式右端为上三角阵，左边为单位下三角阵，,LU,1,U, U,1,U存在（因为,1,1,有 L1 L,1 1,UU,证明仅就 det( Ak ) 0(k 1,n -1) 证明唯一性，Gauss消元过程已 经证明存在性。假若 A L1U 1 LU 且对 A 非奇异时考虑，L1 , L,det A 0, L1 可逆，A L1U1，故 U 1 可逆），从而由 A L1U1,分解,1,因此左右两端应为单位矩阵。故 L1 L,U1 U，即分解是唯一的。 矩阵分解为一个单位下三角矩阵与一个上三角矩阵乘积，即三角 1, ln1ln 2, ,A LU

6、 l21,u11u12 u22 ,1,unn , ,u1n u2 n 称为Doolittle分解。,在以上定理条件下，同样有下面的三角分解：A L U， 其中L为下三角矩阵，U为单位上三角矩阵，称之为Crout分解。,1, 2, ,1,222 A 32 13,9,1,22 11 LU 10,4321 2,2,2 x1 2 x22 x31,2 x24 x3,x3 x29 x3,1 / 2 5 / 2,1,例解线性方程组3 x1,解由Gauss消元过程可得系数矩阵可分解为,如果能先求出从线性方程组系数矩阵的三角分解A LU ， 则线性方程组的求解问题就变得简单了。,(1) LY b Y,(2) U

7、X Y X,于是，令 UX Y，则,事实上，对一般的线性方程组AX b ，若能求出系数 矩阵的三角分解： A LU，则 AX b LUX b,AX b UX Y LY b 因此，方程组AX b的解通过下面两个三角方程组求出。,而求解这两个三角形方程组是很容易的事。,3,333,3,n,n 3,(2)AS n (n 1)(2 n 5) / 6 n,（1） MD n 3n 2,5.3.2 Gauss消去法的计算量,AX b,定理 5.3 设A为n阶非奇异矩阵，则用Gauss消去法解 所需要的乘除法次数及加减法的次数分别为：,如果用Cramer法则解 AX b，需要计算n+1个n阶行列式，总共需要 n!(n1)(n1) 次乘法。如 n 10 时，Gauss消去法需要430乘除法，而 Cramer法则却需要39916800次乘法。如果计算是在每秒作105 次 乘除法的计算机上进行，用Gauss消去法解20阶方程组约需0.03， 而用Cramer法则大约需1.3 1011 小时才能完成（大约相当于107 年） 可见， Cramer法则完全不适于在计算机上求解高维方程组。,？,Gauss消元过程中影响误差传播的主要因素是什么？,5.3 矩阵的三角分解与Gauss消去法,弹幕问题： 1. 只要方程组有唯一解其