第五章線性方程組的直接方法

1、第五章方程組的數(shù)值解法§5.1引言在工程技術(shù)、自然科學(xué)和科學(xué)中，經(jīng)常遇到的許多問題最終都可歸結(jié)為解線性方程組，如電學(xué)中網(wǎng)絡(luò)問題、用最小二乘法求實(shí)驗(yàn)數(shù)據(jù)的曲線擬合問題，工程中的三次樣條函數(shù)的插值問題，機(jī)械與運(yùn)行中的投入產(chǎn)出問題以及大地測(cè)量、結(jié)構(gòu)的設(shè)計(jì)計(jì)算問題等等，都?xì)w結(jié)為求解線性方程組或非線性方程組的數(shù)學(xué)問題。因此線性方程組的求解對(duì)于實(shí)際問題是極其重要的。解線性方程組的直接法常見的線性方程組是方程個(gè)數(shù)和未知量個(gè)數(shù)相同的n階線性方程組，一般形式為+ a12 x2 + . + a1n xn = b1ìa11 x1ïax + ax+ . + ax= bï( 6.

2、1 )2112222nn2í.ïïîan1 x1+ an2 x2 + . + ann xn = bn簡(jiǎn)記為Ax=b，其中éa11a12 .a1nùúé x1ùéb1ùêaê x úêb úa.aA = êú, X= ê2 ú, B = ê2 ú21222nê.úê. úê x úê. úê

3、b úêaúnn ûa.aëën ûë n ûn1n2線性方程組的數(shù)值解法一般有兩類：1. 直接法：就是經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組精確解的方法（若計(jì)算過程中沒有舍入誤差），如克萊姆法則就是一種直接法， 直接法中具有代表性的算法是高斯(Gauss)消去法。2. 迭代法:就是用某種極限過程去逐步逼近線性方程組的精確解的方法。也就是從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。(一般有限步內(nèi)得不到精確解)三、特殊矩陣1)2)3)4)5)6)7)8)9)對(duì)角矩陣三對(duì)角矩陣上三角矩陣上海森伯(

4、Hessenberg)陣對(duì)稱矩陣埃爾米特矩陣對(duì)稱正定矩陣正交矩陣酉矩陣10) 初等置換陣11) 置換陣定理1 設(shè)ARnn, A非奇異?定理2 若ARnn對(duì)稱正定矩陣，則?定理3 若ARnn對(duì)稱矩陣，則對(duì)稱正定矩陣<=?定理4(若當(dāng)éJ1ê)éliê 10li10000 ùLLLLLùú0 úJêJ =0ú0P-1AP = J = êú,2êúú其中.êúúiOêêêLê&

5、#235; 0LúJës ûl úû01iki ´ki對(duì)角化的條件：1）；2） .§ 5.2高斯消去法5.2.1高斯消去法的基本思想先用一個(gè)簡(jiǎn)單實(shí)例來說明Gauss法的基本思想例5.1解線性方程組ìï4íïî解:該方程組的求解過程實(shí)際上是將中學(xué)學(xué)過的消元法標(biāo)準(zhǔn)化,將一個(gè)方程乘或除以某個(gè)常數(shù),然后將兩個(gè)方程相加減,逐步減少方程中的未知數(shù),最終使每個(gè)方程只含有一個(gè)未知數(shù),從而得出所求的解。整個(gè)過程分為消元和回代兩個(gè)部分。（1）消元過程第1步:將方程乘上(-2)加到方程上去,將&#

6、230;1ö方程乘上加到方程上去,這樣就消去-ç2 ÷èø了第2、3個(gè)方程的組ìx1項(xiàng),于是就得到等價(jià)方程ï2= 1= 23ï4x- xíï235313ïx2-x3=î222（2）回代過程回代過程是將上述三角形方程組自下而上求解，從而求得原方程組的解：= -63ìï2= 13ïíïïî-7=4 xx22321-x384這樣，消元過程就是把原方程組化為上三角形方程組，其系數(shù)矩陣是上三角矩陣。前述的消元過程相當(dāng)

7、于對(duì)原方程組- 122é23ùé x1ùé1ùê45úêxú = ê4úêêë1ú0úûêúúûêúêë7úû2êë x3的增廣矩陣進(jìn)行下列變換( ri 表示增廣矩陣的第 i 行）-122éêêêêëé 21 ù

8、0;350200A = Ab= ê 4êr2 +(-2)r14 ú7 úû¾¾1r3 +(- 2 )êë 1é-140200r +(- 5 )rê32同樣可得到與原方程組等價(jià)的方程組 8¾ ® êêêë通常把按照先消元,后回代兩個(gè)步驟求解線性方程組的方法稱為高斯（Gauss）消去法。陣行的初等變換將原方程組系數(shù)矩陣化為上三角形矩陣,而以上三角形矩陣為系數(shù)的方程組的求解比較簡(jiǎn)單,可以從最后一個(gè)方程開始,依次向前代入求出未知變量這

9、種求解上三角方程組的1方法稱為回代, 通過一個(gè)方程乘或除以某個(gè)常數(shù),以及將兩個(gè)方程相加減,逐步減少方程中的變?cè)獢?shù),最 終將方程組化成上三角方程組,一般將這一過程稱為消元,然后再回代求解。5.2.2高斯消去法算法構(gòu)造我們知道,線性方程組(6.1)用矩陣形式表示為éx1ùéb1ùéa11ùa12 a22Ma1nLLêa21a2n úêx ú2êb ú2êúúêú = êú( 6.3 )êMú

10、êMúêMMêaúêx úêúaaëbn ûLënn ûën ûn1n 2解線性方程組（6.1）的高斯（Gauss）消去法的消元過程就是對(duì)( 6.3 )的增廣矩陣進(jìn)行行初等變換。將例n ´ n6.1中解三階線性方程組的消去法推廣到一般的階線性方程組并記= a= b (i, j = 1,2,L, n)a(1),b(1)ijijii則高斯消去法的算法構(gòu)造歸納為： 消元過程,斯消去法的消元過程由n-1步組成：¹ 0a(1)第1步 設(shè)

11、,把(6.3)中的第一列中元素11a(1)消為零,令(1)21(1)31(1)n1m=(i = 2,3,L, n)a, a,L, a i1 ,i1a(1)11用- mi1 乘以第1個(gè)方程后加到第i 個(gè)方程上去,消去x1第2n個(gè)方程的未知數(shù),得到A(2) x = b(2)即éa (1)ùé x1éb(1)ùúúùa (1)a (1)LL11121n1êêêêëúêêúa (2)a (2)x2b(2)úê

12、50; = ê22M2nM(2)nn2úê M úêúMúê(2) úêúa (2)xaëbnûLûën ûn 2ìa ( 2)=- ma (1)a (1)ijiji11 jíî其中- mb ( 2)b (1)b (1)iii11j =i,2,3L, nìa (k +1)= a (k )- ma (k )A(k ) x = b(k )記為其中ijijikkjíb(k +1)= b(k )

13、- mb(k )îia(k )iikk=ik(i = k +1,L, n)miki, j = k + 1L, na(k )kkéa (1)ù xéb(1) ùéùúa (1)(1)aLLO111121n1êêêêêêêúêêúúa (2)a (2)x2b(2)úêêú222nM(k )knM(k )nn2úê M ú = 

14、34;úMúê(k ) úêúa (k )xaêbkLúêúúk úkkMúê M úêMúêêúúa (k )xê bkêúúaLë n ûëûënûnk只要¹ 0 ,消元過程就可以進(jìn)行下去,直到a(k )kk經(jīng)過n-1次消元之后，消元過程結(jié)束，得到與原方程組等價(jià)的上三角形方程

15、組,記為 A(n) x = b(n)或者寫成éa(1)ù xéb(1) ùéùa(1)(1)aLLO111121n1êêêêëúêêúúúa(2)a(2)b(2)x2úêú = ê222nM(n)nn2úê M úêúMúê(n) úêúxaëbnûë n &

16、#251;û即ìa (1) x+ a(1) x+L+L+LL= b(1)(1)ax1111221nn1ï= b(2)a(2)(2)2nïxax222n2íï(6.7)ï= b(n)a (n) xî（2）回代過程nnnn就是對(duì)上三角方程組（6.7）自下而上逐步回代解方程組計(jì)算，即b(n)x= nna (n)nnnå-b(i )(i )ijaxijj =i+1x=(i = n -1,L,2,1),ia (i )ii（3）高斯消去法的計(jì)算步驟：消元過程;設(shè)計(jì)算¹ 0, 對(duì)k = 1,2,L, n -1

17、a(k )kkìa ( k )= ikïmika ( k )ïkkí( k +=- m1)a ( k )a ( k )aïijijikkjï( k +- m1)b ( k )b ( k )bîiiikkk + 1, k + 2,L, ni,j回代過程ìb ( n )= nï xïna ( n )nn ïíïnåb ( i )-a ( i )xiijjï xj =i +1=iïa ( i )îiii = n - 1, n - 2

18、,L,1(4)(5)高斯消去法流程圖，1 n33Gauss消去法計(jì)算量 消元計(jì)算: aij(k+1)= aij(k)- mik akj(k)(i,j=k+1,k+2, , n)第一 步計(jì)算乘數(shù)mik, mik=ai1/a11 (i=2,3,n)需要n-1次除法運(yùn)算,計(jì)算 aij(2）(i,j=2,3,n)需要(n-1)2次乘法運(yùn)算及(n-1)2次加減法運(yùn)算,乘除法次數(shù)：MD= n(n-1)(2n-1)/6+ n(n-1)/2=1/3 n(n2-1)加減法次數(shù)：AS= n(n-1)(2n-1)/6第k 步加減法次數(shù)乘法次數(shù)除法次數(shù)123 n-1(n-1)2(n-2)2(n-3)2 1(n-1)2

19、(n-2)2(n-3)2 1(n-1)(n-2)(n-3) 1合計(jì)n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2¹ 0, k = 1, 2,若a(k ), n，A(k)覆蓋A,.算法.kk1.消去：對(duì)于k = 1,2,L, n(1) 若akk = 0,則停止計(jì)算.(2) 對(duì)于i = k +1, n¬ aik / akk(i)mikbi ¬bi - mik × bk .(ii) 對(duì)于j = k +1, n× akj .¬ aij - mikaij2.回代：對(duì)于i = n,L,1,(1) xi ¬ bi

20、 ,(2) 對(duì)于j = i +1,L, nxi ¬ xi - aij × x j ,(3) xi ¬ xi / aii.乘除法運(yùn)算工作量n -1n -1232511(n - k)+ 2(n - k) = n+n- n消元過程乘除法次數(shù)： åå326k = 1k = 1n -1åk = 1回代過程乘除法次數(shù)：11+(n - k +1) =n(n +1)21321+ n- 3 n總的乘除法運(yùn)算次數(shù)： 3 nn -11非零次數(shù)最多為：(n - k) =n(n -1)å2k = 1n -1行交換的元素個(gè)數(shù)為： å1(n -

21、 k) =n(n -1)2k = 1ånn(n +1)(2n +1)k 2 =k =16ånn(n +1) k =k =12第k步消元：mik : n - k次除法, a(k+1) : (n - k)2次乘法,ijb(k+1) : n - k次乘法,(i, j = k + 1,L, n).i5.2.3高斯消去法的適用條件定理1方程組系數(shù)矩陣的順序主子式全不為零則高斯消去法能實(shí)現(xiàn)方程組的求解。上三角形方程組是從原方程組出發(fā)，通證明過逐次進(jìn)行“一行乘一數(shù)加到另一行”而得出的，該變換不改變系數(shù)矩陣順序主子式的值。A = (aij )n設(shè)方程組系數(shù)矩陣，其順序主子式a11Mam1a

22、1mMammLAm=¹ 0（m =1,2,，n）L經(jīng)變換得到的上三角形方程組的順序主子式a(1)a(1)a(1)LLO11121ma(2)a(2)A=¹ 0222mM(1)(2)(m)mmaaLam1122a(m)mm（m =1,2,，n） 所以能實(shí)現(xiàn)高斯消去法求解A = (aij )n定義5.1設(shè)矩陣每一行對(duì)角元素的絕對(duì)值都大于其他元素絕對(duì)值之和n> å aiji = 1,2,L, naii,j =1 j ¹i則稱A為嚴(yán)格對(duì)角占優(yōu)矩陣。若方程組 Ax = b 的系數(shù)矩陣A為定理1.1嚴(yán)格對(duì)角占優(yōu)，則用高斯消去法求解時(shí)，(k )kka全不為零。ai

23、1a1i- ai1a1i=³-a(2)aa得iiiiiia¹ 0a= aa(1)11111111nå故有aa<, = i2, ,j3=,L2,3,Ln, n( 2)ij( 2)aa,ii11 j(2)=-aaiiijijaj =2j ¹i11= a¹ 0當(dāng)A為嚴(yán)格對(duì)角占優(yōu)時(shí), a(1),余下的子陣仍是。依次類推全不1111¹ 0對(duì)角占優(yōu)的，從而又有a(2)22為零。定理證畢。j再利用方程組的對(duì)角占優(yōu)性,由上式可進(jìn)一步得ai1ai1a1inåj =2j ¹i<-+-) =-a ( 2)aa( aaaiji

24、ii111 1iiiaa11 11 - ai1a1 j= ai, j = 2,3,L, na(2)又由,ijija11一般線性方程組使用高斯消去法求解時(shí)，在消元過程中可能會(huì)出現(xiàn)的情況，這= 0(k )kka時(shí)消去法將無法進(jìn)行；即使，但它的¹ 0a(k )kk絕對(duì)值很小時(shí)，用其作除數(shù)，會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，將嚴(yán)重影響計(jì)算結(jié)果的精度。實(shí)際計(jì)算時(shí)必須避免這類情況的發(fā)生。主元素消去法就可彌補(bǔ)這一缺陷。§5.3高斯主元素消去法交換原則：通過方程或變量次序的交換，使在對(duì)角線位置上獲得絕對(duì)值盡可能大的系數(shù)作為a(k)，稱這樣的a(k) 為主kkkk元素，并稱使用

25、主元素的消元法為主元素法根據(jù)主元素選取范圍分為：列主元素法、行主元素法、全主元素法由此回代解出 x1,但這個(gè)解不滿足原= 0, x2 = 1方程組,解是錯(cuò)誤的。這是因?yàn)樗玫某龜?shù)太小使得上式在消元過程中“吃掉”了下式，解決這個(gè)問題的方法之一就是采用列選主元高斯消元法。即按列選絕對(duì)值大的系數(shù)作為主元素， 則將方程組中的兩個(gè)方程相交換，原方程組變?yōu)閤1 + x2= 2= 1ìí-5x1 + x2î10得到消元后的方程組ìx1 +x2 =2íî(1-105 ) x = 1- 2 ´10-52這時(shí)1-105 = 0.00001

26、80;105 -105 = -105，因而方程組的實(shí)際形式是2 -105= 0.00002´105-105= -105+ x2= 2ìx1í= 1x1= 1, x2xî2= 1由此回代解出,這個(gè)結(jié)果是正確的可見用高斯消去法解方程組時(shí),小主元可能導(dǎo)致計(jì)算失敗,因?yàn)橛媒^對(duì)值很小的數(shù)作除數(shù),乘數(shù)很大,引起約化中間結(jié)果數(shù)量級(jí)嚴(yán)重增長(zhǎng),再舍入就使得計(jì)算結(jié)果不可靠了,故避免采用絕對(duì)值很小的主元素。以便減少計(jì)算過程中舍入誤差對(duì)計(jì)算解的影響。全主元素消去法是通過方程或變量次序的交換，使在對(duì)角線位置上獲得絕對(duì)值盡可能大的系數(shù)作為 a (k )，kk。盡管它的算法更穩(wěn)稱這樣

27、的為主元a (k素)kk定，但計(jì)算量較大，實(shí)際應(yīng)用中大多數(shù)使用列主元素消去法即可滿足需要。 全主元素法不是按列選主元素，而是在全體待選系數(shù)中選取，則得全主元素法。 例5.3用全主元素法解下列線組10x1 - 19x2 - 2x3=3-20x1 +40x2 + x3 =4x1 + 4x2 + 5x3=5(1)(2)(3)n 解：選擇所有系數(shù)中絕對(duì)值最大的40作為主元素，交換第一、二行和交換第一、二列使該主元素位于對(duì)角線的第一個(gè)位置上，得40x2 - 20x1 + x3 =4-19x2+10x1 - 2x3=3(4)(5)(6)4x2+x1 +5x3=5計(jì)算m21=-19/40=0.475，m31

28、=4/40=0.1(5)- m21(4),(6)- m31(4)消去x2得0.5x1 1.525 x3 =4.9(7)(8)3x1 +4.9 x3 =4.6選4.9為主元素4.9x3 +3x1=4.6(9)(10)1.525 x3 +0.5x1=4.9計(jì)算m32=-1.525/4.9=-0.31122，(10)- m32(9)消去x2得1.43366x1=6. 33161(11)保留有主元素的方程40x2 - 20x1 + x3=4(4)(9)(11)4.9x3 +3x1=4.61.43366x1=6. 33161進(jìn)行回代x1=4.41634 x3 =-1.76511x2=2.352305.3

29、.2列主元素法 列主元素法就是在待消元的所在列中選取主元，經(jīng)方程的行交換，置主元素于對(duì)角線位置后進(jìn)行消元的方法。 例5.4用列主元素法解下列線性方程組x1 - 19x2 - 2x3=3x1 +40x2 + x3 =4x1 + 4x2 + 5x3=5(1)(2)(3)n 解：選擇-20作為該列的主元素，-20x1 +40x2 + x3 =3 10x1 - 19x2 - 2x3=4x1 + 4x2 + 5x3=5(4)(5)(6)計(jì)算m21 =10/-20=-0.5m31=1/-20=-0.0510-20(5)- m21(4),(6)- m31(4)得(7)x2 1.5x3=56x2 + 5.05

30、x3=5.2選6為主元素6x2 + 5.05x3=5.2(8)(9)(10)x2 1.5x3=5計(jì)算m32=1/6=0.16667，(10)- m32(9) 得-2.34168x3=4.13332(11)保留有主元素的方程-20x1 +40x2 + x36x2 + 5.05x3=4=5.2(4)(9)(11)-2.34168x3=4.13332進(jìn)行回代x3 =-1.76511 x2=2.35230 x1=4.41634列選主元素的計(jì)算方法與高斯消去法完全一樣, 不同的是在每步消元之前要按列選出主元例5.5用矩陣的初等行變換求解解方程組ìïíï-7

31、8;解:用矩陣的初等行變換求解,對(duì)增廣矩陣(下面帶下劃線元素為主元素)é 2ùúúúûA= A b=(1)éùú78.5- 0.51êæ1 ö+ç -÷r2êr1®ê0êë0é4r «r¾¾2è¾¾ø-1.57.5_7- 0.58.5ú ¾¾¾® 0- 6.52.57.5-1.5

32、32êêë0ú1êúr3 + r1- 2.5úû- 6.5ú2ûù71æ 1 ör3 +ç 5 ÷r2êú¾¾è¾¾ø®ê0êë0- 6.5ú1.2 úû7.508.51.2§5.4 矩陣三角分解法矩陣三角分解法是高斯消去法解線性方程組的一種變形解法5.4.1矩陣三角分解原理應(yīng)用高斯消去法

33、解n階線性方程組Ax=b,經(jīng)過n步消元之后,得出一個(gè)等價(jià)的上三角型方程組A(n) x=b(n),對(duì)上三角形方程組用逐步回代就可以求出解來。上述過程可通過矩陣分解來實(shí)現(xiàn)。將非奇異陣A分解成一個(gè)下三角陣L和一個(gè)上三 角陣U的乘積A=LU稱為對(duì)矩陣A的三角分解，又稱LU分解éa11a1n ùa12 a22a32Lan2a13 a23a33Lan3LLLLLêa21a2n úêú其中A = êa31a3n ú = LUêúêLêëan1L úann ú&

34、#251;éa(1)a(1) ùé 1êùúúú,úú1úûa(1)a(1)L1112131nêêúúúúúm211m32Mmn2a(2)a(2)a(2)ê22232n (3)3nU = êL = êm311LLa(3)a33êêêëêê Mêëmn1Oú(n)ann û方程組A

35、x=b的系數(shù)矩陣A經(jīng)過順序消元逐步化為上三角型A(n),相當(dāng)于用一系列初等變換左乘A的結(jié)果。事實(shí)上，第1列消元將A(1)=A化為A(2)，若令：é0ù1010M0001M0LLLOLê- m210úêú0ú0ú1úû(1)i1am=(i = 2,3,L, n),L1= ê- m31i1a(1)êú11Mêêë- mn1則根據(jù)距陣左乘有L1A(1)=A(2)第2列消元將A(2)化為A(3)，若令：é10ù01- m32

36、 M- mn 2001M0LLLOLê00úêú0ú0ú1úûa(2)L2= ê0m=(i = 3,4,L, n) i 2,i 2êúa(2)êMêë022經(jīng)計(jì)算可知L2A(2)=A(3),依此類推,一般有LkA(k)=A(k+1)é1êêêùúúúúúúúúO1= êL1- mk +1,kMêê&

37、#234;êk1Oê1ú- mëûnk于是矩陣經(jīng)過消元化為上三角陣A(n)A = A(1)LL L A = A(n)的過程可表示為L(zhǎng)Ln-1n-221上述矩陣它們都是Lk (k = 1,2,L, n -1)是一類初等矩陣,下三角陣，且其逆矩陣也是下三角陣,只需將 - mik改為,mik (i = k +1, k + 2,L, n)L-1 。即就得到ké1êêêùúúúúúúúúO1= êL-11mk +1,

38、kMêêêêk1Oê1úmëûnk于是有-A = (L=)U º LU111)A(n)111LLL(LLLLn-1n-11212其中éa(1)a(1) ùé 1êùúúú,úú1úûa(1)a(1)L1112131nêêúúúúúûm211m32Mmn2a(2)a(2)a(2)ê22232n (3)

39、3nU = êL = êm311LLa(3)a33êêêëêê Mêëmn1Oú(n) nnaL為由乘數(shù)由此可見，在的下三角陣，U為上三角陣，的條件下，¹ 0(k = 1,2,L, n -1)a(k )kk高斯消去法實(shí)質(zhì)上是將方程組的系數(shù)矩陣A分解為兩個(gè)三角矩陣的乘積A=LU。這種把非奇異矩陣A分解成一個(gè)下三角矩陣L和一個(gè)上三角矩陣U的乘積稱為矩陣的三角分解，又稱LU分解。顯然，如果¹ 0(k = 1,2,L, n -1),由行列式a(k )kk的性質(zhì)知，方程組系數(shù)

40、矩陣A的前n-1個(gè)順序主子矩陣非奇異，即順序主子Ak (k = 1,2,L, n -1)式不等于零，即det(A ) = a(1)¹ 0111det(A ) =¹ 0(i = 2,3,L, k)(1)(2)(i)iiaaLai1122其中éa11a1i ùLLLA1 = (a11 ), Ai= ê MM ú（A的主子陣）êêëai1úaii úû反之,可用歸納法證明,如果A的順序主子式det(A ) =¹ 0(i = 1,2,L, k)(1)(2)(i)iiaaLa

41、i1122則¹ 0(i = 1,2,L, k)a(i)ii于是得到下述定理：其中 L L, 為單位下三角陣，U ,U 為上三角陣A的行列式LU = LU均為非奇異矩陣,有A ¹ 0, L,U , L,U上式兩邊左邊同乘L-1L = UU -1，右邊同乘得L-1U -1上式左邊為單位下三角陣,右邊為上三角陣,故應(yīng)為單位陣,即惟一性得證。L = L,U = U現(xiàn)僅證明分解的惟一性。設(shè)A有兩種LU分解A = LU = LU把A分解成一個(gè)上三角陣L和一個(gè)下三角陣U的乘積稱為杜利特爾（Doolittle）分解。其中é 1êl21ùúé

42、u11êu1n ùu12u22LLOu2n ú1Mln2L = êú,U = êúê MúúêêëM úOLêúëln11ûunn û若把A分解成一個(gè)下三角陣L和一個(gè)上三角陣U的乘積稱為克洛特分解Crout）其中él11êl21ùúé1êu1n ùu121LLOu2n úl22Mln2L = êú,U = &

43、#234;úê MúúêM úOLêêúëln1lnn û1 ûë5.4.2用三角分解法解方程組求解線性方程組Ax=b時(shí),先對(duì)非奇異矩陣A進(jìn)行LU分解使A=LU，那么方程組就化為L(zhǎng)U x=b從而使問題轉(zhuǎn)化為求解兩個(gè)簡(jiǎn)單的的三角方程組L y=bU x=y求解y求解x這就是求解線性方程組的三角分解法的基本思想。下面只介紹杜利特爾（Doolittle）分解法。設(shè)A=LU為éa11a11 ùé 1ùúúú

44、úéu11êêêêëu1n ùa11 a22Mu12u22LLOLLLOêa21a2n úêl21u2n ú1Mn2êú = êúê MM úê MM úOLêaúnn ûêúnn ûaaëln1l1ûuën1n2由矩陣乘則= u1ii = 1,2,L, ni = 2,3,L, na1iai1 = li1u1

45、1由此可得U的第1行元素和L的第1列元素= a1ii = 1,2,L, ni = 2,3,L, nu1iai1=li1u11éa11a11 ùé 1ùúúúúéu11êêêêëu1n ùa11 a22Mu12u22LLOLLLOêa21a2n úêl21u2n ú1Mn2êú = êúúê Múê MMOLMêa

46、50;êúaaëln1l1ûuë n1nn ûnn ûn2再確定U的第k行元素與L的第k列元素,對(duì)于k=2,3, ,n計(jì)算： 計(jì)算U的第k行元素k -1- ålkr urj= akjukj（j=k,k+1,n）r =1計(jì)算L的第k列元素aik- ålir urkk -1（i=k,k+1,n）= r =1likukk利用上述計(jì)算公式便可逐步求出U與L的各元素求解Ly=b,即計(jì)算:ì y1= b1ïí yi-1= b - ål(i = 2,3,L, n)yïi

47、iikkîk =1求解Ux=y ,即計(jì)算：ìxyn=ïïíïnunnnåy-uxiikkïx= k =i+1(i = n - 1,L,2,1)iïuîii¹ 0(k = 1,2,L, n)顯然, 當(dāng)ukk時(shí),解Ax=b直接三角分解法計(jì)算才能完成。設(shè)A為非奇異矩陣, 當(dāng) ukk= 0 時(shí)計(jì)算將中斷或者ukk當(dāng)絕對(duì)值很小時(shí)，按分解公式計(jì)算可能引起舍入誤差的積累，因此可采用與列主元消去法類似的方法，對(duì)矩陣進(jìn)行行交換，則再實(shí)現(xiàn)矩陣的三角分解。用直接三角分解法解Ax=b大約需要次乘除法。n3/

48、3例6.8用三角分解法解方程組é1ê13ù5ú6é x1ùúúúûé22ê x2= ê4êêë x3êêë5é1ùúú1úûéL = ê1= ê11Uêêë1êêëLy=bUx=yy= 2，2，1T求解求解得得x= -1，0，1 T所以方程組的解為= 13&#

49、167;5.5解三對(duì)角線方程組的追趕法在數(shù)值計(jì)算中,有一種系數(shù)矩陣是三對(duì)角方程組é b1c12a3êabcêêêêêêë22cOa3簡(jiǎn)記為Ax=f,A滿足條件(對(duì)角占優(yōu)）（1）（2）（3）>³> 0b1bic1+ ciai(> a> 0bnnìb1= l1按乘法展開ï= liuiíciï1= ai+1ui+ li+1當(dāng)，lii = 1,2,L, n - 1bî i+¹ 0= b1= ciìl1則可計(jì)算由

50、上式可惟ï一確定L和U。i = 1,2,L, n -1®L® un-1 ® lníui/ liï1= bi+1 - ai+1uilîi+® u1 ® l2® u2可依次計(jì)算l1éb1ùúc1bé lùé1úêúêúêùúúuêa11cêaêêêêú22O2l1uú =

51、ê222Oêêëun-1 úúOOOabcúêún-1 ún-1n-1al1n ûëûêúnabënûn-13- 2é 2ê-1- 2êêêëf1= 3 = 1.5,2y =由Ly=f解出y1l1a yy= 332 3l3x4 = y4 = -1,= y2 - u2 x3 =又由Ux=y解出xx25.6解正定矩陣方程的平方根法工程實(shí)際計(jì)算中,線性方程組的系數(shù)矩陣常常具

52、有對(duì)稱正定性，其各階順序主子式及全部特征值均大于0。矩陣的這一特性使它的三角分解也有更簡(jiǎn)單的形式，從而導(dǎo)出一些特殊的解法，如平方根法與改進(jìn)的平方根法。定理6設(shè)A是正定矩陣，則存在惟一的對(duì)角元素均為正數(shù)的下三角陣L，使A=LLT證：因A是正定矩陣,A的順序主子式i>0, i=1,2,n因此存在惟一的分解A=LUL是下三角陣, U是上三角陣, 將U再分解éùúúu12 u1nùê1úêúêúêúênn ûêëLéu

53、11 êêêêëuu11 11 u1ú = DU22 un-1,núúúû0OOuun-1,n-11其中D為對(duì)角陣, U0為A = L U = L D U0上三角陣，于是A = AT = UTD LT又0由分解惟一性, 即得U T=L0A=L D LTéu11 êùúúúúnn û> 0,(i = 1,2,L, n)記u22 D = êêêëOuuii又因?yàn)閐et(Ak)

54、0,(k=1,2,n), 故于是對(duì)角陣D還可分解éùéúêúêúêùéu11êùu11u11êúúu11uuú = êú = D2 D2D = ê222222êêêëúêêëúúnn ûOOOúêúuuunn úûêën

55、n úû1111 A = LDLT = LD2 D2 LT = (LD2 )(LD2 )T = L LT111L1 = LD 2其中為下三角陣,令L=L1，定理得證。將A=LLT展開，寫成éa11a11 ùél11ùúúúúnn ûél11êêêêëln1 ùa11 a22Ml21l22LLOLLLOêa21a2n úêl21ln2 úl22Mêú = &#

56、234;úê Múê MM úMOLêaúêúnn ûaaëln1lllë n1nn ûn2n2按矩陣乘法展開，可逐行求出分解矩陣L的元素，計(jì)算公式是對(duì)于i=1,2,ni-1a ji - ål jk lik k =112i-1åj=i+1, i+2,nl= (a-2l)l=iiiiikjilk =1ii這一方法稱為平方根法,又稱喬累斯基(Cholesky)分1 n3解,它所需要的乘除次數(shù)約節(jié)省近一般的工作量。為數(shù)量級(jí),比LU分解6例6.9平方根法

57、求解方程組é12 ùé x1ùúúúûé5ù120ê10 úêx= ê8úêêë2ú11úûêêúêë7úû2êë x3é1êùúú3úûy1 = 5, y2 = 3, y3 =解得3由Ly=b解得L = ê11- 2LT x = y由êë2= 13由此例可以看出，平方根法解正定方程組的缺點(diǎn)是需要進(jìn)行開方運(yùn)算。為避免開方運(yùn)算，我們改 用單位三角陣作為分解陣，即把對(duì)稱正定矩陣A分解成A