數(shù)值計算方法解線性方程組的數(shù)值解法

1、3.2 矩陣的三角分解法n我們知道對矩陣進(jìn)行一次初等變換，就相當(dāng)于用相應(yīng)的初等矩陣去左乘原來的矩陣。因此我們這個觀點來考察Gauss消元法用矩陣乘法來表示，即可得到求解線性方程組的另一種直接法：矩陣的三角分解。 3.2.1 Gauss消元法的矩陣形式)2() 1 (1)2()2(2)2()2() 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 (131211) 1 (11) 1 (1111131121) 1 (11.1.00.1011.,32i)()(1),.,0:122211211212222111211AALaaaaaaaa

2、aaaaaaaalllni-laalaaaannnnnnnnnnnniiin，其矩陣形式為，行行令消零時，將步等價于第則）（）（）（)3()3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11222)2(22)2(222322)2(22.00.00.0.:),.,4 , 3(1.00.0.100.0100.00102AaaaaaaaaaaaALAniaalllLannnnnn)()(iin，即有左乘時，用矩陣步等價于：若同理第1.1111.11.000.00.0.2321212111)()3(3)3(33)2(2)2(23)2(22)1(1)1(13

3、)1(12)1(111221nnnnnnnnnnllLllLUaaaaaaaaaaALLLL因為以此類推可得為上三角陣為單位下三角陣，其中所以U1.111.).(1213231211112121111221LLUUllllllULLLLULLLLAnnnnnnnn分解。行直接進(jìn)否對矩陣因此，關(guān)鍵問題在于能個三角方程：就等價于解兩由此解線性方程組LUAyUxbLyULAbxbx)(3.2.2 Doolittle分解1131313111311121212111211111232322131211323121333231232221131211)3 , 2 , 1(11113,ualluauallu

4、ajauuakuuuuuulllaaaaaaaaanULjjjj得由；得由時：為例的各元素，以此分解在于如何算出)(322332133133333323321331332212313232233212313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得時：由得由；得由；得時：Doolittle分解n若矩陣A有分解：A=LU，其中L為單位下三角陣，U為上三角陣，則稱該分解為Doolittle分解，可以證明，當(dāng)A的各階順序主子式均不為零時，Doolittle分解可以實現(xiàn)并且唯一。nA的各階順序主子

5、式均不為零，即),.2 , 1(0.1111nkaaaaAkkkkkDoolittle分解各元素方法逐行逐列求解用比較等式兩邊元素的令ULuuuuuulllaaaaaaaaannnnnnnnn,.1.11.222112112121n2n1n2222112111Doolittle分解。得再由；得由時：。得再由；得由時),.,4 , 3(),.,3 , 2(12),.,3 , 2(),.2 , 1(1:12212122222121212222121211111111 i1111niuulalululanjulauuulakniualluanjauuakiiiiiijijjjjjiiijjjjDoo

6、little分解1111211211,.1,000.10.,.,kttjktkjkjktkjtjktjjjjkkkkkjknkkkknkkjulauuuluuulllakjuuuk）（有步時：計算第Doolittle分解11111111,.1/)(000.0, 1 ,.,.,ktkktkitikikktkkiktkitkkkikiiknkkknkiuulalululuullakill）（得，于是由由于計算Doolittle分解nnnnnnkkkttkitikikkttjktkjkjulluuluuunkuulalnkinkjulau.A,.,2 , 1/ )(),.,1;,.,(2122221

7、112111111的各位各元素在計算機(jī)內(nèi)存于即Doolittle分解。可獲解得及再由TniinijjijiiijjijiixxxnniuxuyxniylbyULxyxby),.,(1,.1,/ )(,.,2 , 121111例題30191063619134652.D. 1321xxxoolittle分解求解方程組試用例例題。，；，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuuuuulllALU例題LUAululaukuulalulauulauk473652143121434/ )(7)6(219

8、35213223321331333322123132321321232312212222所以時：，時：例題TyyyyyyybLy)4 , 1,10(43034, 12019,1030191014312112321321即得）解（、解方程組例題。所以方程組的解為解得：解TxxxxxxxyUx) 1 , 2 , 3(3, 2,2(123321Doolittle分解).,.,()(),.,(/ )(;/)2),.,)(;) 1)(),.,(/ )(),.,(,.,)2),.,(/)(),.,(),.,() 1 (nixniuxuyxayxniylbybyyUxbLynkiu

9、ulalankkjulauankniaalaLUAnibnjiaiiinijjijiinmnnijjijiikkkttkitikikikkttjktkjkjkjiiiiij2141212311323212212111111111111111輸出：方程組的解；和解；做對；分解輸入：3.2.3 對稱矩陣的Cholesky分解n在應(yīng)用數(shù)學(xué)中，線性方程組大多數(shù)的系數(shù)矩陣為對稱正定這一性質(zhì)，因此利用對稱正定矩陣的三角分解式求解對稱正定方程組的一種有效方法，且分解過程無需選主元，有良好的數(shù)值穩(wěn)定性。 對稱矩陣的Cholesky分解n A對稱：AT=A A正定：A的各階順序主子式均大于零。即 ),.2 ,

10、1(0.1111nkaaaaAkkkkk對稱矩陣的Cholesky分解n由Doolittle分解，A有唯一分解 。，也就是所以，有即TTTTTTTTTLLAULULLULULULULUALU)(A對稱矩陣的Cholesky分解n定理3.2.4 設(shè)A為對稱正定矩陣，則存在唯一分解A=LDLT，其中L為單位下三角陣，D=diag(d1,d2,dn)且di0(i=1,n)對稱矩陣的Cholesky分解n證明： ndddUULLUADoolittle21111,A令非奇異的上三角陣。為為單位下三角陣，其中分解為分解可唯一是對稱正定，由因為對稱矩陣的Cholesky分解均大于零即。得由；得；由得故有的順

11、序主子式均大于零是正定的，則又因為nnnnddddddddddddA,.,00.;0000A21212212111對稱矩陣的Cholesky分解。所以為單位上三角陣。為對角陣其中故LDUAUDDUdddddddUn,1.1*.*1*.*12211211對稱矩陣的Cholesky分解。，所以故有對稱，即又因為TTTTTTLDLAULADLULDUAA)(推論：設(shè)A為對稱正定矩陣，則存在唯一分解 其中L為具有主對角元素為正數(shù)的下三角矩陣。TLLA 對稱矩陣的Cholesky分解n證明： 0,.,0, 0)(4 . 2 . 3),.,(2121212121nTTTndddLLLLDLDLDLAddd

12、diagD的主對角元素為其中則由定理令Cholesky分解的求法332322131211333231222111333231232221131211212221113?.,llllllllllllaaaaaaaaanlllllllLLLAAijnnnnT為例。以如何求令則對稱正定設(shè)Cholesky分解的求法。，得由；，得時：由。；同理得，得由；，得時：由2221313232223221313222122222222212211313111212111212111112111121lllalllllalalllaklallalllaallakCholesky分解的求法njnjilllallaln

13、lallllakjjjkjkikijijjkjkjjjjii,.,2 , 1,.,1/ )()(,311211122123333323323223133有階行列式推廣到，得時：由Cholesky分解法TTLLAyxLbLybAXcholesky其中分解法解線性方程組用Cholesky分解法缺點及優(yōu)點 優(yōu)點：可以減少存儲單元。 缺點：存在開方運算，可能會出現(xiàn)根號下負(fù)數(shù)。改進(jìn)Cholesky分解法n改進(jìn)的cholesky分解A=LDLTnnnnnnnnTnnnnnndlddldlddldldlddllllllDLLAdddDllllllL.1.111)(1.11133322322211311211

14、112132312121121323121由改進(jìn)的cholesky分解1121111211,.,2 , 1) 1,.,2 , 1(/ )(),.,2 , 1() 1,.,2 , 1(jkkikiiijjkjkkikijijjkikikiijijjkjkkikijnidladijdldlalniddlaijdlldlaji由此可得有逐行相乘，并注意到改進(jìn)的cholesky分解) 1,.,2 , 1,.,3 , 2(,1111ijnilcaddcllcacdcldlcikikikiiijijijjkjkikijijjijijjijij，成所以可將上述公式改寫，則可令為減少計算量TnnnTdydyd

15、yyDdddDDLLACholeskyyxbybx),.,(111221112111故即等價于求分解法解線性方程組用改進(jìn)的cholesky分解算法；做對做對分解，輸入1111)2(1,.,2 , 1) 1 (,.,3 , 2. 2);,.2 , 1(),.,2 , 1(. 1ikikikiiiiijijijijjkikikijijTiijlcadadclalcacijniLDLAnibni,ja改進(jìn)的cholesky分解算法。輸出：；解；解解),.,2 , 1()3() 1,.,1()2(),.,2() 1 (. 3111111nixnixldyxdyxyDxLniylbybybLyAinik

16、kkiiiinnnTikkikiibx例題分解做解：對系數(shù)矩陣算法解方程組分解試用改進(jìn)的例DoolitteAxxxCholeskey6353212211142 . 2 . 3321例題TLDLA11125. 025. 0111.7541125. 025. 01175. 11.751141125. 025. 011125. 075. 175. 125. 01143125. 075. 175. 125. 01143225. 02225. 0114321221114例題TybyyyyyyyL)3 ,47, 5(3,75. 1, 5635110.25125. 01321321即得得由例題TTTxyxy

17、xxxxxxDLD)3 , 2 , 1 (1, 2, 33125. 111125. 025. 01)3 , 1,45(12332111所以方程的解：得得，由而nA=LDLT分解，既適合于解對稱正定方程組，也適合求解A為對稱，而各階順序主子式不為零的方程組n而對A=LLT只適合于對稱正定方程組3.2.4 三對角方程組求解的追趕法nnnnnijnnijabcabcabcaAajaA11122211, 01|i |)(即有，對一切設(shè)三對角矩陣三對角方程組求解的追趕法),.,3 , 2(1111,111111221132nicpaqqbpaqqcqcqcqpppALUDoolittleAiiiiiii

18、nnnn其中則有分解滿足如果三對角方程組求解的追趕法),.,2(1111),.,(1113213213221niypfyfyffffyyyypppfffULAiiiinnnTnfyxfyfx解得，故有其中等價于求則求三對角方程組求解的追趕法組的追趕法。以上稱為解三對角方程解得再由) 1,.,1(1121121112211niqxcyxqyxyyyyxxxxqcqcqcqiiiiinnnnnnnnnn三對角方程組求解的追趕法n其計算工作量為5n-4次乘除法。工作量小，其實現(xiàn)的條件為qi不為零。有以下定理可得證三對角矩陣求解的充分性條件。且追趕法可以實現(xiàn)。非奇異則矩陣，且滿足形如設(shè)三對角矩陣定理,

19、| |,|)3() 1,.,3 , 2(|)2(),.2 , 1(0) 1 (,11). 2 . 3(2 . 2 . 311AabcbnicabnicAnniiii解三對角矩陣線性方程組的追趕法程序框圖3.3 矩陣求逆的解。個方程組的為單位向量，右端項分別均為問題等價于求系數(shù)矩陣解存在，求的逆矩陣非奇異，則設(shè)矩陣),.,2 , 1()0,.,1,.,0 , 0(11njAnAAAAAjjTjjexe矩陣求逆這就是原地求逆。個單元，則可節(jié)省放的單元，最后仍用來存如果將個單元還是很困難的。很大時，這但當(dāng)個存儲單元即可實現(xiàn)，。算法上增加了則）（）（式即為順序消去法知，求解上由初等變換21221|nAAnnnAXXIIAJordanGauss矩陣求逆111)()()()()()()(111.)(1)(1.1.:LLLAkiakiaallllLIALLLJordanGaussnnkkkkkkkikkikknkkkkkkKnn故其中消去法矩陣形式由實現(xiàn)n為使求逆過程不斷提高求解精度，因此增加選主元工作，最常用的是選列主元求逆。因此增加一個數(shù)組Z(n)，記錄選主元的交換號，最后在消元工作完成后，根據(jù)Z(n)對A中的元素進(jìn)行相應(yīng)的列交換，得到A-1GaussJordan原地求逆法算法（原地求逆法）);,.2 , 1() 3(;, 0)2(;)(|max|) 1 (),.2 , 1.