数值分析课件：5.2 Gauss消去法.ppt

1、第五章方程组的直接解法5.2 Gauss消去法消去法5.2.4 Gauss-Jordan消元法消元法5.2.3 主元素消去法主元素消去法5.2.2 矩阵的三角分解矩阵的三角分解5.2.1 Gauss消去法的计算过程消去法的计算过程第五章方程组的直接解法第第5章章 线性方程组的直接解法线性方程组的直接解法教学目的教学目的 1. 掌握解线性方程组的高斯消去法、高斯选主元素消去法；掌握解线性方程组的高斯消去法、高斯选主元素消去法；2. 掌握用直接三角分解法解线性方程组的方法；掌握用直接三角分解法解线性方程组的方法；3. 了解解对称正定矩阵线性方程组的平方根法与解三对角线方程了解解对称正定矩阵线性方程

2、组的平方根法与解三对角线方程组的追赶法；组的追赶法；5. 掌握向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分掌握向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析。析。教学重点及难点教学重点及难点 重点是重点是1. 解线性方程组的高斯消去法、高斯选主元素消去法；解线性方程组的高斯消去法、高斯选主元素消去法；2. 直接三角分解法解线性方程组的方法；直接三角分解法解线性方程组的方法；3. 向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析；向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析；难点是难点是方程组的扰动分析。方程组的扰动分析。第五章方程组的直接解法 在工程技术、自然科学和社会

3、科学中，经常遇到的许在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重

4、要的。程组的求解对于实际问题是极其重要的。第第5章章 线性方程组的直接解法线性方程组的直接解法(Direct Method for Solving Linear Systems)第五章方程组的直接解法在工程实际问题中产生的线性方程组，其系数矩阵大在工程实际问题中产生的线性方程组，其系数矩阵大约有两种：约有两种：一种是低阶稠密矩阵一种是低阶稠密矩阵(阶数阶数n 150，矩阵的全部元素都，矩阵的全部元素都可能贮在计算机中可能贮在计算机中)；另一种是大型高阶稀疏矩阵另一种是大型高阶稀疏矩阵(矩阵元素中零元素较多，矩阵元素中零元素较多，阶数较高，如阶数较高，如n=103或或104等，这类矩阵一般要压缩

5、存储或仅等，这类矩阵一般要压缩存储或仅存储系数矩阵中的非零元素存储系数矩阵中的非零元素) 第五章方程组的直接解法关于线性方程组的数值解法有两大类：关于线性方程组的数值解法有两大类：近十几年来,直接法在求解具有较大型系数矩阵方程组方面取得了较大进展.直接法直接法：就是经过有限步算术运算，可求得方程组精就是经过有限步算术运算，可求得方程组精确解的方法确解的方法(若计算过程中没有舍入误差若计算过程中没有舍入误差)，如克莱姆，如克莱姆法则就是一种直接法，但实际上由于舍入误差的存在，法则就是一种直接法，但实际上由于舍入误差的存在，这类方法也只能求得线性方程组的近似解。这类方法也只能求得线性方程组的近似解

6、。 直接法中具有代表性的算法是直接法中具有代表性的算法是高斯高斯(Gauss)消去消去法法。其特点是准确，可靠，理论上得到的解是精确的其特点是准确，可靠，理论上得到的解是精确的. 这类方法是解这类方法是解低阶稠密矩阵方程组低阶稠密矩阵方程组的有效方法的有效方法.第五章方程组的直接解法迭代法是解大型稀疏矩阵方程组的的重要方法迭代法是解大型稀疏矩阵方程组的的重要方法.迭代法迭代法： ( 第六章介绍）就是用某种极限过第六章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。程去逐步逼近线性方程组的精确解的方法。也就是也就是从解的某个近似值出发，通过构造一从解的某个近似值出发，通过构造一个无穷

7、序列去逼近精确解的方法。个无穷序列去逼近精确解的方法。(一般有限一般有限步内得不到精确解步内得不到精确解). 特点是速度快，但有误差特点是速度快，但有误差.第五章方程组的直接解法本章讲解本章讲解直接法直接法.对于中小型方程组，常用对于中小型方程组，常用直接解法直接解法。从本质上来说，。从本质上来说，直接方法的原理是找一个可逆矩阵直接方法的原理是找一个可逆矩阵M，使得，使得MA是一个上是一个上三角阵，这一过程一般称为三角阵，这一过程一般称为“消元消元”过程，消元之后再过程，消元之后再进行进行“回代回代”，即求解，即求解MAx=Mb。本章讨论。本章讨论Gauss消去消去法及其变形，以及一些情况下的

8、特殊方法，最后进行误法及其变形，以及一些情况下的特殊方法，最后进行误差分析。差分析。第五章方程组的直接解法 设线性方程组为或写成矩阵形式或简单地记为: 11112211211222221122 (1)nnnnnnnnnna xa xa xba xa xa xba xa xa xb1112111212222212 (2)nnnnnnnnaaaxbaaaxbaaaxb TT1212 ,(), (,) , ( ,) .ijn nnnAxbAaxx xxbb bb第五章方程组的直接解法 Gauss消去法是一个古老的求解线性方程组的方法。由它改进的选主元法是目前计算机上常用的有效的求解低阶稠密矩阵线性方

9、程组的方法。5.2 Gauss消去法消去法1231231232221(1)1324(2)2539(3)2Gaussxxxxxxxxx例4.1：用消去法解方程组第五章方程组的直接解法123232331121) ()(3)2222211(4)282(5)xxxxxxx 解：第1步，（ ） （）加到（ ），（加到，得等价方程组：12323324) 2522211100(6)xxxxxx 第 步，(加到（ ）得等价的方程组：第五章方程组的直接解法3213610,1,.2xxx 第 步，回代法求解（ ）即可求得该方程组的解为：程即为：用矩阵法描述的约化过122133(1)3()21()222212221

10、0111,3241/202821395/2rrrrrrA b 消去法。回代的这种求解过程称为具有Gaussrrr0100011101222)2(2332第五章方程组的直接解法GaussA此例可见消去法的基本思想是：用矩阵得初等行变换将系数矩阵 化为具有简单形式的矩阵（如上三角阵，单位矩阵等），而三角形方程组是很容易回代求解的。一般的，设有n个未知数的线性方程组为：11 11221121 1222221 122(5.2.1)nnnnnnnnnna xa xa xba xa xa xba xa xa xb1212)( ,)( ,)5.2.1设（，则（）化为：TTij n nnnAaXx xxbb

11、bbAXb1 Gauss消去法的步骤消去法的步骤第五章方程组的直接解法(1)(1)(1)(1)(1)(1)12()(,) ,det0 .Tijn nnAAabbbbbA为方便,设,消元过程就是要按确定的计算过程对方程组进行初等行变换消元过程就是要按确定的计算过程对方程组进行初等行变换,将方程组化为上三角方程组将方程组化为上三角方程组.nnnnnnnbaaabaaabaaa21222221111211(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333( )( )000000nnnnnnnnaaaabaaabaabab第五章方程组的直接解法

12、步骤如下：步骤如下：11, 2,iilin第 行-第 行(1)(1)(1)(1)111211(1)(1)(1)(1)212222(1)(1)(1)(1)12nnnnnnnaaabaaabaaab(1)(1)(1)(1)111211(2)(2)(2)2222(2)(2)(2)200nnnnnnaaabaabaab运算量：运算量： (n-1)*(1+n)第一步消元第一步消元：设设 ，计算因子，计算因子0)1(11a1(1)11(1)11()iiialma或其中其中(2)(1)(1)1 1(2)(1)(1)1 1, ,2,3,ijijijiiiaal ai jnbbl b第五章方程组的直接解法(1)

13、(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333(3)(3)(3)300000nnnnnnnaaaabaaabaabaab运算量：运算量： (n-2)*(1+n-1)=(n-2)n第二步第二步：设设 ，计算因子，计算因子22,3,iilin第 行-第 行(1)(1)(1)(1)111211(2)(2)(2)2222(2)(2)(2)200nnnnnnaaabaabaab(2)220a(2)222(2)22()iiialma或其中其中(3)(2)(2)2 2(3)(2)(2)2 2, ,3,ijijijiiiaal ai jnbbl b第五章

14、方程组的直接解法0)( kkka第第k步：步：设设 ，计算因子，计算因子( )( )()/(1,., )ikkkikikkklmaaikn或将增广矩阵将增广矩阵的的第第 i 行行- - lik 第第k k行行，得到：，得到：(1)()()(1)()()( ,1, .,)kkkijijikkjkkkiiikkaal abbl bijkn其中其中(1)(1)(1)(1)(1)111111,11( )( )( )( ),1(1)(1)(1)11,11,1(1)(1)( ),100000kknkkkkkkkk kknkkkkkkkknkkkkn knnnnbxaaaaxaaabxaabaaxb 运算量

15、：运算量： (nk)*(1nk1) =(nk)(nk2)(5.2.2)第五章方程组的直接解法(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333( )( )000000nnnnnnnnaaaabaaabaababn1步以后，我们可以得到变换后的矩阵为：步以后，我们可以得到变换后的矩阵为：这就完成了消元过程。这就完成了消元过程。(5.2.3)(4.1.1)得到与等价的三角形方程组：(1)(1)(1)(1)1111211(2)(2)(2)22222( )( )(5.1.4)nnnnnnnnxaaabxaabxab第五章方程组的直接解法)()(

16、/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii回代过程：回代过程： 以上由消去过程和回代过程合起来求解（以上由消去过程和回代过程合起来求解（5.2.1）的过程就称为的过程就称为Gauss消去法消去法，或称为，或称为顺序顺序Gauss消去法消去法。(5.2.5)( )kkka元素称为约化的主元素.总结上述讨论即有以下定理：总结上述讨论即有以下定理：第五章方程组的直接解法( ),0(1,2)-(4.1.4)n nkkkGaussAXb ARaknGauss定理：消去法 设。若约化的主元素，则可通过消去法（不进行两行的初等变换 两行交换位置）将方程组化

17、为等价的三角形方程组。且消元和求解的计算公式为：回代计算02( )( )( )( )1( )(),(1,2,1)nnnnnniiiijjj iiiiibxaba xxinna 011,21)kn消元计算，(，( )( )(1)( )( )(1)( )( )(1,)( ,1,)(1,)kikkikkkkkkijijikkjkkkiiik kaliknaaal ai jknbbl bikn第五章方程组的直接解法算法算法. ( )( )0,1,2, .kkkkikikaknAA la若，覆盖覆盖，消去：对于nk, 2 , 1 . 1( )(1) 0,.kkka若则停止计算(2) 1, ( ) / (

18、 ) 1, , ikikkkijijikkjiiikkiknilaaiijknaalabbl b对于对于, 1 , . 2ni 回代：对于, ) 1 (iibx , , 1 )2(jijiixaxxnij对于./ ) 3(iiiiaxx 第五章方程组的直接解法例例5.1 用用Gauss消去法解方程组消去法解方程组1231231232221132425392xxxxxxxxx222101110282解解 第一步消元第一步消元,令令 得增广矩阵得增广矩阵21313 / 2,1/ 2,ll第二步消元，令第二步消元，令 得增广矩阵得增广矩阵3 22 /(1)2,l 22210111 .00100利用回

19、代公式（利用回代公式（5.2.4）依次得到）依次得到32110,1,.2xxx 在这个例子中我在这个例子中我们写出的是分数们写出的是分数运算的结果。如运算的结果。如果在计算机上进果在计算机上进行计算，系数矩行计算，系数矩阵和中间结果都阵和中间结果都用经过舍入的机用经过舍入的机器数表示，中间器数表示，中间结果和方程组的结果和方程组的解都会有误差。解都会有误差。第五章方程组的直接解法矩阵A在什么条件下才能保证)(kkka0(k=1，2，n)?下面的定理给出了这个条件。引理5.1 约化的主元素 )(iiiaO(i=1，2，n)的充要 条件是矩阵A的顺序主子式Di0(i=1,2,n)。即即:11111

20、110,0kiiiiaaDaDaa约化的主元素约化的主元素第五章方程组的直接解法证证 先证必要性先证必要性设设 ，则可进行，则可进行k-1步消元。显步消元。显然然 ，对，对 ，由于每步进行的初等变换不改变，由于每步进行的初等变换不改变顺序主子式的值，所以第顺序主子式的值，所以第i-1步消元后有步消元后有).,2 , 1( ,0)(kiaiii 01)1(11 Da2i. 0)()2(22)1(11)()2(2)2(22)1(1)1(12)1(11 iiiiiiiiiaaaaaaaaaD,0)(22)(12)(11)( mmmmAAAA用归纳法证充分性用归纳法证充分性。k=1时，命题显然成立。设

21、命题对时，命题显然成立。设命题对m-1成立。成立。已知已知 由归纳假设有由归纳假设有 Gauss消去法可进行第消去法可进行第m-1步，矩阵步，矩阵A变换为变换为, 2 , 1, 0detmiADii . 1, 2 , 1, 0)( miaiii其中其中 是对角元素为是对角元素为 的上三角阵。的上三角阵。因因 是通过消元过程由是通过消元过程由A逐步经初等变换得到的，逐步经初等变换得到的，A的的m 阶顺序主阶顺序主子式等于子式等于 的的m 阶顺序主子式，即阶顺序主子式，即由由 可推出可推出 ，定理得证。，定理得证。)(11mA)()1(1, 1)2(22)1(11,mmmmmmaaaa )(mA)

22、(11mA)()1(1,1)2(22)1(11,mmmmmmaaaa 0mD0)( mmma第五章方程组的直接解法定理5.2:如果n阶矩阵A的所有顺序主子式均不为零，即Di0(i=1,2,n)，则可通过高斯消去法(不进行交换两行的初等变换)求解求解方程组方程组(5.2.1)。特别地，若特别地，若A为对称正定矩阵，则由对称正定为对称正定矩阵，则由对称正定矩阵的性质可知，对原方程组不必作任何处理，矩阵的性质可知，对原方程组不必作任何处理，可直接用可直接用Gauss消去法求解方程组。消去法求解方程组。推论推论: 若若，)1, 2 , 1(0 nkDk，且且则则)1, 2 , 1(0)( nkakkk

23、 ), 2(/1)(1)1(11nkDDaDakkkkk第五章方程组的直接解法 高斯消元法运算量： 消元过程： 乘： 除： 回代过程： 运算量：221(1)(1)(2)3 22 11(1)(1)(1),31(1)(2)2 1(1);(for right item)2nnkknnnnk kk kn nnnn n 1(1)(2)2 1(1)2nnn n 112(1)(multiply)(divide)(1).2nnn n322311135(1)(1)(1)322326().nn nn nn nnnO n第五章方程组的直接解法 高斯消元法的局限性：1.1.在高斯消元过程中，我们假定了对角元素在高斯消

24、元过程中，我们假定了对角元素 由于每次消元时是按未知量的自然顺序进行的，而顺序由于每次消元时是按未知量的自然顺序进行的，而顺序消元不改变消元不改变 A 的主子式的值，因此高斯消元法可行的充的主子式的值，因此高斯消元法可行的充分必要条件为分必要条件为 A 的各阶主子式不为零。实际上只要的各阶主子式不为零。实际上只要detdetA A00，方程组就有解。，方程组就有解。2. 2. 即使高斯消元法可行，如果即使高斯消元法可行，如果 很小，运算中用它作分很小，运算中用它作分母会导致其它元素数量计的严重增长和舍入误差的扩散。母会导致其它元素数量计的严重增长和舍入误差的扩散。(1)0,kkka(1)kkk

25、a第五章方程组的直接解法例例 解方程组解方程组 精确解为：精确解为：x1=1/3，x2=2/3。计算取。计算取5 5位有效数字。位有效数字。解解1 顺序消元：顺序消元：解解2 交换方程的顺序：交换方程的顺序： 经高斯消元：经高斯消元：12120.00033.00002.00011.00001.00001.0000 xxxx122210.00033.00002.0001 0.6667 9999.06666.00 xxxxx 12121.00001.00001.00000.00033.00002.0001xxxx122211.00001.00001.00000.6667 2.99971.99980

26、.3333xxxxx第五章方程组的直接解法 这个例子告诉我们，在采用高斯消去法解方程组时这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能导致计算失败，故在消去法中应避免采用，小主元可能导致计算失败，故在消去法中应避免采用绝对值很小的主元素。绝对值很小的主元素。 方法方法1计算失败的原因，是用了一个绝对值很小的数计算失败的原因，是用了一个绝对值很小的数作除数，乘数很大，引起约化中间结果数量误差很严重作除数，乘数很大，引起约化中间结果数量误差很严重增长，再舍入就使得计算结果不可靠了。增长，再舍入就使得计算结果不可靠了。1ikm 对一般矩阵方程组，需要引进主元的技巧，即在高斯消对一般矩阵方程

27、组，需要引进主元的技巧，即在高斯消去法的每一步应该选取系数矩阵或消元后的低阶矩阵中的绝对去法的每一步应该选取系数矩阵或消元后的低阶矩阵中的绝对值最大的元素作为主元素，保持乘数值最大的元素作为主元素，保持乘数 ，以便减少计算，以便减少计算过程中的舍入误差对计算解的影响。过程中的舍入误差对计算解的影响。第五章方程组的直接解法一、列主元消去法一、列主元消去法 设有线性方程组：设有线性方程组：AX=b1112111212222212, , .nnnnnnnnaaaxbaaaxbAXbaaaxb 第一步第一步: :先在先在A的的第一列第一列选取选取绝对值最大绝对值最大的元素作主元素的元素作主元素, ,.

28、 0max111 ,1iniiaa 然后然后交换交换第第1行和第行和第i1行行(当当i11时时),再进行第再进行第1次消元次消元.第五章方程组的直接解法 第第k k步选主元素步选主元素, ,. 0max,iknikkiaak 然后交换第然后交换第k行和第行和第ik行行( (当当ikk时时),),再进行第再进行第k次消元次消元. . 第第n-1n-1步步. 000212122211211nnnnnnbbbxxxaaaaaa第五章方程组的直接解法 回代求解回代求解 nnnabnx ) 1 , 1( ,1nianijxabxiijijii算法算法(列主元消去法列主元消去法). .det, , ,存消

29、元结果bxamAikik ( (见见P P李庆扬李庆扬177)177).1, 2 , 1( 1nkmik可见第五章方程组的直接解法完成了完成了n-1步主元，换行与消元运算后，得步主元，换行与消元运算后，得到到 ，这是与原方程组等价的方程组，这是与原方程组等价的方程组,是一个是一个上三角阵上三角阵,再代回求解再代回求解.这就是列主元素消去法的计算过程这就是列主元素消去法的计算过程.)()(nnbxA )(nA除了列主元素消去法外除了列主元素消去法外,还有一种还有一种完全主元素消去法完全主元素消去法.在其在其过程的第过程的第k 步步 ，不是按列来选主元，而是在，不是按列来选主元，而是在右下角的右下

30、角的n-k+1阶子阵中选主元阶子阵中选主元 ,即即然后将然后将 的第的第 行与第行与第k行交换，将第行交换，将第 列与第列与第k列交换列交换,同时将自变量同时将自变量 与与 的位置交换并记录自变量的位置交换并记录自变量的排列次序的排列次序.直到消去法完成后直到消去法完成后,再按记录恢复自变量为再按记录恢复自变量为自然次序自然次序.完全主元法比列主元法运算量大得多完全主元法比列主元法运算量大得多,由于列主由于列主元法的舍入误差一般已较小元法的舍入误差一般已较小,所以在实际计算中多用列主所以在实际计算中多用列主元法元法.) 1( k.max)(,)(,kijnjikkjiaakk )(,kjikk

31、a),()()(kkbAkikxjkxkj)(kA第五章方程组的直接解法例例5.3 用列主元素消去法解方程组用列主元素消去法解方程组Ax=b,计算过程中五位有计算过程中五位有效数字进行运算效数字进行运算,其中其中.4178. 745625. 5996. 33816. 1078125. 014 . 022002. 0),(bA解解 记记 . 第一步选列主元为第一步选列主元为 ，交换，交换第第1行与第行与第3行，再消元计算得行，再消元计算得),(),()1()1(bAbA 996. 3)1(31 a.40371. 00020. 20028. 2047471. 00010. 161077. 0041

32、78. 745625. 5996. 3),()2()2(bA第二步选列主元为第二步选列主元为 ,交换第交换第2行与第行与第3行，再消元计行，再消元计算得算得0028. 2)2(32 a第五章方程组的直接解法.35159. 039047. 00040371. 00020. 20028. 204178. 745625. 5996. 3),()3()3( bA消去过程至此结束。回代计算依次得到解消去过程至此结束。回代计算依次得到解这个例题的精确解是这个例题的精确解是 而用不选住主元的顺序而用不选住主元的顺序Gauss消去法，则解得消去法，则解得9273. 1,69850. 0,90043. 0123

33、xxx,)900423. 0 ,698496. 0,92730. 1 (Tx,)88888. 0 ,68695. 0,9300. 1 (Tx这个结果误差较大，这是因为消去法的第这个结果误差较大，这是因为消去法的第1步中，步中， 按绝对值比按绝对值比其他元素小很多所引起的。从此例看到去其他元素小很多所引起的。从此例看到去列主元素消法列主元素消法是有效是有效的方法。的方法。)1(11a第五章方程组的直接解法解：精确解为（舍入值）：解：精确解为（舍入值）：)3279. 0 ,2841. 0 ,2245. 0(*x000. 11 . 121. 1331. 18338. 06867. 09 . 081.

34、 0729. 0321321321xxxxxxxxx例例5.4：用列主元消去法去解方程组：用列主元消去法去解方程组000. 1100. 1210. 1331. 18338. 0000. 1000. 1000. 16867. 09000. 08100. 07290. 0,bA132131(,1 1.3310.7513,0.7209 1.3310.5477)rr mm第五章方程组的直接解法32321.3311.2101.1001.00000.090900.17360.0825000.14730.29750.1390,0.61711.3311.2101.1001.00000.14730.29750.

35、1390000.010000.0032800.2246,0.2812,0.3280Trr mx回代计算得到计算解： 本例是具有舍入的本例是具有舍入的4位浮点数进行运算，所得的计算解还是比较准确的。位浮点数进行运算，所得的计算解还是比较准确的。第五章方程组的直接解法列主元素消去法步骤：设Ax=b。对于具有行交换的列主元素消去法，消元结果冲掉A，乘数mij冲掉aij，计算解X冲掉常数项b,行列式存在det. 1, 1det, k=1 （对k=1n-1 做27步。）|max|, 2,kkinikkiaa按列选主元素 3， 若aik,k=0, 则 0det. 计算终止。,4,.5(,1, ),detd

36、etkkkkjijkiikaajk knbb，若转，否则，执行： 5， 计算乘数mik, mik= aik/ akkaik.(i=k+1n) (| mik|1)第五章方程组的直接解法6, 消元计算： aij - mik aij aij (i,j=k+1,n) bi - mik bk bi (i=k+1,n)7,detdet12kkakk 返)2, 1()( , 81innibababbabiiinijiijinnnn回代求解：.detdet, 9nna优点：优点：数值稳定。数值稳定。修正方法：修正方法：列主元高斯列主元高斯- -约当（约当（Gauss-Jordam）消去法。）消去法。缺点：缺点

37、：既消元；又回代。既消元；又回代。列主元素高斯消去法第五章方程组的直接解法5.2.4* Gauss-Jordan消元法（可不讲，自学）消元法（可不讲，自学） 高斯消去法有消元和回代两个过程，消去的是对角线下方高斯消去法有消元和回代两个过程，消去的是对角线下方的元素。当对消元过程稍加改变便可使方程组的元素。当对消元过程稍加改变便可使方程组 化为对角化为对角阵阵 bAx )()(2)(121111nnnnnbbbxxx（5.2.95.2.9） 这时求解就不需要回代了这时求解就不需要回代了, ,这种将主元素化为这种将主元素化为1,1,并用主元将其所并用主元将其所在列的冗余元素全都消为在列的冗余元素全

38、都消为0,0,即消去对角线上方与下方的元素即消去对角线上方与下方的元素, ,这这种方法称为种方法称为高斯高斯- -约当约当消去法消去法, ,这时等号右端即为方程组的解这时等号右端即为方程组的解第五章方程组的直接解法nnnknknkkknkkknkkkkkbaabaaaabaabAbxAbAxkJG, 1, 11, 1, 1)()()()(1111其中：方程组化为等价）步，于是消去法已完成（设用第五章方程组的直接解法 在第k步计算时，考虑对上述矩阵的第k行上、下都进行消元计算（k=1,2n）,1,|max |kkikikk i niaa 按列选主元素，即定 使2，换行（当ikk）。交换A,b第k

39、行与第ik行元素。3，计算乘数 mik = -aik/akk (i=1n,i k), mkk =1/ akk (mik可存放在aik的单元中) （| mik |1） ）且（）且（消元计算kinibbmbkinkjniaamaikikiijkjikij,11,1, 45,1kjkkkjkkkka majk knb mb计算主元素（ ）第五章方程组的直接解法上述过程全部执行完后有：nkkbbbbAbA111,21)1()1( 这表明用GJ方法将A约化为单位矩阵，计算解就在常数项位置得到，因此用不着回代求解。用GJ方法接方程组的计算量大约需要 次乘除法，要比Gauss消去法大些。23n第五章方程组的

40、直接解法例例5.4 5.4 用高斯用高斯- -约当约当(Jordan)(Jordan)消去法求方程组的解消去法求方程组的解 120221321321321xxxxxxxxx解解 方程组相应的增广矩阵方程组相应的增广矩阵 111202211111111102211112列选主元列选主元5 . 15 . 05 . 105 . 05 . 15 . 205 . 05 . 05 . 012 . 14 . 0002 . 06 . 0104 . 08 . 001第五章方程组的直接解法3100201020013, 2, 2321xxx故得故得 2 . 14 . 0002 . 06 . 0104 . 08 .

41、001说明：说明：次次乘乘除除法法。计计算算量量较较大大，大大约约是是)2/(3nO因此，可以因此，可以用来求逆矩阵用来求逆矩阵。 不用回代，将不用回代，将A化为单位矩阵，则解为常数项列。化为单位矩阵，则解为常数项列。解解即即消消去去法法bAxbxAJG1 优点：优点：缺点：缺点：约约当当消消去去法法。时时，一一般般不不用用高高斯斯在在解解方方程程组组 bxA因为计算量太大，但是在解多个方程组而它们的系数矩阵相同时，因为计算量太大，但是在解多个方程组而它们的系数矩阵相同时，则则有有了了矩矩阵阵的的逆逆矩矩阵阵用用此此方方法法，即即是是求求系系数数bAxAA111, 高斯高斯-约当约当(Jord

42、an)消去法消去法第五章方程组的直接解法定理定理5.5 设设A为为为为n阶非奇异矩阵，方程组阶非奇异矩阵，方程组Ax=I的增广矩阵为的增广矩阵为C=（A，I）。如果对）。如果对C用用Gauss-Jordan消去法化为（消去法化为（I，T），则），则 .1 AT证证 设设 ,则则 这里，这里， 为单位矩阵为单位矩阵I的第的第j列，用列，用Gauss-Jordan消去法解方程组消去法解方程组 ,其解在其解在C中中I的第的第j列，即为列，即为T的第的第j列，即列，即 .因此因此 .定理得证定理得证.)(211nXA njeAIAXjj, 2 , 1, jejjeAx 121),( AXTn jjTe

43、 例例5. 用用Gauss-Jordan消去法求矩阵消去法求矩阵的逆矩阵。的逆矩阵。 653542321A第五章方程组的直接解法解解 用列主元素消去法有用列主元素消去法有,100653010542001321),()1( IACC,310113103210132031000351)2( C,021121001230231022502101)3( C).,(0121001330102310011)4( AIC第五章方程组的直接解法在实际计算中，为了节省内存单元，单位矩阵不必存放。在上例中，在实际计算中，为了节省内存单元，单位矩阵不必存放。在上例中，可将可将 的最后一列放在的最后一列放在A第第1列

44、，将列，将 的第的第5列存放在列存放在A的第的第2列，列，将将 的第的第4列存在列存在A的第的第3列。一般地，第列。一般地，第k步消元时，可将步消元时，可将A的第的第k列列)2(C)4(C)3(CTnkkkkkaaaa),(1Tkknkkkkkkkkkkkkkkkaaaaaaaaal,1, 1, 11用向量用向量取代。最后再调整一下列就可以在取代。最后再调整一下列就可以在A的位置得到的位置得到 。实际上，在。实际上，在A的位置最后得到的矩阵的位置最后得到的矩阵 是的逆矩阵是的逆矩阵 ，其中，其中P为行变换为行变换形成的排列阵，于是形成的排列阵，于是APA 1A.11PAA 1A第五章方程组的直

45、接解法5 .基于初等变换的矩阵的三角分解基于初等变换的矩阵的三角分解( )(1)(1)(2)(2)(1)(2)(1)(2)110(1,21),1kkkGaussaknAAGaussA XbAXbL AALbb我们用用矩阵理论进一步来分析消去法，设约化主元素，由于对 实行行的初等变换相当于用初等矩阵左乘于是，消去法第 步：则有：,其中：211110010001nlLl1( )( )(1)(1)( )(1)( )(1)(,(1)(1,2,1)kkkkkkkkkkLGausskAXbAXbL AAL bbkn为初等三角矩阵）消去法第 步消元过程：则有：下面建立高斯消去法与矩阵的因式分解的关系下面建立

46、高斯消去法与矩阵的因式分解的关系. .第五章方程组的直接解法1,11111kkkn kkLll第 列其中：11,11111kkkn kkLll第 列第五章方程组的直接解法1(1)( )(1)( )12211221111211,(2)(3)nnnnnnnLLL L AAULLL LbbL LLULU利用递推公式（ ）则有：由(2)得: A=( ),(3)0,(1,2).ijkkkLlijUGaussaknGaussAALU为由乘数 ()构成的单位下三角矩阵，为上三角矩阵表明，用矩阵理论来分析消去法，得到一个重要结果，即在条件下消去法实质上是将 分解成两个三角矩阵的积(1)(1)(1)111212

47、1(2)(2)2223132( )12111,1nnnnnnnaaalaaLllUall其中称该式为称该式为A的的LU分解分解。第五章方程组的直接解法分解式分解式A=LU也称为也称为杜里特尔杜里特尔(Doolittle)分解分解。由。由A=LU式可求出式可求出A的行列式，即的行列式，即若将若将上三角上三角U写成写成 ，其中，其中D是对角阵，是对角阵， 是单位是单位上三角阵，则有上三角阵，则有称该式为称该式为A的的LDU分解，显然，这种分解具有唯一性。分解，显然，这种分解具有唯一性。.det)()2(22)1(11nnnaaaA UDU ULDA U（5.2.9）第五章方程组的直接解法如果如果

48、A 的的各阶主子式不为零各阶主子式不为零，则可以实现：，则可以实现：(1)(1)(1)1112121(2)(2)2223132( )12111,1nnnnnnnaaalaaLllUall一旦实现一旦实现 A= =LU，则，则 Ax= =b 可以化为可以化为 LUx= =b。令令 Ux= =y，则，则 Ly=b。 由由 Ly=b， 解出解出 y； 再由再由 Ux= =y， 解出解出 x。（）（）库朗库朗(Courant)分解：分解：如果如果L为下三角矩阵，为下三角矩阵，U为单位上三角为单位上三角矩阵。矩阵。（）多利特尔（）多利特尔(Doolittle)分解：分解：如果如果L为为单位单位下三下三角

49、矩阵，角矩阵，U为上三角矩阵；为上三角矩阵；(1)(1)(1)1112121(2)(2)2223132( )12111,1nnnnnnnaaalaaLllUall第五章方程组的直接解法111.6. 04-12-21，将 作Doolittle-分解。AALU例例5 5(1)(1)31212131(1)(1)1111(2)3232(2)221110,2,0410431111111041L,041004004解：由高斯消去法，1,故 = 012-11aallAaaalAUa 100111 010041.211004ALU第五章方程组的直接解法2114Example 232 ,7,.2349AbALU

50、Axb 设，将 作分解 求解.200120112111011001LU解：Solve ,i.e. 10044 11073 ,11192Solve ,i.e. 21110211 .0021LybyyUxyxyx 第五章方程组的直接解法下面讨论矩阵的下面讨论矩阵的含换行含换行的三角分解，即的三角分解，即列主元法中消去过列主元法中消去过程的矩阵表示程的矩阵表示。一般的，将矩阵。一般的，将矩阵A的第的第i行与第行与第j行交换，其结果行交换，其结果相当于矩阵相当于矩阵A左乘左乘一个初等排列矩阵一个初等排列矩阵 ，即，即 ，这里，这里 是单位阵是单位阵I交换第交换第i行与第行与第j行后所得的矩阵，不难验证