線性方程組的直接解法

1、第五章 線性方程組的直接解法1 Gauss1 Gauss消去法消去法 1.1 1.1 順序順序GaussGauss消去法消去法 1.2 1.2 列主元列主元GaussGauss消去法消去法 2 2 直接三角分解方法直接三角分解方法 2.1 Gauss 2.1 Gauss消去法的矩陣運(yùn)算消去法的矩陣運(yùn)算 2.2 2.2 DoolittleDoolittle分解法分解法 2.3 2.3 平方根法平方根法 2.4 2.4 追趕法追趕法 在科學(xué)計(jì)算中，經(jīng)常需要求解含有在科學(xué)計(jì)算中，經(jīng)常需要求解含有n n個未知量個未知量 的的n n個方程構(gòu)成的線性方程組個方程構(gòu)成的線性方程組方程組還可以用矩陣形式表示為

2、方程組還可以用矩陣形式表示為 bAx nnnnnnnnbbbbxxxxaaaaaaaaaA2121212222111211, nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(5.1)(5.1) 根據(jù)根據(jù) GramerGramer（克萊姆）法則（克萊姆）法則，求解方程組（，求解方程組（5.15.1）時(shí)，要計(jì)算大量的行列式，所需乘法次數(shù)大約為時(shí)，要計(jì)算大量的行列式，所需乘法次數(shù)大約為!)1(2nnN 當(dāng)當(dāng) n n 較大時(shí)，較大時(shí)， 這個計(jì)算量是驚人的。這個計(jì)算量是驚人的。 例例 如，如， 當(dāng)當(dāng) n= 20 n= 20 時(shí)，約需乘法次數(shù)為時(shí)，約

3、需乘法次數(shù)為20107.9 N0)det( A若系數(shù)矩陣若系數(shù)矩陣A A非奇異，即非奇異，即Tnxxxx),(21 則方程組有惟一解則方程組有惟一解 如果用每秒百萬次的計(jì)算機(jī)來計(jì)算，需要三千萬如果用每秒百萬次的計(jì)算機(jī)來計(jì)算，需要三千萬年時(shí)間?？梢娔陼r(shí)間?？梢奊ramerGramer法則不是一種實(shí)用的方法。法則不是一種實(shí)用的方法。 因此，必須構(gòu)造出適合于計(jì)算機(jī)使用的線性方程因此，必須構(gòu)造出適合于計(jì)算機(jī)使用的線性方程組的求解方法。組的求解方法。 直接方法的特點(diǎn)直接方法的特點(diǎn)是，如果不考慮計(jì)算過程中的是，如果不考慮計(jì)算過程中的舍入誤差，運(yùn)用此類方法經(jīng)過有限次算術(shù)運(yùn)算就能舍入誤差，運(yùn)用此類方法經(jīng)過有限

4、次算術(shù)運(yùn)算就能求出線性方程組的精確解。求出線性方程組的精確解。 求解線性方程組的數(shù)值方法可分為兩大類：求解線性方程組的數(shù)值方法可分為兩大類：直接直接方法方法和和迭代方法迭代方法。本章討論直接方法，迭代方法將在。本章討論直接方法，迭代方法將在下一章中討論。下一章中討論。 需要指出，由于實(shí)際計(jì)算中舍入誤差的存在，用需要指出，由于實(shí)際計(jì)算中舍入誤差的存在，用直接方法一般也只能求得方程組的近似值。本章我直接方法一般也只能求得方程組的近似值。本章我們將給出直接解法的若干算法。們將給出直接解法的若干算法。1 Gauss消去法消去法 GaussGauss（高斯）消去法是一種規(guī)則化的加減消元法。（高斯）消去法

5、是一種規(guī)則化的加減消元法。 基基 本本 思思 想想 通過逐次消元計(jì)算把需求解的線性方程組轉(zhuǎn)化成通過逐次消元計(jì)算把需求解的線性方程組轉(zhuǎn)化成上三角形方程組，也就是把線性方程組的系數(shù)矩陣轉(zhuǎn)上三角形方程組，也就是把線性方程組的系數(shù)矩陣轉(zhuǎn)化為上三角矩陣，從而使一般線性方程組的求解轉(zhuǎn)化化為上三角矩陣，從而使一般線性方程組的求解轉(zhuǎn)化為等價(jià)（同解）的上三角形方程組的求解。為等價(jià)（同解）的上三角形方程組的求解。 Gauss Gauss消去法由消元和回代兩個過程組成，先討論消去法由消元和回代兩個過程組成，先討論一個具體的線性方程組的一個具體的線性方程組的求解。求解。 一、順序一、順序Gauss消去法消去法 152

6、33322242321321321xxxxxxxxx 48822422423232321xxxxxxx 8122242242332321xxxxxx323 x612 x321 x 188022402242 152333212242,bA 81200224022423/ 2, 6/ 1, 32123 xxx例例1. 用用Gauss消去法解方程組消去法解方程組用增廣矩陣進(jìn)行進(jìn)算用增廣矩陣進(jìn)行進(jìn)算這樣，對于方程組這樣，對于方程組 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(5.1)(5.1)我們用增廣矩陣表示，并給出我們用增廣矩陣表示，并給

7、出gauss消去法的具體算法消去法的具體算法 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabAbAbAx 或者或者 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabAbA順序順序Gauss消去法的消

8、元過程可表述如下：消去法的消元過程可表述如下： 第一步第一步，設(shè)，設(shè) ，將第一列以下各元素消成零，將第一列以下各元素消成零，0)1(11 a乘以矩陣乘以矩陣A（1），b（1）的第的第一行加到第一行加到第i i 行，得到行，得到矩陣矩陣 (i2，3，n)1(11)1(11aalii 即依次用即依次用其中其中 niblbbnjialaaiiijiijij,3,2,3,2,)1(11)1()2()1(11)1()2( 第二步第二步，設(shè)設(shè) ,將第一列將第一列 以下各元素消成零，以下各元素消成零，0)2(22 a)2(22a)2(22)2(22aalii （i3，4，n） 即依次用即依次用的第二行加到第

9、的第二行加到第i行，得到矩陣乘以矩陣行，得到矩陣乘以矩陣A（2），b（2） )2()2()2(3)2(2)2(3)2(3)2(33)2(32)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)2()2(000,nnnnnnnnbaaabaaabaaabaaaabAniblbbnjialaaiiijiijij, 4 , 3, 4 , 3,)2(22)2()3()2(22)2()3( 其中其中 如此繼續(xù)消元下去第如此繼續(xù)消元下去第n1步結(jié)束后，得到矩陣步結(jié)束后，得到矩陣 )3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(

10、1)1(13)1(12)1(11)2()2(00000,nnnnnnnbaabaabaaabaaaabA增廣矩陣增廣矩陣A（n），b（n）對應(yīng)如下上三角形方程組對應(yīng)如下上三角形方程組 )()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa這是與原線性方程組（這是與原線性方程組（5.1）等價(jià)的方程組）等價(jià)的方程組. )()()3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)()(000000,nnnnnnnnnnbabaabaaabaaaabA對于等價(jià)方程組對于等價(jià)

11、方程組 )()()1(1)1(11)1(11)2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnnnnnnnnnnnbxabxaxabxaxabxaxaxa進(jìn)行回代求解，可以得到：進(jìn)行回代求解，可以得到：)()(nnnnnnabx nkknkkkkkkkkkknnnkxaxaxabax)(2)(21)(1)()(1 1 ,2, 1,11)()()( nkxabankjjkjkkknnn首先寫出增廣矩陣首先寫出增廣矩陣于是，采用于是，采用Gauss消去法求解方程組消去法求解方程組 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa221122222

12、12111212111(5.1)(5.1) )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabAbAnkkiblbbnkkjialaakkikkikikkjikkijkij,2,1,2,1,)()()1()()()1( 然后進(jìn)行消元，采用公式然后進(jìn)行消元，采用公式最后進(jìn)行回代得到方程組的解最后進(jìn)行回代得到方程組的解得到相似增廣矩陣得到相似增廣矩陣)()(kkkkikikaal （ik+1，k+2，n

13、） )()()3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)()(000000,nnnnnnnnnnbabaabaaabaaaabA)()(nnnnnnabx nkjjkjkkknnnkxabax1)()()(1在編程計(jì)算時(shí)，最后的增廣矩陣存放的元素是：在編程計(jì)算時(shí)，最后的增廣矩陣存放的元素是： )()(321)3(3)3(3)1(333231)2(2)2(2)2(23)2(2221)1(1)1(1)1(13)1(12)1(11nnnnnnnnnnnballlbaallbaaalbaaaa下面給出下面給出Gauss消去法的計(jì)算流程：

14、消去法的計(jì)算流程：1 ,2, 1 nk消元過程：消元過程： )()(kkkkikikaal ,)()()1(kkjikkijkijalaa jk1，n kkikkikiblbb )()1(回代過程：回代過程： 對于對于in1，n2，1，計(jì)算，計(jì)算)(1)()(iiinijjiijiiiaxabx k1，2，n1，ik1，k2，n對于對于執(zhí)行計(jì)算執(zhí)行計(jì)算)()(/nnnnnnabx 置置算法算法 Gauss(A,b,n,x) 1. 消元消元 For k=1,2, , n-1 1.1 if akk=0 , stop; 1.2 For i=k+1,k+2, , n 1.2.1 l ik=aik /a

15、kk = aik 1.2.2 For j=k+1，k+2, ,n ai j -aik ak j =aij 1.2.3 bi -aik bk= bi 2. 回代回代2.1 bn / an=xn;2.2 For i=n-1,n-2, , 2,1 2.2.1 bk = S 2.2.2 For j=k+1，k+2, ,n S akj xj =S 2.2.3 S/ akk = xk a1 1 a1 2 a13 a1 n b1a2 1 a2 2 a23 a2 n b2a3 1 a3 2 a33 a3 n b3an 1 an 2 an3 an n bnl21 l31 l41 .l n1 a22 a23 .

16、a2n b2 l32 l42 .l n2 . a33 . a 3n b3l43 .l n3 a1 1 a1 2 a13 . a1 n b1a 4n b4. . .ann bn 用用Gauss消去法解方程組，應(yīng)注意：消去法解方程組，應(yīng)注意：1. 適用條件：適用條件： 原方程組系數(shù)矩陣的各階順序主子原方程組系數(shù)矩陣的各階順序主子 式不等于零。式不等于零。2 . 運(yùn)算量小：共有乘除法次數(shù)為運(yùn)算量?。汗灿谐顺ù螖?shù)為 )3(312)1(231233nnnnnnnn 而而Gramer 法則的乘除法次數(shù)為法則的乘除法次數(shù)為: (n2 -1) n！當(dāng)當(dāng) n=20 時(shí)時(shí)202107 . 9!)1( nnN30

17、60)3(3123 nnnN二二 列主元列主元Gauss消去法消去法 順序順序Gauss消去法計(jì)算過程中的消去法計(jì)算過程中的 akk(k) 稱為主元稱為主元素，在第素，在第k步消元時(shí)要用它作除數(shù)步消元時(shí)要用它作除數(shù),則可能會出現(xiàn)以則可能會出現(xiàn)以下幾種情況下幾種情況若出現(xiàn)若出現(xiàn) 0，消元過程就不能進(jìn)行下去。，消元過程就不能進(jìn)行下去。 )(kkka 0，消去過程能夠進(jìn)行，但若消去過程能夠進(jìn)行，但若 很小，也很小，也會造成舍入誤差積累很大導(dǎo)致計(jì)算解的精度下降。會造成舍入誤差積累很大導(dǎo)致計(jì)算解的精度下降。 )(kkka)(kkka 例例5-2 在四位十進(jìn)制的限制下，試順序在四位十進(jìn)制的限制下，試順序G

18、auss消消去法求解如下方程組去法求解如下方程組 9812 . 4120032001 .1291. 58334. 06781. 0167. 001. 0012. 0321321321xxxxxxxxx此方程組具有四位有效數(shù)字的精確解為此方程組具有四位有效數(shù)字的精確解為x117.46，x245.76，x35.546 解解 用順序用順序Gauss消去法求解，消元過程如下消去法求解，消元過程如下 0 .981200. 41200320010.12910. 58334. 0000. 16781. 01670. 00100. 00120. 0 231017981044541467041.44010. 8

19、101000. 006781. 01670. 00100. 00120. 0 5531065171011750041.44010. 8101000. 006781. 01670. 00100. 00120. 0經(jīng)回代求解得經(jīng)回代求解得 x35.546，x2100.0，x1104.0和此方程組的精確解相比和此方程組的精確解相比x35.546 ，x245.76， x117.46有較大的誤差。有較大的誤差。 對于此例，由于順序?qū)τ诖死?，由于順序Gauss消去法中的消去法中的主元素絕對主元素絕對值非常小值非常小，使消元乘數(shù)絕對值非常大，計(jì)算過程中出，使消元乘數(shù)絕對值非常大，計(jì)算過程中出現(xiàn)大數(shù)吃掉小數(shù)現(xiàn)

20、象，產(chǎn)生較大的舍入誤差，最終導(dǎo)現(xiàn)大數(shù)吃掉小數(shù)現(xiàn)象，產(chǎn)生較大的舍入誤差，最終導(dǎo)致計(jì)算解致計(jì)算解 x1104.0 和和 x2100.0 已完全失真。已完全失真。 為避免這種現(xiàn)象發(fā)生，我們可以對原方程組作等為避免這種現(xiàn)象發(fā)生，我們可以對原方程組作等價(jià)變換，再利用順序價(jià)變換，再利用順序Gauss消去法求解。消去法求解。 0 .981200. 41200320010.12910. 58334. 0000. 16781. 01670. 00100. 00120. 0 6781. 01670. 00100. 00120. 010.12910. 58334. 0000. 10 .981200. 4120032

21、00寫出原方程組的增廣矩陣：寫出原方程組的增廣矩陣：針對第一列找出絕對值最大的元素，進(jìn)行等價(jià)變換：針對第一列找出絕對值最大的元素，進(jìn)行等價(jià)變換： 644. 01670. 0105500. 0079.11909. 54584. 000 .981200. 4120032002 5329. 00961. 00079.11909. 54584. 000 .981200. 412003200求得方程的解為：求得方程的解為：x35.546，x245.76，x117.46精確解為：精確解為： x35.546 ，x245.76， x117.46 由此可見，第二種由此可見，第二種Gauss消去法的精度明顯高于順

22、消去法的精度明顯高于順序序Gauss消去法，我們稱它為消去法，我們稱它為列主元列主元Gauss消去法消去法。 列主元列主元Gauss消去法與順序消去法與順序Gauss消去法的不同之消去法的不同之處在于：處在于： 后者是按自然順序取主元素進(jìn)行消元后者是按自然順序取主元素進(jìn)行消元 前者在每步消元之前先選取主元素然后再進(jìn)行消元前者在每步消元之前先選取主元素然后再進(jìn)行消元 下面將列主元下面將列主元Gauss消去法的計(jì)算步驟敘述如下：消去法的計(jì)算步驟敘述如下： 給定線性方程組給定線性方程組 Axb, 記記A（1）, b（1） A,b，列主元列主元Gauss消去法的具體過程如下：消去法的具體過程如下： 1

23、. 首先在增廣矩陣首先在增廣矩陣A（1）,b（1）第一列的第一列的n個元素中個元素中選取絕對值最大的一個作為主元素，并把此主元素選取絕對值最大的一個作為主元素，并把此主元素所在的行與第一行交換，即所在的行與第一行交換，即,max)1(11)1(1inikaa 2. 其次進(jìn)行第一步消元得到增廣矩陣其次進(jìn)行第一步消元得到增廣矩陣A（2）,b（2），在矩陣在矩陣A（2）,b（2） 第一列的后第一列的后 n1個元素中選取絕個元素中選取絕對值最大的一個作為主元素，并把此主元素所在的行對值最大的一個作為主元素，并把此主元素所在的行與第二行交換，即與第二行交換，即,max)2(22)2(2inikaa )1

24、(1)1()1(1)1(,bbaakjkj)2(2)2()2(2)2(,bbaakjkj 3. 再進(jìn)行第二步消元得到增廣矩陣再進(jìn)行第二步消元得到增廣矩陣A（3），b（3）。按此方法繼續(xù)進(jìn)行下去，經(jīng)過按此方法繼續(xù)進(jìn)行下去，經(jīng)過n1步選主元和消元運(yùn)步選主元和消元運(yùn)算，得到增廣矩陣算，得到增廣矩陣A（n），b（n），它對應(yīng)的方程組，它對應(yīng)的方程組A（n）xb（n）是一個與原方程組等價(jià)的上三角形方程組，可進(jìn)行是一個與原方程組等價(jià)的上三角形方程組，可進(jìn)行回代求解。回代求解。 容易證明，只要容易證明，只要det（A）0，列主元，列主元Gauss消去消去法就可以順利完成，即不會出現(xiàn)主元素為零或者絕法就可以順

25、利完成，即不會出現(xiàn)主元素為零或者絕對值太小的情形出現(xiàn)。對值太小的情形出現(xiàn)。 下面給出列主元下面給出列主元Gauss消去法的計(jì)算流程：消去法的計(jì)算流程：列主元列主元Gauss消去算法消去算法 用列主元用列主元Gauss消去法求解線性方程組消去法求解線性方程組Axb 輸入輸入 A（aij），），b（b1，bn）T，維數(shù)，維數(shù)n輸出輸出 方程組解方程組解x1，xn，或方程組無解信息，或方程組無解信息1： 對于對于k1，2，n1，循環(huán)執(zhí)行步，循環(huán)執(zhí)行步2到步到步52： 按列選主元素按列選主元素 aik ，即確定下標(biāo)，即確定下標(biāo) I 使使jknjkikaa max3： 若若aik0，輸出，輸出 no u

26、nique solution，停機(jī)，停機(jī)nkjaaijkj, ikbb4： 若若ik，換行，換行5： 消元計(jì)算，對于消元計(jì)算，對于ik1，n，計(jì)算，計(jì)算 kkikikaal/nkjalaakjikikik, 1, kikiiblbb 6：若：若 ann 0輸出輸出 no unigue solation，停機(jī)，停機(jī)7： 回代求解回代求解 nnnnabx/1 ,2 , 1,11 nixabiaxnijjijiii8： 輸出輸出 x1，x2，xn 由于這兩種方法的精度差不多，且全主元由于這兩種方法的精度差不多，且全主元Gauss消去法程序設(shè)計(jì)復(fù)雜占用機(jī)器時(shí)間較多，實(shí)際應(yīng)用消去法程序設(shè)計(jì)復(fù)雜占用機(jī)器時(shí)

27、間較多，實(shí)際應(yīng)用中一般采用列主元中一般采用列主元Gauss消去法，它既簡單又能保證消去法，它既簡單又能保證計(jì)算精度。計(jì)算精度。 有時(shí)候在消元過程中可以在系數(shù)矩陣所有元素中有時(shí)候在消元過程中可以在系數(shù)矩陣所有元素中選擇絕對值最大的元素作為主元素，這樣的選擇絕對值最大的元素作為主元素，這樣的Gauss消消去法去法和叫做和叫做全主元全主元Gauss消去法消去法。 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaaba

28、aaabA2 2 直接三角分解方法直接三角分解方法一一 、 Gauss消去法的矩陣運(yùn)算消去法的矩陣運(yùn)算 從從1中討論可知，順序中討論可知，順序Gauss消去法的消元過程消去法的消元過程是將增廣矩陣是將增廣矩陣A，bA（1），b（1）逐步約化為矩陣逐步約化為矩陣A（n），b（n）。 現(xiàn)在說明，在消元過程中，系數(shù)矩陣現(xiàn)在說明，在消元過程中，系數(shù)矩陣AA（1）是是如何經(jīng)矩陣運(yùn)算約化為上三角矩陣如何經(jīng)矩陣運(yùn)算約化為上三角矩陣A（n）。即。即 用矩陣運(yùn)算的觀點(diǎn)來看，用矩陣運(yùn)算的觀點(diǎn)來看，消元的每一步計(jì)算等價(jià)消元的每一步計(jì)算等價(jià)于用一個單位下三角矩陣左乘前一步約化得到的矩陣。于用一個單位下三角矩陣左乘前一

29、步約化得到的矩陣。 )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nnnnnnaaaaaaaaaA )1()1(2)1(22)1(1)1(12)1(11)(000nnnnnaaaaaaA? )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nnnnnnaaaaaaaaaA若若 ，令，令 ，i2，3，n，0)1(11 a)1(11)1(11/aalii 得到下三角矩陣得到下三角矩陣 1001011131211nlllL施行第一步消元，我們得到施行第一步消元，我們得到 )2()2(2)2(2)2(22)1(1)1(12)1(1

30、1)1(1)2(00nnnnnaaaaaaaALA若若 ，令，令 ，i2，3，n，則有，則有 0)2(22 a)2(22)2(22/aalii 10101012322nllL施行第二步消元，我們得到施行第二步消元，我們得到 )3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)2(2)3(00000nnnnnnaaaaaaaaaaaALA如此下去，施行第如此下去，施行第n1步消元，得到步消元，得到 )2()2(2)2(22)1(1)1(12)1(11)1(1)(nnnnnnnaaaaaaALA 由此可見，在順序由此可見，在順序Gauss消去法的過程

31、中，系數(shù)矩消去法的過程中，系數(shù)矩陣陣AA（1）經(jīng)過一系列單位下三角矩陣的經(jīng)過一系列單位下三角矩陣的左乘運(yùn)算左乘運(yùn)算約約化為上三角矩陣化為上三角矩陣A（n），即，即 )1(1)( nnnALA這時(shí)這時(shí))2(21 nnnALLALLLLnn1221 )(111211nnALLLA 11111nkkkkllL由由 111111nkkkkllL得得)(111211,nnAULLLL 令令容易驗(yàn)證容易驗(yàn)證 1111121323121111211nnnnnllllllLLLL 則從順序則從順序Gauss消去法的矩陣運(yùn)算表示式可知，系消去法的矩陣運(yùn)算表示式可知，系數(shù)矩陣數(shù)矩陣A可分解為一個單位下三角矩陣可分

32、解為一個單位下三角矩陣L和一個上三角和一個上三角矩陣矩陣U的乘積，即的乘積，即LUALLLAnn )(111211 )2()2(2)2(22)1(1)1(12)1(11)(nnnnnaaaaaaAU其中其中 nnnnuuuuuu22211211第一個方程組的系數(shù)矩陣為下三角矩陣，第二個方程第一個方程組的系數(shù)矩陣為下三角矩陣，第二個方程組的系數(shù)矩陣為上三角矩陣，兩個方程組都非常容易組的系數(shù)矩陣為上三角矩陣，兩個方程組都非常容易求解，具體求解結(jié)果如下：求解，具體求解結(jié)果如下：我們將我們將稱為稱為矩陣矩陣A的三角分解的三角分解LUA 這時(shí)線性方程組：這時(shí)線性方程組：bAX bLUX 令令YUX 則有

33、則有 YUXbLYbLY 對于對于 nnnnnnbbbbyyyyllllll3213211213231211111由由 nkylbybykiikikk, 3 , 2,1111解得解得YUX 對于對于 nnnnnnyyyxxxuuuuuu212122211211由由 1 , 2, 1,/1nniuxuyxuyxiinijjijiinnnn求得求得bAX 可以看出對于方程組可以看出對于方程組： 只要對系數(shù)矩陣作了三角分解：只要對系數(shù)矩陣作了三角分解： LUA 由這個簡單的計(jì)算過程可知，系數(shù)矩陣的三角分解很由這個簡單的計(jì)算過程可知，系數(shù)矩陣的三角分解很關(guān)鍵，如何進(jìn)行三角分解更容易？下面介紹幾種方法。

34、關(guān)鍵，如何進(jìn)行三角分解更容易？下面介紹幾種方法。 nkylbybykiikikk,3,2,1111 1 , 2, 1,/1nniuxuyxuyxiinijjijiinnnn通過如下兩組公式很容易求解通過如下兩組公式很容易求解： 二、二、 Doolittle分解法分解法 前已述及，若在順序前已述及，若在順序Gauss消去法的過程中，每消去法的過程中，每步消元的主元素步消元的主元素 akk(k)0，則矩陣，則矩陣A可分解為可分解為ALU，L為單位下三角矩陣，為單位下三角矩陣，U為上三角矩陣，此分解稱為為上三角矩陣，此分解稱為A的的 Doolittle（杜利特爾）分解杜利特爾）分解。可以證明?？梢宰C

35、明akk(k) 0的的充要條件是充要條件是A的各階順序主子式不為零，于是有如下的各階順序主子式不為零，于是有如下定理。定理。 定理定理5.1 設(shè)設(shè)n階方陣階方陣A的各階順序主子式不為零，的各階順序主子式不為零，則存在惟一單位下三角矩陣則存在惟一單位下三角矩陣L和上三角矩陣和上三角矩陣U使使ALU。下面介紹矩陣三角分解的下面介紹矩陣三角分解的Doolittle分解方法。分解方法。LUA nnnnnnaaaaaaaaa212222111211 nnnnuuuuuu22211211 1111321323121nnnllllll根據(jù)根據(jù)LUA 有等式成立：有等式成立：比較等式兩端對應(yīng)元素，有比較等式兩

36、端對應(yīng)元素，有 ija)001(121 i iiilll 00121jjjjjjuuuu ija)001(121 i iiilll 00121jjjjjjuuuujijii ijijiuululul 112211ji ji jjijjjijjijiulululul 112211 nnii可以解得：可以解得：,11jjau ,1111ualii 當(dāng)當(dāng) i=1 時(shí)時(shí) 當(dāng)當(dāng) j=1 時(shí)時(shí) nj, 2 , 1 ni, 3 , 2 當(dāng)當(dāng) i 1 時(shí)時(shí) niij, 1, 11ikkjikijijulau當(dāng)當(dāng) j 1 時(shí)時(shí) njji, 2, 1 jiululululjiuulululajjijjjijjij

37、iijjiiijijiij112211112211jjjkkjikijijuulal/ )(11 于是，對于矩陣的三角分解：于是，對于矩陣的三角分解：可按照以下公式進(jìn)行：可按照以下公式進(jìn)行： niualnjauiijj,3,2,/,2,1,111111 nnnnnnaaaaaaaaa212222111211 nnnnuuuuuu22211211 1111321323121nnnllllll nikulaulniijulauimmikmkiiikiimmjimijij,1),(1,1,1111對于對于 i=2,3, ，n, 計(jì)算計(jì)算（5.2）（5.3）（5.4）用計(jì)算公式用計(jì)算公式(5.3)、(

38、5.4)對矩陣對矩陣A作的分解作的分解(5.2),稱作稱作Doolittle分解。分解。 nnnnnnaaaaaaaaa212222111211 nnnnuuuuuu22211211 1111321323121nnnllllll下面，我們對具體矩陣進(jìn)行下面，我們對具體矩陣進(jìn)行Doolittle 三角分解。三角分解。為了表示和存儲方便，可以將分解后的兩個矩陣用一為了表示和存儲方便，可以將分解后的兩個矩陣用一個矩陣表示個矩陣表示 nnnnnnaaaaaaaaa212222111211 nnnnnnulluuluuu212222111211例例5-3 利用利用Doolittle三角分解法分解矩陣三角

39、分解法分解矩陣解：分解時(shí)用到如下公式解：分解時(shí)用到如下公式 niualnjauiijj,3,2,/,2,1,111111 25681161642781169414321A 1234111261237624624 11ikkjikijijulauniij, 1, njji, 2, 1 jjjkkjikijijuulal/ )(11 25681161642781169414321A 1234111261237624624可以寫成：可以寫成：這時(shí)，矩陣的三角分解這時(shí)，矩陣的三角分解 25681161642781169414321A 25681161642781169414321A 167101310

40、0110001 2400024600126204321如果我們要求解方程組如果我們要求解方程組 19044102256811616427811694143214321xxxx則由則由 25681161642781169414321 1671013100110001 2400024600126204321得到得到 1904410216710131001100014321yyyy 432143212400024600126204321yyyyxxxx由由 1904410216710131001100014321yyyy解得解得 2418824321yyyy再由再由 4321432124000246

41、00126204321yyyyxxxx 24188224000246001262043214321xxxx求得方程組的解：求得方程組的解：14 x13 x12 x11 x 1 ,2, 1,/,3,2,11111nniuxuyxuyxnkylbybyiinijjijiinnnnkiikikk（5.5） 如下的計(jì)算公式如下的計(jì)算公式(5.3)、(5.4)與與(5.5)就是求解方程組就是求解方程組Axb 的的 Doolittle 三角分解方法三角分解方法,包括分解和回代兩步包括分解和回代兩步。 niualnjauiijj,3,2,/,2,1,111111（5.3） nikulaulniijulaui

42、mmikmkiiikiimmjimijij,1),(1,1,1111（5.4）關(guān)于具體求解過程可以按下面例子的方法進(jìn)行。關(guān)于具體求解過程可以按下面例子的方法進(jìn)行。 例例5-4 利用利用Doolittle三角分解方法解線性方程三角分解方法解線性方程 105201021243321321xxx解解: 進(jìn)行三角分解進(jìn)行三角分解ALU，按照公式按照公式(5.5)可以對增廣可以對增廣 矩陣矩陣A,b作三角分解作三角分解: 100102512432321 1 2 3 -2-3 2 2 -3-13317 1712300320321321xxx得到得到,3173 x 100102512432321 1 2 3

43、 -2-3 2 2 -3-13317這時(shí)，相應(yīng)的方程組為：這時(shí)，相應(yīng)的方程組為：x135x28，例例5-5 利用利用Doolittle三角分解方法解線性方程組三角分解方法解線性方程組 710521391443010213124343214321xxxx解：解：對增廣矩陣進(jìn)行三角分解對增廣矩陣進(jìn)行三角分解 71391441030102513124324321 1 2 3 -4 -2-3 2 42-3133322-4-117-16等價(jià)方程組通過分解式容易寫出為：等價(jià)方程組通過分解式容易寫出為： 1 2 3 -4 -2-3 2 42-3133322-4-117-16 1617124000230013

44、2043214321xxxx解得解得, 44 x, 33 x, 22 x, 11 x三、平方根法三、平方根法 在實(shí)際應(yīng)用中，常見一類非常重要的線性方程組在實(shí)際應(yīng)用中，常見一類非常重要的線性方程組Axb，其中，其中A為對稱正定矩陣，即為對稱正定矩陣，即A是對稱的且對是對稱的且對任何非零向量任何非零向量 x 都有都有xTAx0。本節(jié)將對這類方程組。本節(jié)將對這類方程組導(dǎo)出更有效地三角分解求解方法，稱之為導(dǎo)出更有效地三角分解求解方法，稱之為平方根法。平方根法。 設(shè)設(shè)A為對稱正定矩陣，那么為對稱正定矩陣，那么A的所有順序主子式的所有順序主子式均大于零，根據(jù)定理均大于零，根據(jù)定理5.1，存在惟一三角分解，

45、存在惟一三角分解ALU，即，即 nnnnnnnnnuuuuuuuuuullllllA3332232211312111213231211111 nnnnnnnnnuuuuuuuuuullllllA3332232211312111213231211111 記記 Ak（1kn）為）為A的的 k 階順序主子陣，則階順序主子陣，則det（Ak）為）為A的的k階順序主子式。由上式，利用矩陣分階順序主子式。由上式，利用矩陣分塊運(yùn)算規(guī)則，容易驗(yàn)證塊運(yùn)算規(guī)則，容易驗(yàn)證 det（Ak）u11 u22 ukk那么由那么由 det（Ak）0，可知，可知 ukk0，k1，2，n 這時(shí)，將上面的矩陣表示為：這時(shí)，將上面的

46、矩陣表示為： nnnnnnnnnuuuuuuuuuullllllA3332232211312111213231211111 1111111133322222311111131112332211121323121uuuuuuuuuuuunnnnnnnnnuuuullllllLDM 即：即： A=LDM ，其中其中 DM=U， M=D-1U。當(dāng)當(dāng)AAT為對稱矩陣時(shí)，根據(jù)為對稱矩陣時(shí)，根據(jù) ALDM, 得到得到ATMT D LT再根據(jù)矩陣三角分解的唯一性再根據(jù)矩陣三角分解的唯一性,可知可知 MLT。于是。于是ALDLT則有則有TLDLDA2121 ),diag(221121nnuuuD 21LDG

47、令令TLDLD)(2121 TGG nnnnnnnnnnngggggggggggggggggggg333223221131211121333231222111 如果對稱正定矩陣如果對稱正定矩陣A具有如下分解具有如下分解 AGGT，其中其中G為下三角矩陣，則稱其為對稱正定矩陣的為下三角矩陣，則稱其為對稱正定矩陣的 Cholesky（喬列斯基）分解。（喬列斯基）分解。 為表示方便，可以為表示方便，可以記記TLLA nnnnnnnnnnnllllllllllllllllllll333223221131211121333231222111 給定對稱正定方程組給定對稱正定方程組 Axb，對，對 A 進(jìn)行

48、進(jìn)行 Cholesky分解分解ALLT，則原方程組等價(jià)于，則原方程組等價(jià)于 LLTxbLyb LTx y解此方程組即可得到原方程組的解解此方程組即可得到原方程組的解x ，這就是求解方這就是求解方程組的平方根法。程組的平方根法。 下面，我們通過比較矩陣的對應(yīng)元素給出對稱正下面，我們通過比較矩陣的對應(yīng)元素給出對稱正定矩陣的平方根分解法。已知定矩陣的平方根分解法。已知即：即： LLTxb，等價(jià)于等價(jià)于 nnnnnnnnnnnllllllllllllllllllll333223221131211121333231222111 nnnnnnaaaaaaaaa212222111211 ija比較對應(yīng)元素：

49、比較對應(yīng)元素： nnnnnnnnnnnllllllllllllllllllll333223221131211121333231222111 nnnnnnaaaaaaaaa212222111211 0021jjjjlll 0, 0,21iiiilll ija當(dāng)當(dāng) i = j時(shí)時(shí) 0021jjjjlll 0, 0,21iiiilll22221jjjjjjllla 當(dāng)當(dāng) j i 時(shí)時(shí)jjijjijiijlllllla 2211解得解得njlaljkjkjjjj, 2 , 1,)(21112 njjilllaljjjkjkikijij, 1,/ )(11 于是，根據(jù)計(jì)算公式于是，根據(jù)計(jì)算公式njlal

50、jkjkjjjj, 2 , 1,)(21112 njjilllaljjjkjkikijij, 1,/ )(11 可以對對稱正定矩陣進(jìn)行平方根分解可以對對稱正定矩陣進(jìn)行平方根分解 nnnnnnaaaaaaaaa212222111211l11 l22 l33 lnn l21 l31 ln1 l32 ln2 ln3 nnnnnllllllllll333232221312111 關(guān)于方程組關(guān)于方程組 Ax=b , 如果對系數(shù)矩陣進(jìn)行了平方根分如果對系數(shù)矩陣進(jìn)行了平方根分解解 ALLT，則將方程組化為：，則將方程組化為： Lyb , LTxynjlylbyjjjkkjkjj,2 , 1,11 1 , 1

51、,1 nnjlylyxjjnjkkkjjj nnnnnnnbbbbyyyyllllllllll321321321333231222111 nnnnnnnyyyyxxxxllllllllll321321333232221312111解得解得 于是，關(guān)于系數(shù)矩陣是對稱正定矩陣的線性方程于是，關(guān)于系數(shù)矩陣是對稱正定矩陣的線性方程組組Ax=b的求解，分兩步進(jìn)行：的求解，分兩步進(jìn)行：第一步：系數(shù)矩陣的平方根分解第一步：系數(shù)矩陣的平方根分解njlaljkjkjjjj, 2 , 1,)(21112 njjilllaljjjkjkikijij, 1,/ )(11 第二步：解等價(jià)方程組第二步：解等價(jià)方程組njl

52、ylbyjjjkkjkjj,2 , 1,11 1 , 1,1 nnjlylyxjjnjkkkjjj例例5-6 用平方根法求解對稱正定方程組用平方根法求解對稱正定方程組 25. 7645 . 375. 2175. 225. 41114321xxx解解: 首先進(jìn)行首先進(jìn)行A 的的Cholesky 分解分解 ALLTnjlaljkjkjjjj, 2 , 1,)(21112 njjilllaljjjkjkikijij, 1,/ )(11 2-0.50.521.51 2 -0.5 0.521.51得得 y12，y23.5 ，y31 得得 x11，x21，x31 25. 76415 . 15 . 0025

53、 . 0002321yyy 15 . 321005 . 1205 . 05 . 02321xxx求解求解Lyb:再求解再求解 LTxy: 25. 7645 . 375. 2175. 225. 41114321xxx關(guān)于對稱正定方程組關(guān)于對稱正定方程組 也可以用一般的三角分解法求解，這時(shí)由也可以用一般的三角分解法求解，這時(shí)由 4 -1 1 4-0.250.254370.7511求得求得 x11，x21，x31 25. 75 . 375. 21675. 225. 414114四、追趕法四、追趕法 追趕法是專門用于求解三對角方程組的。這類追趕法是專門用于求解三對角方程組的。這類方程組經(jīng)常出現(xiàn)于用差分

54、方法或有限元方法求解二方程組經(jīng)常出現(xiàn)于用差分方法或有限元方法求解二階常微分方程邊值問題、熱傳導(dǎo)問題及三次樣條函階常微分方程邊值問題、熱傳導(dǎo)問題及三次樣條函數(shù)插值等問題，三對角方程組數(shù)插值等問題，三對角方程組Axb的系數(shù)矩陣具的系數(shù)矩陣具有如下形式：有如下形式： nnnbacbacbacbA13322211 設(shè)設(shè)A為一個三對角矩陣，那么它的順序主子式均不為一個三對角矩陣，那么它的順序主子式均不為零的一個充分條件是：為零的一個充分條件是： 1, 2, 0|,|0| , 0|11 niacacbabcbiiiiinn在此條件下，可對在此條件下，可對A進(jìn)行三角分解，設(shè)進(jìn)行三角分解，設(shè) 11112133

55、221nnnA 比較矩陣的對應(yīng)元素，根據(jù)矩陣乘法規(guī)則，可得到比較矩陣的對應(yīng)元素，根據(jù)矩陣乘法規(guī)則，可得到 1i iiac 0 , 0 , 0 , 0ii 00100i i-1列列i 行行 11112133221nnn nnnbacbacbacb13322211第第3列列1, 2 , 1, niii i iiab 0 , 0 , 0 , 0ii 001001i i-1列列i -1行行niiii, 2 , 1,1 11112133221nnn nnnbacbacbacb13322211第第3列列 1i iiaa 0 , 0 , 0 , 0ii i-1列列nii, 3 , 2, 1111213322

56、1nnn nnnbacbacbacb13322211第第3列列 001002i i -1行行i-1列列于是，由以上結(jié)果：于是，由以上結(jié)果：niaii, 3 , 2, niciii,2, 1, nibiiii, 2 , 1,1 分別得到：分別得到：niaii,3,2, 11b nibiiii, 3 , 2,1 1,2, 1, niciii 也就是說，用這一組公式可以對三對角矩陣進(jìn)行三也就是說，用這一組公式可以對三對角矩陣進(jìn)行三角分解：角分解： 11112133221nnn nnnbacbacbacb13322211niaii,3,2, 11b nibiiii, 3 , 2,1 1,2, 1, n

57、iciii 對于三對角方程組對于三對角方程組Axb，設(shè)，設(shè)A的三角分解為的三角分解為ALU，則原方程組等價(jià)于則原方程組等價(jià)于Lyb，Uxy 由由Lyb，即即 nnnnbbbbyyyy32132133221 解得解得niybybyiiiii, 2,/ )(/1111 1 , 1,1 nixyxyxiiiinn nnnyyyyxxxx321321121111 解得解得由由Uxy，即即于是，對于三對角矩陣方程組于是，對于三對角矩陣方程組 Ax=b，如下的兩組公如下的兩組公式便構(gòu)成了式便構(gòu)成了構(gòu)成了解三對角方程組的構(gòu)成了解三對角方程組的追趕法：追趕法：niaii,3,2, 11b nibiiii, 3

58、 , 2,1 1,2, 1, niciii 1 , 1, 2,/ )(,/11111nixyxyxniybybyiiiinniiiii 例例5-7 用追趕法求解三對角方程組用追趕法求解三對角方程組 100121001210012100124322xxxx解解 : 首先進(jìn)行系數(shù)矩陣的三角分解首先進(jìn)行系數(shù)矩陣的三角分解 11112133221nnn nnnbacbacbacb13322211 4510003410002310002niaii,3,2, 11b nibiiii, 3 , 2,1 1,2, 1, niciii 1000431000321000211 2100121001210012求解方程組求解方程組Lyy，即，即 得得 到到 y11/2，y21/3，y31/4，y41 再求解方程組再求解方程組 Uxy，即，即 得得 到到 x11，x21，x31，x41 100145100034100023100024321yyyy 110004310003210002114131214321xxxx 當(dāng)三