理学解线性方程组的直接方法学习教案

1、会计学1理学理学(lxu)解线性方程组的直接方法解线性方程组的直接方法第一页，共156页。nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.,.,.22112222212111212111),.,2 , 1,(njiaij),.,2 , 1(nibi,bAx nbbb,.,21.,.,2121212222111211nnnnnnnnbbbbxxxxaaaaaaaaaA第1页/共156页第二页，共156页。 本章主要介绍求解线性方程组本章主要介绍求解线性方程组(1.1)的直接法。所谓直接法，就是不考虑计算过程的舍入误差的直接法。所谓直接法，就是不考虑计算过程的舍入误差时，经有限次数

2、的运算便可求得方程组准确时，经有限次数的运算便可求得方程组准确(zhnqu)解的方法解的方法.我们还将在我们还将在5中对计算过程中的中对计算过程中的舍入误差作一些初步分析舍入误差作一些初步分析 1.1 Gauss 消去法第2页/共156页第三页，共156页。 （1.31.3）之间有一对应关系之间有一对应关系. .不难看出不难看出: : （1 1）交换矩阵）交换矩阵(1.3)(1.3)的第的第p,qp,q两行两行( (记作记作 ) )相当于交换方程组相当于交换方程组(1.1)(1.1)的第的第p,qp,q两个两个(lin )(lin )方程；方程； （2 2）用一个非零数）用一个非零数 乘矩阵乘

3、矩阵(1.3)(1.3)的第的第p p行行( (记作记作 ) )相当于用相当于用 乘方程组乘方程组(1.1)(1.1)的第的第p p个方程；个方程； （3 3）矩阵）矩阵(1.3)(1.3)的第的第q q行减去第行减去第p p行的行的 倍倍( (记作记作 ) )相当于方程组相当于方程组(1.1)(1.1)的第的第q q个方程减去第个方程减去第p p个方程的个方程的 倍倍. . 因此，解线性方程组因此，解线性方程组(1.1)(1.1)的基本的基本GaussGauss消去法的消元过程可以对它的增广矩阵进行上消去法的消元过程可以对它的增广矩阵进行上述行初等变换述行初等变换qprr nnnnnnnba

4、aabaaabaaabA.,22222221111211ppq. 7542, 1774, 3322321321321xxxxxxxxx例例1 1 用基本用基本(jbn)Gauss(jbn)Gauss消去法解线性方程组消去法解线性方程组第3页/共156页第四页，共156页。.22/)323(2,1;23/)5(;16/6.66,53,3322660051303322486051303322754217743322,321233233323212)1(2231312xxxxxxxxxxxxxxbA第4页/共156页第五页，共156页。 现在，我们将应用于上述现在，我们将应用于上述(shngsh)(

5、shngsh)例例1 1的基本的基本GaussGauss消去法推广到解一般的消去法推广到解一般的 n nn n 阶线性方程组阶线性方程组(1.1).(1.1). Gauss Gauss消去法的消元过程由消去法的消元过程由n1n1步组成：步组成：.,.,20,.,2,)6.1(,.0.0.,.,.,2,.,011)1()1(11)1()1()1()1(2)1(2)1(2)1(221111111)1()1(111111312111niblbbanjalaabaabaabaaabAlbAniaalaaaaiiiijijijijnnnnniiin 第一步第一步 设设 把增广矩阵把增广矩阵(1.3)(1

6、.3)的第一列中元素的第一列中元素 消为零为此，消为零为此，令令 从从 的第的第i(i2i(i2， n) n)行分别行分别(fnbi)(fnbi)减去第一行的减去第一行的 倍，得到倍，得到其中其中第5页/共156页第六页，共156页。) 1() 1(, 1) 1() 1() 1() 1() 1() 1(1,) 1() 1(1) 1(, 1) 1(1, 1) 1(, 1) 1() 1() 1(1,) 1() 1 (2) 1 (2) 1 (1, 2) 1 (2) 1 (22111, 111211) 1() 1() 1 (2) 1 (32) 1 () 1 () 1 (22,., 0) 7 . 1 (

7、.,., 0knkkkkkkkkkknknnkknknkkkknkkkkkkkkkkknkkkkkknkknkkkknaabAabaaabaaabaaabaaaabaaaaabAaabAa 第二步第二步 设设 把矩阵把矩阵 的第二列中元素的第二列中元素 消为零消为零. . 仿此继续进行仿此继续进行(jnxng)(jnxng)消元，假设进行消元，假设进行(jnxng)(jnxng)了了klkl步，得到步，得到 第第 k k步步 设设 把把 的第的第k k列的元素列的元素 消为零，得到消为零，得到第6页/共156页第七页，共156页。.,.,2 , 1,) 9 . 1 (.,.,1,.,1, 0,

8、/) 8 . 1 (.,)0()0() 1() 1() 1() 1()()() 1() 1() 1() 1() 1(1,) 1() 1(1) 1(, 1) 1(1, 1) 1(, 1) 1() 1() 1(1,) 1() 1 (2) 1 (2) 1 (1, 2) 1 (2) 1 (22111, 111211) 1() 1(njibbaankiblbbnkjalaaaaalbaaabaaabaaabaaaabaaaaabAiiijijkkikkikikkjikkijkijkikkkkkikikknknnkknknkkkknkkkkkkkkkkknkkkkkknkknkkkk第7页/共156页第八

9、页，共156页。)1( kkka, 0)1(kkka)1()1(, 1,.,knkkkkaa,)1( krka,)1( krka)1()1(,kkbA),.,1(nkilik 进行进行n1n1步消元后，我们便得到一个步消元后，我们便得到一个(y )(y )上梯形矩阵上梯形矩阵 )10. 1 (,.,) 1() 1() 1() 1() 1(1,) 1() 1 (2) 1 (2) 1 (1, 2) 1 (2) 1 (22111, 111211) 1() 1(nnnnnkkkknkkkkkknkknkknnbabaaabaaaabaaaaabA这里这里, ,我们假设整个消元过程我们假设整个消元过程(

10、guchng)(guchng)中没有进行过矩阵的行交换中没有进行过矩阵的行交换. . 是一个上是一个上三角矩阵三角矩阵. .与上与上 相应的上三角方程组相应的上三角方程组)1( nA)1()1(,nnbA第8页/共156页第九页，共156页。) 1() 1() 1() 1(1) 1(1,) 1() 1 (2) 1 (21) 1 (1, 2) 1 (22) 1 (221111, 1121211.,.,.,.nnnnnnkknkknkkkkkkkknnkkkknnkkkkbxabxaxaxabxaxaxaxabxaxaxaxaa,1,.,1,/)()1(1)1()1(nnkaxabxkkknkjj

11、kkjkkk0(.)1nn)1( nnna.313123nnn第9页/共156页第十页，共156页。例例 2 我们用我们用Gauss消去法来解方程组消去法来解方程组 （1.13）在一个假想的计算机上用断位的五位十进制数算术运算进行在一个假想的计算机上用断位的五位十进制数算术运算进行(jnxng)计算。计算。第一步计算得乘子第一步计算得乘子做完第一步，做完第一步， （1.14）)1( kkka)1( kkka)1(, 1kkka)1( knka.14873.12381348127. 121916321xxx.5 . 475. 025. 50123. 8125. 8002. 00381916,.2

12、5. 0164,125. 0162131312123121rlrrlrbAll第10页/共156页第十一页，共156页。.3,1,1.8593.2,75000.0,99995.0.213262132700123.8125.8002.00381916.2625002.025.512312332xxxxxxl因此，我们得到的计算解因此，我们得到的计算解 的相对误差的相对误差(xin du w ch)(xin du w ch)为为 , ,但但 0.75000 0.75000 和和 2.8593 2.8593 的相对误差的相对误差(xin du w ch)(xin du w ch)较大，它们分别为较大

13、，它们分别为 0 025 25 和和 0 00469.0469. 为了减小计算过程舍入误差的影响，我们在第二步开始时，交换增广矩阵（为了减小计算过程舍入误差的影响，我们在第二步开始时，交换增广矩阵（1 11414）的第的第2 2行与第行与第3 3行，得到行，得到 5310599995. 0 x2x1x第11页/共156页第十二页，共156页。.3, 1, 1,1247.81247.8005 .475.025.50381916.1038095.025.5002.0.123.8125.8002.005 .475.025.50381916123332xxxl我们应当指出，在最后的增广矩阵中，（我们应

14、当指出，在最后的增广矩阵中，（3 3，3 3）和（）和（3 3，4 4）位置的元素都不）位置的元素都不是准确的，侥幸的是在这些是准确的，侥幸的是在这些(zhxi)(zhxi)元素中产生舍入误差而得出元素中产生舍入误差而得出 的准确的准确结果。结果。 3x第12页/共156页第十三页，共156页。)1()1(, 1)1()1(,.,knkkkkkkkkkkaaaa)1()1(maxkiknikkrkaa)1( krka) 1( kika.,.,2 , 1,1,niabnii)(kija)(kijabAx .,.,1,1,1TnnnnnijaabaA第13页/共156页第十四页，共156页。ki0

15、,kikakik.;,taaaatjijikjkjkkki.1,.,1./kjikijijkkikikikaaaankjaalannnnnaax/1, kknkjjkjnkkaxaaxnk/ )(1,.,111,),.,(21nxxx.max,iknikkiaaknxx ,.,1第14页/共156页第十五页，共156页。,max,.,)1()1(,)1()1(1,)1(kkjnjkkjkkknkkkkkkaaaaak)1(,kjkkakj,max)1(,)1(,kijnjikkjiaakk)1(,kjikkakikj第15页/共156页第十六页，共156页。n元，这种选主元的方法似乎是合理的。

16、经过这样修改的n列主元消去法称为按比例(bl)列主元消去法。1410837.12103813410810127. 110210109101644321444444xxx410.5 . 475. 025. 581230812502010381010910164444第16页/共156页第十七页，共156页。,krr.max1ijnjias.,niksasaiikrrk .,.,1,1, 1TnnnnnijaabaAnxx ,.,1.max1ijnjias0is;maxiiknikrrksasa第17页/共156页第十八页，共156页。;ksqkr.tarj0rka./kkikikikaala.k

17、jikijijaaaa./1,nnnnnaax;rkss .qsr;kjat ;rjkjaa ./ )(11,kknkjjkjnkkaxaax第18页/共156页第十九页，共156页。),.,(21nxxx,51,43,21.10, 4, 2.10334102043121331221111321321sasasasssxxx321a4121sss22s.1041023121304310410230433121,21 rrbA第19页/共156页第二十页，共156页。.151110322,3123284322322132313043332222sasa.32,311131313111212121

18、aalaaala322.2,103232ssss3121ll第20页/共156页第二十一页，共156页。, 21171114.11141171113184322323043.111.213231843223230438432232213231304332232323232 xaalarr第21页/共156页第二十二页，共156页。.1320043,032224812xxTnppp,.,21p,.,2 , 1,niippiTnp,.,2, 11p2pnxnxnx1nxnxpppnp1np1nxijlb第22页/共156页第二十三页，共156页。.,.,21TnnnijbbbbaAbAxnxxx,

19、.,21;max1ijnjias.max,iirrpkpnikpkpsasa0is;ipi0,kpra;kptemprk;rkpp .temppr第23页/共156页第二十四页，共156页。./ )(,1,ipnijjjppiiiiaxabx.,jpkpjpjpkiiiaaaa.11ppbb.11,ijpjpppjiiibabb./,nppnnnabx ),.,(21nxxx.10334102043121321xxx第24页/共156页第二十五页，共156页。,51,43,21.10, 4, 23, 2, 13322111 ,1 ,1 ,321ppppppTsasasasssp22pTpp3,

20、 1, 2,31/1 ,1 ,1 ,11122pppaaaa.4322320431173231,32/1 ,1 ,1 ,31133pppaaaa,3022,3133222,2,ppppsasa第25页/共156页第二十六页，共156页。33pTpp1, 3, 2.43223204311711131,111/2,2,2,12233pppaaaa, 321 bbp, 83321012221 ,3ppppbabbb.114811133132313332,1 ,1ppppppbababbb第26页/共156页第二十七页，共156页。,21171141313,333ababxpp. 13042031 ,

21、22,33 ,11111ppppaxaxabx,21171141313,333ababxpp第27页/共156页第二十八页，共156页。n其中. 1,.,2 , 1,.,2 , 1,)16. 1 (,.,2 , 11,.,1,.,1,.,2 , 1,.,2 , 1, 0,.,2 , 1,/)0() 1(,)(,) 1(,) 1()()() 1(,) 1(njniaanknnkjaannkjiiniamaaiiniaiiniaamijijkjikjikkjiikkijkijkkikkkkikikikkkkkkniiinia,.,2 , 1,1,)1(,kkika第28页/共156页第二十九页，共

22、156页。)17. 1 (.,.,2 , 1,)(,)(1,nkaaxkkinnikkk 算法算法(sun f) 3.3 (sun f) 3.3 应用应用Gauss-JordanGauss-Jordan列主元消去法解列主元消去法解 n n阶线性方阶线性方程组程组 其中其中 输入输入 方程组的阶数方程组的阶数 n n；增广矩阵；增广矩阵AA，bb。 输出输出 方程组的解方程组的解 或系数矩阵奇异的信息。或系数矩阵奇异的信息。 step 1 step 1 对对 k=1,2,n k=1,2,n 做做step 2-4step 2-4。 step 2 step 2 选主元选主元: :求求 , ,使使 s

23、tep 3 step 3 若若 ，则输出（，则输出（A is A is singular singular ）；）； 停机。停机。 TnnnnnijaabaA1,1,1,.,nxxx,.,21bAx .max11,.,.,1,ikiiinikiaakkki0,kika第29页/共156页第三十页，共156页。.,.,2 , 1,1,kinikkkaaxnk),.,(21nxxx.1,.,1.,.,1,jiikijijkiikkiikkkkaaaankjaamaiini第30页/共156页第三十一页，共156页。 现在，我们应用现在，我们应用Gauss消去法来解矩阵方程消去法来解矩阵方程 ， （

24、1.18）其中其中 。假如按照自然顺序进行消元，。假如按照自然顺序进行消元，则类似于公式（则类似于公式（1.9），在消元过程的第），在消元过程的第 k 步得到步得到其中规定其中规定 。由回代过程得到方程（由回代过程得到方程（1.18）的解）的解 X 的元素的元素(yun s) 的计算公式为的计算公式为 注意注意,逐步计算得逐步计算得 存放到存放到 的位置上，的位置上， 存放到存放到 的位置上，最后的位置上，最后的解的解 还可存放到还可存放到 的位置上。同解线性方程组的位置上。同解线性方程组 的情形完全一的情形完全一样，一般需要选主元。因此我们可以用样，一般需要选主元。因此我们可以用Gauss列

25、主元消去法列主元消去法或或 Gauss-Jordan列主元消去法解矩阵方程（列主元消去法解矩阵方程（1.18）。）。),.,2 , 1,.,2 , 1( ,),.,2 , 1,( ,)19. 1 (,.,1,.,1,.,1,0)0()0()1()1()()1()1()()()1()1(mjnibbnjiaankimjblbbnkjalaaaaalijijijijkkjikkijkijkijikkijkijkikkkkkikikmnijmnijnnijxXBBaABAX,.,.,1, 1,.,1,)20.1(,)()1(1)1()1(mjnniaxabxiiinikkjiikiijijijkij

26、ijkijbbaa)()(ijxbAxbxijij第31页/共156页第三十二页，共156页。,.,.,2,111,111211121112)1()1(12)2()2(111112111111111)1()1(bLLAxLLbALLbALbAniaalllLbLAxLbALbAiin第32页/共156页第三十三页，共156页。,.,.,.,3,1111111111111111111)1()1(1)()(1111)1(1111)1()1()1(111111111111)1()1()1(22)1(2223212bLLLAxLLLbALLLbALbAbLLbALLAbxAbLLAxLLbALLbAn

27、iaalllLkkkkkkkkkkkkkkkkkkkkkkiin其中其中(qzhng)(qzhng)第33页/共156页第三十四页，共156页。其中其中(qzhng)(qzhng)26. 1 (,)25. 1 (.)24. 1 (,.,.,1,)23. 1 (,111111)1()1(111211111211)1()1(, 11TkkknnnnkkkkikiknkkkkelILbxAbLLLAxLLLnkiaalllL) 1( nA1kLke第34页/共156页第三十五页，共156页。.,.,0,.,0,1TnkkkklllnkixxlxxxxkiikTn,.,1,.,21knxLk10kTk

28、le,)(.11111,)(, 1ILLelelIelIelILLjillelILIelIelIjiTjjTiiTjjTiijinkkkTkkkTkkTkk第35页/共156页第三十六页，共156页。11111111)2(1,1)2(1,)1(22)1(2111)1(22)1(32113111211,21323121nnnnnnnnnnnnaaaaaaaaaaaallllll11121)2(.niinInLLLLL第36页/共156页第三十七页，共156页。)27.1 (.,121111211)1(LUULLLAUALLLUAnnnnkaaaaaaaaaAaaaaAaAaaannnnnnkkk

29、k212222111211222112112111)1()1(2211,.,1111aAk)2(1, 1)1(2211,1kkkaaak121,kAAA121)2(1, 1)1(2211,kkkkAAAaaa第37页/共156页第三十八页，共156页。.1112111ALLLAkkk 由由于于1kA的的k阶阶顺顺序序子子矩矩阵阵)1(KkA是是以以)1()2(1, 1)1 (2211,kkkkkkaaaa为为主主对对角角元元的的上上三三角角阵阵，并并且且易易知知 ,)()()(1112111kkkkkkkkALLLA 其其中中kiL )(1表表示示1iL的的 k阶阶顺顺序序主主子子矩矩阵阵，.

30、 1, 1ki从从而而 ,detdet)det()det(det1111) 1(kkkkkkkAALLA 因因此此 ,det)1()2(1,1)1(2211kkkkkkkaaaaA （1 1. .2 28 8） 故故)1()2(1, 1)1 (2211,kkkkkkaaaa全全不不为为零零的的充充分分必必要要条条件件是是kkAAAA,121 都都非非奇奇异异。 第38页/共156页第三十九页，共156页。我我们们用用rsI表表示示单单位位阵阵 I I 的的第第 r r 行行（列列）与与第第s s 行行（列列）交交换换得得到到的的矩矩阵阵， 通通常常称称为为初初等等排排列列阵阵。 初初等等排排列

31、列阵阵rsI具具有有下下列列简简单单性性质质： （1 1）rsI= =srI； （2 2）用用rsI左左乘乘矩矩阵阵 A A，就就是是交交换换 A A 的的第第 r r 行行与与第第 s s 行行，而而用用rsI右右乘乘 A A 就就是是交交换换 A A 的的第第 r r 列列与与第第 s s 列列； （3 3）;,1IIIIIIsrrsrsrsTrs （4 4）.1detrsI 现现在在， 我我们们可可以以将将G Ga au us ss s 列列主主元元消消去去法法的的消消元元过过程程叙叙述述如如下下。 第第一一步步，假假设设选选取取) 1(11 ,1iai为为主主元元类类似似于于（1 1.

32、 .2 21 1） ，我我们们得得到到 .1 ,111 ,1111bILAxILii第39页/共156页第四十页，共156页。左乘方程（左乘方程（1.301.30）的两端，其中）的两端，其中 ,.,2 , 1,/, 1)1()1(nikiaakimkkkkikik ) 1(Kija是是)1( kA的的),(ji元素。从而，方程组（元素。从而，方程组（1.301.30）化为）化为 )()(kkbxA， 其中其中 )1()()1()(,kkkkkkbMbAMA， 最后，进行了最后，进行了 n n 步消元得到步消元得到 )(nbDx ， （1.321.32） 其中其中 ),()1()1 (22111

33、1nnnnnaaadiagAMMMD。 假如消元过程的每一步都作主行元素除以主元的运算，那么消元过程假如消元过程的每一步都作主行元素除以主元的运算，那么消元过程的第的第 k k 步，步，kM中中的的元素元素), 1(nimik为为 .,/,1)1()1()1(kiaakiamkkkkikkkkik 第40页/共156页第四十一页，共156页。第第二二步步，若若选选)2(2)1(2,2iai为为主主元元，我我们们有有 .1 ,112,121 ,112,121212bILILAxILILiiii 进进行行 n 一一 1 步步消消元元后后，原原方方程程组组 Ax=b 便便化化为为一一个个上上三三角角

34、形形方方程程组组 .1 ,111,111 ,112,121,1111121bILILAxILILILininininninnnn (1.29) 类类似似于于 G Ga au us ss s 消消去去法法的的讨讨论论， 假假定定 G Ga au us ss s- -J Jo or rd da an n 消消去去法法按按自自然然顺顺序序选选主主元元，且且进进行行 k k- -1 1 步步后后方方程程组组已已化化为为 .)1()1(kkbxA （1 1. .3 30 0） 第第 k k 步步 则则是是用用矩矩阵阵 1111,1,11nkkkkkkkkkmmmmmM ( (1 1. .3 31 1)

35、) 第41页/共156页第四十二页，共156页。消消元元过过程程完完成成时时， 我我们们得得到到 IAMMMnn11。 （1 1. .3 33 3） 原原方方程程组组bAx 则则化化为为 bMMMbxnnn11)(。 （1 1. .3 34 4） 它它便便是是方方程程组组bAx 的的解解。 再再假假设设 G Ga au us ss s- -J Jo or rd da an n 消消去去法法按按列列选选主主元元，第第 k k 步步的的主主元元为为)1(,kkika，并并且且每每一一步步都都作作主主行行元元素素除除以以主主元元的的运运算算。消消元元过过程程完完成成时时，便便将将方方程程组组bAx

36、化化为为 bIMIMAxIMMIMinininininnnn1 ,1,1 ,11,111。 （1 1. .3 35 5） 现现在在 IAIMIMIMininninnn1 ,11,1,11。 （1 1. .3 36 6） 因因此此 bIMIMIMxininninnn1 ,11,1,11。 第42页/共156页第四十三页，共156页。TLDL第43页/共156页第四十四页，共156页。2 直接三角(snjio)分解法在在1 1. .6 6 中中我我们们已已经经知知道道，在在 n n 阶阶矩矩阵阵 A A 的的顺顺序序主主子子矩矩阵阵) 1, 2 , 1(nkAk均均非非奇奇异异的的假假定定下下，G

37、 Ga au us ss s 消消去去法法的的消消元元过过程程能能进进行行到到底底。这这样样，还还可可以以把把矩矩阵阵 A A 分分解解成成 LUA ， 其其中中 L L 是是一一个个单单位位下下三三角角阵阵，U U 是是一一个个上上三三角角阵阵。 定定义义 若若方方阵阵 A A 可可以以分分解解成成一一个个下下三三角角阵阵 L L 和和一一个个上上三三角角阵阵 U U 的的乘乘积积，即即 LUA （2 2. .1 1） 则则这这种种分分解解称称为为方方阵阵 A A 的的一一种种三三角角分分解解。 或或L LU U 分分解解。 特特别别，若若 L L 为为单单位位下下三三角角阵阵时时，则则称称

38、它它为为D Do oo oI Ii it tt tl le e 分分解解；若若 U U为为单单位位上上三三角角阵阵时时，则则称称它它为为C Cr ro ou ut t 分分解解。 第44页/共156页第四十五页，共156页。据据1 1 定理知， 若定理知， 若 n n 阶方阵阶方阵 A A 的顺序主子矩阵的顺序主子矩阵121,nAAA均均非奇异，则非奇异，则 GaussGauss 消去法的消元过程可以作出消去法的消元过程可以作出 A A 的的 DoolittleDoolittle 分解分解 LUA 。但对任一非异对角阵。但对任一非异对角阵 D D，我们有，我们有 )(1ULUDLDA， 这也是

39、这也是 A A 的一种三角分解。这说明矩阵的三角分解并不唯一。为了的一种三角分解。这说明矩阵的三角分解并不唯一。为了讨论矩阵讨论矩阵 A A 的三角分解的唯一性问题，我们将的三角分解的唯一性问题，我们将 A A 分解成分解成 LDRA , , （2.22.2） 其中，其中，L L、R R 分别为单位下、上三角阵，分别为单位下、上三角阵，D D 为一个对角阵。这种分解为一个对角阵。这种分解称为矩阵称为矩阵 A A 的一种的一种LDRLDR 分解分解。 定理定理 1 1 阶矩阵阶矩阵 A A 有唯一的有唯一的 LDRLDR 的充分必要条件是的充分必要条件是 A A 的顺序主的顺序主子矩阵子矩阵 A

40、 A； ，； ，A A。 ，。 ，AnAnl l 均非奇异均非奇异 第45页/共156页第四十六页，共156页。证证明明 充充分分性性 设设121,nAAA均均非非奇奇异异，则则由由 G Ga au us ss s 消消去去法法的的消消元元过过程程可可实实现现一一个个 D Do oo ol li it tt tl le e 分分解解：LUA , ,上上三三角角阵阵 U U 的的主主对对角角为为)2(1, 1)1(2211,nnnaaa和和)1( nnna且且)2(1, 1)1(2211,nnnaaa都都不不为为零零。若若 A A 非非奇奇异异，则则由由 0detdetdetULA 知知0)1(

41、nnna。于于是是，令令 ),()1()1(2211nnnaaadiagD, , 则则 D D 非非奇奇异异，且且 LDRULDDLUA1, , ( (2 2. .3 3) ) 其其中中UDR1为为单单位位上上三三角角阵阵。故故( (2 2. .3 3) )式式是是一一个个 L LD DR R 分分解解。若若 A A奇奇异异，则则0)1(nnna。这这时时，令令 ),(),0 ,()2(1, 1)1(22111)2(1, 1)1(2211nnnnnnnaaadiagDaaadiagD 则则 .,10000001111111LARLUADRcDUDDcUUTnnnTnTn 因因此此，矩矩阵阵 A

42、 A 仍仍存存在在一一个个 L LD DR R 分分解解。 第46页/共156页第四十七页，共156页。当当A A 非非奇奇异异时时，设设另另有有一一个个L LD DR R 分分解解：111111,RDLRDLA也也都都是是非非奇奇异异的的， 则则 111RDLLDR. . （2 2. .4 4） 于于是是有有 111111DRRDLL。 （2 2. .5 5） （2 2. .5 5）式式左左端端是是单单位位下下三三角角阵阵，右右端端是是单单位位上上三三角角阵阵，因因此此它它们们应应该该都都是是单单位位阵阵I I，即即 IDRRDILL111111,。 从从而而有有 LL 1 以以及及 DDR

43、R1111。 （2 2. .6 6） 又又因因11RR是是一一个个单单位位上上三三角角阵阵，DD11是是对对角角阵阵，因因此此由由（2 2. .6 6）式式有有 IDDIRR1111,。 故故 .11DDRR 第47页/共156页第四十八页，共156页。若若 A A 奇奇异异，则则（2 2. .4 4）可可写写成成分分块块形形式式 1000010100001011111TTTTTTcRDbLcRDbL. . 由由此此得得出出 1111111111cDbRDbcDLRDLcDbRDbcDLRDLTTTT, , 其其中中111,RDLRDL皆皆非非奇奇异异。类类似似于于前前面面的的推推导导，可可得

44、得 .,11111ccbbRRDDLLTT 必必要要性性 假假设设矩矩阵阵 A A 有有唯唯一一的的 L LD DR R 分分解解。当当 A A 非非奇奇异异时时，L L, ,D D, ,R R 皆皆非非奇奇异异。当当 A A 奇奇异异时时，设设),(21nddddiagD，则则必必0),1, 1( 0nidnid，否否则则 A A 的的 L LD DR R 分分解解不不可可能能唯唯一一。因因此此，不不论论哪哪种种情情形形，L L, ,D D, ,R R 的的 i i 阶阶主主子子矩矩阵阵iiiRDL,都都非非奇奇异异，1, 2 , 1ni。 第48页/共156页第四十九页，共156页。由由于

45、于 , 1, 2 , 1,niRDLAiiii 因因此此121,nAAA都都非非奇奇异异。 如如果果对对线线性性方方程程组组 bAx （2 2. .7 7） 的的系系数数矩矩阵阵 A A 作作出出 L LU U 分分解解（由由 A A 确确定定 L L 和和 U U） ，那那么么方方程程组组（2 2. .7 7）可可写写成成 bLUx . . 于于是是，解解方方程程组组（2 2. .7 7）便便等等价价于于解解下下面面的的两两个个方方程程组组： bLy ( (2 2. .8 8) ) 和和 yUx 。 （2 2. .9 9） 这这就就是是解解线线性性方方程程组组的的直直接接三三角角分分解解法法

46、。 （2 2. .8 8）和和（2 2. .9 9）分分别别为为为为下下、上上三三角角形形方方程程组组，极极容容易易求求解解。 第49页/共156页第五十页，共156页。G Ga au us ss s 消消去去法法的的消消元元过过程程是是将将 A A 的的三三角角分分解解和和解解方方程程组组（2 2. .8 8）同同时时进进行行（注注意意 L L 是是单单位位下下三三角角阵阵，即即作作 D Do oo ol li it tt tl le e 分分解解） ，其其回回代代过过程程是是解解方方程程组组（2 2. .9 9） 。然然而而，直直接接三三角角分分解解法法是是从从矩矩阵阵 A A 的的元元素

47、素直直接接由由关关系系式式 A AL LU U 确确定定 L L 和和 U U 的的元元素素，不不必必像像G Ga au us ss s 消消去去法法那那样样计计算算那那些些中中间间结结果果。 第50页/共156页第五十一页，共156页。设设矩矩阵阵nnijaA可可作作出出 C Cr ro ou ut t 分分解解 LUA 其其中中,22221112112121222111nnnjjjnjnjnnnniiiiuuuuuuuuuuUlllllllllL ( (2 2. .1 10 0) ) njujj,1,1。 我我们们根根据据这这个个三三角角分分解解式式来来确确定定 L L 的的元元素素 ij

48、l和和 U U 的的元元素素 iju。由由LUA 两两端端矩矩阵阵的的（i i，j j）位位置置元元素素对对应应相相等等，有有 njiulajirrjirij,2, 1,),min(1。 （2 2. .1 11 1） 当当 j j= =1 1 时时，有有 niaulliii, 2 , 1,11111。 （2 2. .1 12 2） 当当 i i= =1 1 时时，有有 njauljj, 2,1111, , 因因而而设设011l，则则有有 njlaujj, 2,1111。 （2 2. .1 13 3） 第51页/共156页第五十二页，共156页。因因此此，第第一一步步是是由由（2 2. .1 1

49、2 2）式式计计算算 L L 的的第第一一列列元元素素，而而由由（2 2. .1 13 3）式式计计算算 U U 的的第第一一行行元元素素。 第第二二步步，我我们们计计算算 L L 的的第第二二列列和和 U U 的的第第二二行行元元素素。 假假设设我我们们进进行行了了 k k1 1 步步，计计算算得得 L L 的的前前 k k- -1 1 列列元元素素和和 U U 的的前前 k k- -1 1行行元元素素。 第第 k k 步步， 将将要要计计算算 L L 的的第第 k k 列列元元素素和和 U U 的的第第 k k 行行元元素素。 由由 （2 2. .1 11 1）式式，当当 j j= =k

50、k 时时，对对 i i= =k k, ,k k1 1, , ,n n 有有 ikkrrkirkrrkiriklulula111， 即即 nkiulalkrrkirikik,11。 （2 2. .1 14 4） （2 2. .1 14 4）式式右右端端所所有有的的项项均均为为已已知知，从从而而便便可可以以用用（2 2. .1 14 4）式式来来计计算算 L L的的第第 k k 列列元元素素。仿仿此此，由由（2 2. .1 11 1）式式，当当 i i= =k k 时时，对对于于 j j= =k k1 1，n n有有 kjkkkrrjkrkrrjkrikululula111。 第52页/共156页

51、第五十三页，共156页。因此，假设因此，假设0kkl，则有，则有nkjlulaukkkrrjkrkjkj, 1,)(11 (2.15) (2.15) （2.152.15）式右端的各项均为已知，从而便可由（）式右端的各项均为已知，从而便可由（2.152.15）式来计算）式来计算 U U 的第的第 k k 行元行元素。素。 综合上述，进行综合上述，进行 n n 步计算便可得步计算便可得 L L 和和 U U 的全部元素。注意，进行第的全部元素。注意，进行第 n n 步计步计算时，必须由（算时，必须由（2.142.14）式计算）式计算 L L 的元素的元素nnl，但不必用（，但不必用（2.152.1

52、5）式来计算）式来计算nnu，因因1nnu。 实现矩阵实现矩阵 A A 的的 CroutCrout 分解后，分解后， 解方程组解方程组bAx 就等价于解两个三角形方就等价于解两个三角形方程组程组bLy 和和yUx 。 上述解线性方程组上述解线性方程组bAx 的方法称为的方法称为 CrCro outut 方法方法。 现将它的计算步骤归现将它的计算步骤归结如下：结如下： （1 1） 计算计算 A A 的的 LULU 分解中分解中 L L 的第一列和的第一列和 U U 的第一行元素：的第一行元素： ).1(,2,;,2, 1,11111111unjlaunialjjii 第53页/共156页第五十四

53、页，共156页。（2 2）对对 k k= =2 2, , ,n n 计计算算 L L 的的第第 k k 列列元元素素： nkiulalkrrkirikik,11 以以及及 U U 的的第第) 1,(nnunkk行行元元素素: : )1(, 1,)(11kkkkkrrjkrkjkjunkjlulau。 （3 3）解解下下三三角角形形方方程程组组bLy ： ., 2,)(,111111nklylbylbykkkrrkrkk （4 4）解解单单位位上上三三角角形形方方程程组组yUx ： . 1 , 1,1nkxuyxyxnkrrkrkknn 第54页/共156页第五十五页，共156页。在作矩阵在作矩

54、阵 A A 的的 LULU 分解时，分解时，A A 的元素的元素ija在计算出在计算出ijl或或iju以后不再以后不再使用了。使用了。因此，因此，L L 和和 U U 的元素便可存放到矩阵的元素便可存放到矩阵 A A 中相应元素的位置上中相应元素的位置上（1iiu不必存贮，不必存贮，ni, 1） 。） 。这样，最后矩阵这样，最后矩阵 A A 的位置存放的元的位置存放的元素就变成素就变成 nnnnnnnlllulluul21, 1222111211。 例例 1 1 应用应用 CroutCrout 方法解方程组方法解方程组 551631011411014211264321xxxx。 第55页/共1

55、56页第五十六页，共156页。解解 首首 先先 ， 对对 方方 程程 组组 的的 系系 数数 矩矩 阵阵 A A 作作 C Cr ro ou ut t 分分 解解 A A= =L LU U: : ,741911093113791037321101513102616131631093113791037321101513102616131631311143211015131026161316310114110142616131631011411014211264321 kkkkA 第56页/共156页第五十七页，共156页。于于是是得得到到 .1000379100101511061613110,7

56、4191109311010373210031020006UL 其其次次求求方方程程组组)5, 5 , 1, 6(TbbLy的的解解，得得 .1,3746,109,14321yyyy 最最后后，求求方方程程组组yUx 的的解解，得得 .1,1,1,14321xxxx 这这就就是是要要求求的的方方程程组组的的解解。 第57页/共156页第五十八页，共156页。设设矩矩阵阵的的各各顺顺序序主主子子矩矩阵阵都都非非奇奇异异，据据定定理理 1 可可推推知知 Crout 分分解解是是唯唯一一的的，且且分分解解式式 LU 中中 L 的的主主角角元元nnll,11皆皆非非零零。这这就就是是说说，Crout分分

57、解解过过程程可可以以进进行行到到底底。但但是是，一一般般地地，我我们们只只限限于于 A 非非奇奇异异，因因此此还还需需类类似似于于 Gauss 列列主主元元消消去去法法那那样样选选主主元元进进行行 Crout 分分解解。就就是是每每计计算算得得 L 的的一一列列元元素素后后，找找出出该该列列中中绝绝对对值值最最大大的的元元素素，比比方方说说kikl,，然然后后交交换换矩矩阵阵 A 以以及及 L 的的第第ki行行与与第第 k 行行，再再进进行行其其后后的的计计算算。这这样样并并不不影影响响分分解解式式中中已已经经计计算算得得 L 和和 U 的的其其它它元元素素。 若若用用按按列列选选主主元元的的

58、 Crout 方方法法解解线线性性方方程程组组bAx ，进进行行 A 和和L 的的行行交交换换的的同同时时，还还要要交交换换右右端端向向量量 b 的的相相应应分分量量。 例例 2 应应用用按按列列选选主主元元 C Cr ro ou ut t 方方法法解解方方程程组组 .162113121113121111214321xxxx 第58页/共156页第五十九页，共156页。解解 首首 先先 ，我我 们们 按按 列列 主主 元元 对对 系系 数数 矩矩 阵阵 进进 行行 C Cr ro ou ut t 分分 解解并并 相相 应应 地地 交交 换换 方方 程程 组组 的的 右右 端端 项项 ： 113

59、35221234117274371631313131133522123411113716313131311335211137121234163131313113121112121211631313131131211121212116111311312611131121111121,323121rrkrrkbA 第59页/共156页第六十页，共156页。.22337173411231572335217274371631313132171734112315723352172743716313131321717341117233521727437163131313117233522171734117

60、274371631313134343 krrk因因 此此 ， 得得 到到 LUAIII313243, 其其 中中 .100023151007274103131311,2337173410723352003710003UL 第60页/共156页第六十一页，共156页。方方程程组组bAx 便便化化为为 bIIILUx313243， 即即 TLUx2,1,1,6。 其其次次，我我们们解解方方程程组组TLy2,1,1,6，得得 Ty2,2330,73,2。 最最后后，解解方方程程组组yUx 得得 Tx2,0,1,1。 它它便便是是原原方方程程组组bAx 的的解解。 算算法法 3.5 应应用用按按列列选