第一節(jié)：三角形方程組和三角分解

1、1第一章第一章 線性方程組的直接解法線性方程組的直接解法Dr. Zhang南昌大學(xué)理學(xué)院數(shù)學(xué)系E-mail: 1.1 三角形方程組和三角分解三角形方程組和三角分解上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 2 如何利用電子計(jì)算機(jī)來快速、有效地求解線如何利用電子計(jì)算機(jī)來快速、有效地求解線性方程組的問題是數(shù)值線性代數(shù)研究的核心問題，性方程組的問題是數(shù)值線性代數(shù)研究的核心問題，而且也是目前仍在繼續(xù)研究的重大課題之一。這而且也是目前仍在繼續(xù)研究的重大課題之一。這是因?yàn)楦鞣N各樣的科學(xué)與工程問題往往最終都要是因?yàn)楦鞣N各樣的科學(xué)與工程問題往往最終都要?dú)w結(jié)為一個(gè)線性方程組的求解問題。例如結(jié)構(gòu)分歸結(jié)為一個(gè)線性方程組

2、的求解問題。例如結(jié)構(gòu)分析、網(wǎng)絡(luò)分析、大地測量、數(shù)據(jù)分析、最優(yōu)化及析、網(wǎng)絡(luò)分析、大地測量、數(shù)據(jù)分析、最優(yōu)化及非線性方程組和微分方程組數(shù)值解等，都常遇到非線性方程組和微分方程組數(shù)值解等，都常遇到線性方程組的求解問題。線性方程組的求解問題。 線性方程組的求解問題是一個(gè)古老的數(shù)學(xué)問線性方程組的求解問題是一個(gè)古老的數(shù)學(xué)問題。早在中國古代的題。早在中國古代的九章算術(shù)九章算術(shù)中，就已詳細(xì)中，就已詳細(xì)地描述了解線性方程組的消元法。到了地描述了解線性方程組的消元法。到了19世紀(jì)初，世紀(jì)初，西方也有了西方也有了Gauss消去法，然后求解未知數(shù)多的消去法，然后求解未知數(shù)多的大型線性方程組則是在大型線性方程組則是在2

3、0世紀(jì)中葉電子計(jì)算機(jī)問世紀(jì)中葉電子計(jì)算機(jī)問世后才成為可能。世后才成為可能。上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 3 求解線性方程組的數(shù)值方法大體上可分為求解線性方程組的數(shù)值方法大體上可分為直直接法接法和和迭代法迭代法兩大類。兩大類。 直接法直接法是指沒有舍入誤差的情況下經(jīng)過有限是指沒有舍入誤差的情況下經(jīng)過有限次運(yùn)算可求得方程組的精確解的方法。因此，次運(yùn)算可求得方程組的精確解的方法。因此，直接法又稱為精確法。直接法又稱為精確法。 迭代法迭代法則是采取逐次逼近的方法，亦即從一則是采取逐次逼近的方法，亦即從一個(gè)初始向量出發(fā)，按照一定的計(jì)算格式，構(gòu)造個(gè)初始向量出發(fā)，按照一定的計(jì)算格式，構(gòu)造一個(gè)向量的

4、無窮序列，其極限才是方程組的精一個(gè)向量的無窮序列，其極限才是方程組的精確解，只經(jīng)過有限次運(yùn)算得不到精確解。確解，只經(jīng)過有限次運(yùn)算得不到精確解。上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4 這一章，我們將主要介紹解線性方程組的一類這一章，我們將主要介紹解線性方程組的一類最基本的直接法最基本的直接法GaussGauss消去法消去法, , 其特點(diǎn)是其特點(diǎn)是 （1 1）求解）求解中小規(guī)模線性方程組中小規(guī)模線性方程組（即階數(shù)不要（即階數(shù)不要太高，例如不超過太高，例如不超過10001000）最常用的方法；）最常用的方法； （2 2）一般用于系數(shù)矩陣稠密（即矩陣的絕大）一般用于系數(shù)矩陣稠密（即矩陣的絕大多數(shù)元

5、素都是非零的）而又沒有任何特殊結(jié)構(gòu)多數(shù)元素都是非零的）而又沒有任何特殊結(jié)構(gòu)的線性方程組。的線性方程組。 如若系數(shù)矩陣具有某種特殊形式，則為了盡可如若系數(shù)矩陣具有某種特殊形式，則為了盡可能地減少計(jì)算量與存儲(chǔ)量，需采用其他專門的能地減少計(jì)算量與存儲(chǔ)量，需采用其他專門的方法來求解。方法來求解。51.1.1 三角形方程組的解法三角形方程組的解法1.1.3 三角分解的計(jì)算三角分解的計(jì)算1.1.2 Gauss變換變換1.1 三角形方程組和三角分解三角形方程組和三角分解 由于三角形方程組簡單易于求解，而且它又是用分解方法解一般線性方程組的基礎(chǔ)，所以我們首先考慮這種特殊類型的線性方程組的解法。上頁上頁 下頁下

6、頁 返回返回 結(jié)束結(jié)束 61.1.11.1.1三角形方程組的解法三角形方程組的解法 (1.1.1)下三角形方程組形如Lyb這里 是已知的， 是未知的，而 是已知的非奇異下三角陣，即1( ,)TnnbbbR1(,)TnnyyyRn nijLlR 112122313233123nnnnnlllLlllllll,其中其中 0,1,2,., .iilin上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 7 我們?nèi)菀椎玫椒匠探M（我們?nèi)菀椎玫椒匠探M（1.1.11.1.1）的解）的解的分量表達(dá)式的分量表達(dá)式11,1,2, .iiiijjiijybl ylin 這種解方程組（1.1.1）的方法稱之為前代法前代法.如果在

7、實(shí)際計(jì)算時(shí)將得到的 就存放在 所用的存儲(chǔ)單元內(nèi)，并適當(dāng)調(diào)整一下運(yùn)算順序，可得如下算法：ibiy上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 8算法算法1.1.11.1.1（解下三角形方程組：前代法）（解下三角形方程組：前代法）1:1( )( )/ ( , )(1: )(1: )( ) (1: , )( )( )/ ( , )for jnb jb jL j jb jnb jnb j L jn jendb nb nL n n 該算法所需要的加、減、乘、除運(yùn)算的次數(shù)為：21(1)(21)22nin ninn即該算法的運(yùn)算量為 。2n上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 9注意：針對(duì)方程（注意：針對(duì)方程（

8、1.1.11.1.1）使用消元法，我們）使用消元法，我們能夠得到另外一種程序。能夠得到另外一種程序。算法分析如下：算法分析如下：第一步：對(duì)增廣矩陣實(shí)施行初等變換，使之成為其中：其中： 顯然地，上式右端是顯然地，上式右端是與原方程組同解的一個(gè)方程組的增廣矩陣。與原方程組同解的一個(gè)方程組的增廣矩陣。(1)(1)(1)111111/,2,., .iiibblbbb lin上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 10第第k步：消元工作如下步：消元工作如下上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 11經(jīng)經(jīng)n-1步變換之后，我們將得到原方程組的如下同解步變換之后，我們將得到原方程組的如下同解方程：方程：其中

9、：其中： ( )(1)( )(1)( ),/,1, .kkkkkkkk kiiki kbblbbblikn(1)1(1)1(1),11nnnn nnbblb上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 12最后，對(duì)第最后，對(duì)第n個(gè)方程做行初等變換，令個(gè)方程做行初等變換，令 我們便得到原方程組的一個(gè)最簡形式的同解方程組：我們便得到原方程組的一個(gè)最簡形式的同解方程組：( )(1),/,nnnnn nbbl,xb其中：其中： (1)(2)( )12(,) .nTnbbbb綜合上述，我們得到如下算法程序：綜合上述，我們得到如下算法程序：1:1( )( )/ ( , );1:( )( )( )* ( , );

10、( )( )/ ( , )for inb ib il i ifor jinb jb jb il j iendendb nb nl n n 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 13 (1.1.2)再考慮如下上三角形方程組再考慮如下上三角形方程組: Uxy其中其中 是非奇異上三角陣。是非奇異上三角陣。 ,n ni jUuR這一方程組可以用所謂的回代法解之，即從方程組這一方程組可以用所謂的回代法解之，即從方程組的最后一個(gè)方程出發(fā)依次求出的最后一個(gè)方程出發(fā)依次求出 ，其計(jì)，其計(jì)算公式為算公式為11,nnxxx1,1,1;niiijjiij ixyu xuin n 上頁上頁 下頁下頁 返回返回 結(jié)束

11、結(jié)束 14顯然該算法的運(yùn)算量也為 。2n算法算法1.1.21.1.2（解上三角形方程組：回代法）（解上三角形方程組：回代法）: 1:2( )( )/( , )(1:1)(1:1)( )*(1:1, )(1)(1)/(1,1)for jny jy jU j jyjyjy jUjjendyyU 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 15對(duì)于一般的線性方程組對(duì)于一般的線性方程組 （1.1.3）Axb其中其中 和和 是已知的，是已知的， 是未知的，如果是未知的，如果我們能夠?qū)⑽覀兡軌驅(qū)分解為：分解為： ，即一個(gè)下三角陣，即一個(gè)下三角陣L與一與一個(gè)上三角陣個(gè)上三角陣U的乘積，那么原方程組的解的乘積，

12、那么原方程組的解x便可由下便可由下面兩步得到：面兩步得到：n nARnbRnxRALU(1) 用前代法解用前代法解 得得y； Lyb(2) 用回代法解用回代法解 得得x.Uxy所以對(duì)于求解一般的線性方程組來說，關(guān)鍵是如何所以對(duì)于求解一般的線性方程組來說，關(guān)鍵是如何將將A分解為一個(gè)下三角陣分解為一個(gè)下三角陣L與一個(gè)上三角陣與一個(gè)上三角陣U的乘積，的乘積，這正是我們本節(jié)的中心任務(wù)。這正是我們本節(jié)的中心任務(wù)。 返回161.1.2 Gauss變換變換 引理引理1 設(shè) 是兩個(gè)單位下三角矩陣，則 仍是單位下三角矩陣。12,n nL LR12LL L 引理引理2 設(shè) 是兩個(gè)上三角矩陣，則 仍是上三角矩陣 。

13、12,n nU UR12UU U定義定義1 設(shè) ，那么以下的變換稱為初等行（列）變換：m nAR第一種初等變換又稱對(duì)換?；Q的兩行（列）；第二種初等變換又稱倍乘。用中一個(gè)非零的數(shù)乘的某行（列）；第三種初等變換又稱倍加。用中的一個(gè)數(shù)乘的某行（列）加到另外一行（列）。上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 17引理引理3 設(shè)設(shè) 是一個(gè)初等矩陣，則方程組是一個(gè)初等矩陣，則方程組與方程組與方程組 同解。同解。n nPRPAxPbAxb 欲把一個(gè)給定的矩陣欲把一個(gè)給定的矩陣A分解為一個(gè)下三角陣分解為一個(gè)下三角陣L與一個(gè)上三角與一個(gè)上三角陣陣U的乘積，最自然的做法是通過一系列的初等變換，逐步將的乘積，最自

14、然的做法是通過一系列的初等變換，逐步將A約化為一個(gè)上三角陣，而又能保證這些變換的乘積是一個(gè)下約化為一個(gè)上三角陣，而又能保證這些變換的乘積是一個(gè)下三角矩陣。這可歸結(jié)為：對(duì)于一個(gè)任意給定的向量三角矩陣。這可歸結(jié)為：對(duì)于一個(gè)任意給定的向量 找一找一個(gè)盡可能簡單的下三角矩陣，使經(jīng)這一矩陣作用之后的第個(gè)盡可能簡單的下三角矩陣，使經(jīng)這一矩陣作用之后的第k+1至第至第n分量均為零。能夠完成這一任務(wù)的最簡單的下三角矩陣分量均為零。能夠完成這一任務(wù)的最簡單的下三角矩陣便是便是Gauss變換陣。變換陣。nxR上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 18定義定義3 如下形式的初等下三角陣如下形式的初等下三角陣,Tk

15、nkkLIl e其中其中 即即1,(0,0,) ,Tkkknklll這種類型的初等單位下三角矩陣稱作這種類型的初等單位下三角矩陣稱作 Gauss 變換變換，而稱向量而稱向量 為為 Gauss 向量向量。kl1,1111kkkn kLll上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 19命題命題1 對(duì)于一個(gè)給定的向量對(duì)于一個(gè)給定的向量 若若 ，取，取其中：其中：12( ,),Tnnxx xxR0kx 1,(0,0,) ,Tkkknklll,1, .iikkxliknx 則則Gauss變換：變換： 使使TknkkLIl e1( ,0,0) .TkkL xxx證明：由于證明：由于111,( ,) ,Tkk

16、kk kknk nkL xxxxx lxx l將將 代入，即得出結(jié)論。代入，即得出結(jié)論。iikkxlx上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 20命題命題2 Gauss變換變換 的逆變換為的逆變換為kL1TknkkLIl e命題命題3 當(dāng)當(dāng) 時(shí)，則時(shí)，則pq(1),TTpqppqqL LIl el e11(2).TTpqppqqL LIl el e上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 21 命題命題4 設(shè)設(shè) ，則對(duì)，則對(duì)A施以指標(biāo)為施以指標(biāo)為k的的Gauss變換，變換，A 的前的前k行保持不變。行保持不變。n nAR則則,Tkke Aa111,()()kTTkkkkkkkkknnkkaaL

17、AIl eAAle Aalaal a從而從而證明證明 將將A按行分塊，記為按行分塊，記為121,(,.,),1,2,., .kkknnaaAaaakna 返回221.1.3 三角分解的計(jì)算三角分解的計(jì)算1.1.3.1 算法的理論分析算法的理論分析假定 ，三角分解是指分解 ，其中 為下三角矩陣， 為上三角矩陣?；诜纸馐降倪@種表達(dá)方式，有時(shí)亦稱三角分解為LU分解。n nARALUn nLRn nUR下面我們來討論怎樣利用下面我們來討論怎樣利用Gauss變換來實(shí)現(xiàn)變換來實(shí)現(xiàn)A的三的三角分解。先來考察一個(gè)簡單的例子。設(shè)角分解。先來考察一個(gè)簡單的例子。設(shè)1472583610A上頁上頁 下頁下頁 返回返

18、回 結(jié)束結(jié)束 23 我們首先計(jì)算一個(gè)Gauss變換 使得 的第1列的后兩個(gè)元素為0。由命題1和4容易得出1L1L A且1100210301L 11470360611L A然后再計(jì)算Gauss變換 使得 的第2列的最后一個(gè)元素為0，再由命題1和4得2L21()L L A上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 242100010021L且且21147()036001L L A由命題由命題211121121,01,301021LL令令1211147()21,036321001LL LU上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 25則有則有.ALU對(duì)于一般的對(duì)于一般的n階矩陣階矩陣A，在一定條件下在一定

19、條件下，我們也可以，我們也可以計(jì)算計(jì)算n-1個(gè)個(gè)Gauss變換變換 ，使得，使得 為為上三角矩陣上三角矩陣。11,nLL11nLL A(1)(1)(1)1112121(1)22,0kkkkkkAAALLL AA事實(shí)上，記事實(shí)上，記 ，并假定已求出，并假定已求出k-1個(gè)個(gè)Gauss變變換換 使得使得11,()n nkLLRkn(0)AA其中其中 是是k-1階上三角陣，階上三角陣， 為為 (1)11kA(1)22kA(1)(1)(1)22(1)(1)kkkkknkkknknnaaAaa上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 26如果如果 ，則我們就又可以確定一個(gè)，則我們就又可以確定一個(gè)Gauss變

20、換變換 ，使，使得得 中第中第k列的最后列的最后n-k個(gè)元素為個(gè)元素為0。由前面所介紹的。由前面所介紹的Gauss變換可知，這樣的變換可知，這樣的 應(yīng)為應(yīng)為(1)0kkkakL(1)kkL AkLTknkkLIl e其中其中(1)1,(1)(0,0,) ,1, .kTikkkknkikkkkallllikna因?yàn)橐驗(yàn)?，故，故 是唯一確定的。對(duì)于這樣確定的是唯一確定的。對(duì)于這樣確定的 ，我們有我們有(1)0kkkakLkL上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 27 其中其中 是是k階上三角陣。從階上三角陣。從k=1出發(fā)，如此進(jìn)行出發(fā)，如此進(jìn)行n-1步，步，最終所得矩陣最終所得矩陣 即為我們所

21、要求的上三角矩陣，則我們就即為我們所要求的上三角矩陣，則我們就已經(jīng)實(shí)現(xiàn)了已經(jīng)實(shí)現(xiàn)了A的上三角形約化。的上三角形約化。 若令若令( )11kA(1)nA則則.ALU注意到對(duì)注意到對(duì) j i有有 , 從而從而0Tj ie l 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 28 由此可見，由此可見，L不僅是一個(gè)單位下三角矩陣，而且是非常不僅是一個(gè)單位下三角矩陣，而且是非常容易得到的。容易得到的。 即即L具有形式具有形式21121313212311 , ,.,011nnnnlLIl lllllll 通常稱通常稱Gauss消去過程中的消去過程中的 為主元。顯然，當(dāng)且僅當(dāng)為主元。顯然，當(dāng)且僅當(dāng) 均不為零時(shí)，算法

22、均不為零時(shí)，算法1.1.3才能進(jìn)行到底。那才能進(jìn)行到底。那么自然要問：給定的矩陣么自然要問：給定的矩陣A滿足什么，才能保證所有主元均不滿足什么，才能保證所有主元均不為零？這一問題可由下面定理回答。為零？這一問題可由下面定理回答。(1)kkka(1)(1,.,1)kkkakn上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 29 定理定理1.1.1 主元主元 均不為零的充分與必要均不為零的充分與必要條件是條件是A的的i階順序主子陣階順序主子陣 都是非奇異的。都是非奇異的。(1)(1,., )iiiaik(1,., )iA ik 證明證明: 對(duì)對(duì)k用歸納法用歸納法. 當(dāng)當(dāng)k=1時(shí)，時(shí)， ，定理顯然成立。，定

23、理顯然成立。假定定理直至假定定理直至k-1成立成立, 下面只需證明下面只需證明“若若 非奇非奇異異, 則則 非奇異的充要條件是非奇異的充要條件是 ”即可即可. 由歸納法由歸納法假定知假定知 . 因此，因此，Gauss消去過程至少可消去過程至少可進(jìn)行進(jìn)行k-1步，即可得到步，即可得到k-1個(gè)個(gè)Gauss變換變換 ，使得，使得(0)111Aa11,kAAkA(1)0kkka(1)0(11)iiiaik 11,kLL（1.1.4） (1)(1)(1)1112121(1)220kkkkkkAAALLL AA其中其中 是對(duì)角元為是對(duì)角元為 的上三角陣。的上三角陣。 (1)11kA(1)(1,.,1)ii

24、iaik上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 30由此可知由此可知 的的k階順序主子陣有如下形式階順序主子陣有如下形式(1)kA(1)11(1)*kkkkAa若將若將 的的k階順序主子陣分別記為階順序主子陣分別記為 ，則由（則由（1.1.4）及下三角陣的性質(zhì)可知）及下三角陣的性質(zhì)可知11,kLL11() ,()kkkLL(1)11121(1)*() ()()kkkkkkkkkkALLLAa注意到注意到 是單位下三角陣，由此立即得到是單位下三角陣，由此立即得到iL(1)(1)11detdet,kkkkkAaA從而有從而有 非奇異當(dāng)且僅當(dāng)非奇異當(dāng)且僅當(dāng) 。kA(1)0kkka上頁上頁 下頁下頁

25、返回返回 結(jié)束結(jié)束 31定理定理1.1.2 若若 的順序主子陣的順序主子陣 均非奇異，則存在唯一的單位下三角陣均非奇異，則存在唯一的單位下三角陣 和上三角和上三角陣陣 使得使得 。n nAR(1,.,1)k kkARknn nLRn nURALU上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 321.1.3.2 算法的編程算法的編程 這種計(jì)算三角分解的方法稱作Gauss消去法消去法。實(shí)際編程計(jì)實(shí)際編程計(jì)算時(shí)，我們還需要弄清的是：當(dāng)算時(shí)，我們還需要弄清的是：當(dāng) 作用于作用于 后，后， 的哪的哪些元素作了改變？以及作了怎樣的改變？此外，些元素作了改變？以及作了怎樣的改變？此外， 及及 的的元素又是怎樣存儲(chǔ)起來的？元素又是怎樣存儲(chǔ)起來的？因?yàn)閗L(1)kA(1)kAkL( )kA( )(1)(1)(1)(1)(),kkTkkTkkkkkkAL AIl eAAl e A并注意到 是 的第k行