Gauss消去法、 矩陣分解

1、第1頁(yè)/共42頁(yè)2.1 Gauss消去法下面通過(guò)簡(jiǎn)單例子導(dǎo)出一般算法。下面通過(guò)簡(jiǎn)單例子導(dǎo)出一般算法。設(shè)給定方程組設(shè)給定方程組1111221331441211222233244231132233334434114224334444,.a xa xa xa xba xa xa xa xba xa xa xa xba xa xa xa xb (1)第2頁(yè)/共42頁(yè)1111/iilaa 乘以第一個(gè)方程，這樣方程組（乘以第一個(gè)方程，這樣方程組（1 1） 1111221331441,a xa xa xa xb (2)(2)(2)(2)2222332442(2)(2)(2)(2)3223333443(2)(

2、2)(2)(2)4224334444,axaxaxbaxaxaxbaxaxaxb (2) 化為化為其中：其中：(2)11(2)11,2,3,4,2,3,4.ijijijiiiaalai jbblbi顯然方程組（顯然方程組（2）和原方程組（）和原方程組（1）等價(jià)）等價(jià) 若若110a ，則以第，則以第(2,3,4)i i 個(gè)方程減去個(gè)方程減去 第3頁(yè)/共42頁(yè) 1111221331441(2)(2)(2)(2)2222332442(3)(3)(3)3333443(3)(3)(3)4334444,.a xa xa xa xbaxaxaxbaxaxbaxaxb(3)(3)(2)(2)22(3)(2)(

3、2)22,3,4,3,4.ijijijiiiaalai jbblbi 其中其中依此方法繼續(xù)下去，得到依此方法繼續(xù)下去，得到以（以（2 2）的第）的第i個(gè)方程個(gè)方程(3,4)i 減去減去(2)(2)2222/iilaa 乘以第二個(gè)方程，得到乘以第二個(gè)方程，得到 第4頁(yè)/共42頁(yè)1111221331441(2)(2)(2)(2)2222332442(3)(3)(3)3333443(4)(4)4444,.a xa xa xa xbaxaxaxbaxaxbaxb （4）(3)(3)(4)(3)(3)(4)(3)(3)4343444434443(3)(3)3333,.aaaaabbbaa 其中其中從（從

4、（4）的最后一個(gè)方程組得到）的最后一個(gè)方程組得到(4)440,a 若若(4)(4)4444/,xba 第5頁(yè)/共42頁(yè)(3)(3)(3)3334433()/,xbaxa再將再將4x代入（代入（4 4）倒數(shù)第二個(gè)方程，可得：）倒數(shù)第二個(gè)方程，可得：類似地，得到：類似地，得到： (2)(2)(2)(2)22233244221112213314411()/,()/,xbaxaxaxba xa xa xa 我們稱將方程組（我們稱將方程組（1）按以上步驟化為等價(jià)方程組）按以上步驟化為等價(jià)方程組（4）的過(guò)程為解線性方程組的）的過(guò)程為解線性方程組的消元過(guò)程消元過(guò)程 從（從（4）中得出解的過(guò)程稱為高斯消去法的

5、）中得出解的過(guò)程稱為高斯消去法的回代過(guò)程回代過(guò)程 第6頁(yè)/共42頁(yè)一般情形一般情形對(duì)于一般的對(duì)于一般的n階線性代數(shù)方程組階線性代數(shù)方程組Axb 11112211211222221122,nnnnnnnnnna xa xa xba xa xa xba xa xa xb即即1. 消元過(guò)程消元過(guò)程首先消去第一列除首先消去第一列除 之外的所有元素，之外的所有元素， 11a第7頁(yè)/共42頁(yè)(2)(1)11221,10,0,0nnnaaa 設(shè)設(shè)總可由消元過(guò)程得到系數(shù)矩陣為上三角陣的線性代數(shù)總可由消元過(guò)程得到系數(shù)矩陣為上三角陣的線性代數(shù)方程組，其第方程組，其第k步的結(jié)果為步的結(jié)果為(1)(1)(1)(1)1

6、1112211(2)(2)(2)22222( )( )( )( )( )( ),.nnnnkkkkkkknnkkkknkknnnnaxaxaxbaxaxbaxaxbaxaxb第8頁(yè)/共42頁(yè)其中其中(1),1( )(1)(1)1(1)1,1,ki kkkkijijkjkkkaaaai jkna (1),1( )(1)(1)1(1)1,1,ki kkkkiikkkkabbba 這里取這里取 (1)(1)1111,1,2, ,.jjaajnbb 2. 2. 回代過(guò)程回代過(guò)程若通過(guò)消元過(guò)程原方程組已化為等價(jià)的三角形若通過(guò)消元過(guò)程原方程組已化為等價(jià)的三角形方程組方程組第9頁(yè)/共42頁(yè)(1)(1)(1)

7、(1)11112211(2)(2)(2)22222( )( ),.nnnnnnnnnnaxaxaxbaxaxbaxb 且且 , 則逐步回代可得原方程組的解則逐步回代可得原方程組的解( )0nnna ( )( )( )( )( )1/,/,1,2,2,1.nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 第10頁(yè)/共42頁(yè)2.2 Gauss主元素消去法Gauss逐步消去法有如下的缺點(diǎn)逐步消去法有如下的缺點(diǎn)： 任一主元任一主元 ，就無(wú)法做下去，就無(wú)法做下去( )0(1,2, )kkkakn 任一任一 絕對(duì)值很小時(shí)絕對(duì)值很小時(shí),也不行（舍入誤差的影響大）也不行（舍入誤差的影響大）( )

8、kkka第11頁(yè)/共42頁(yè)例例 二元線性方程組二元線性方程組41212101,2xxxx 精確解為精確解為 1210.000/9.999,9.998/9.999.xx 下面我們用三位浮點(diǎn)十進(jìn)制數(shù)求解：下面我們用三位浮點(diǎn)十進(jìn)制數(shù)求解：（1 1） 按按GaussGauss逐步消元法逐步消元法31112100.100100.100100.100 xx 552100.100100.100 x 得近似解得近似解121100.100,0,xx完全失去近似意義。完全失去近似意義。1x 第12頁(yè)/共42頁(yè)（2 2）變換方程的順序然后消元）變換方程的順序然后消元11112100.100100.100100.20

9、0 xx112100.100100.100 x得近似解得近似解1121100.100,100.100 xx相當(dāng)近似相當(dāng)近似 1x 下面我們討論選主元素的方法。下面我們討論選主元素的方法。第13頁(yè)/共42頁(yè)1) 1) 列主元消去法列主元消去法假設(shè)假設(shè)GaussGauss消去法的消元過(guò)程進(jìn)行到消去法的消元過(guò)程進(jìn)行到 第第 步，設(shè)步，設(shè) (11)kkn ( ),maxkki kk i naa 并令并令 為達(dá)到最大值為達(dá)到最大值 的最小行標(biāo)的最小行標(biāo) ， jkajk jk 若則交換則交換 和和 中的第中的第 行和第行和第 行，行，Abjk再進(jìn)行消元過(guò)程的第再進(jìn)行消元過(guò)程的第 步。步。k第14頁(yè)/共42

10、頁(yè)( )( ),/kkiki kk klaa 這時(shí)每個(gè)乘子這時(shí)每個(gè)乘子 都滿足都滿足 ,1, ,i klikn 可以防止有效數(shù)字大量丟失而產(chǎn)生誤差。可以防止有效數(shù)字大量丟失而產(chǎn)生誤差。2) 2) 全主元消去法全主元消去法( ),max.kki jk i j na 定義定義然后進(jìn)行第然后進(jìn)行第 步消元過(guò)程步消元過(guò)程 k此時(shí)交換此時(shí)交換 和和 的行及的行及 的列，使主元位置的元素的列，使主元位置的元素的絕對(duì)值具有給出的最大值的絕對(duì)值具有給出的最大值 ， Abk A第15頁(yè)/共42頁(yè)注意：因?yàn)橛辛械慕粨Q，因此未知量的注意：因?yàn)橛辛械慕粨Q，因此未知量的次序有改變，待求解過(guò)程結(jié)束后必須還原。次序有改變，

11、待求解過(guò)程結(jié)束后必須還原。多使用列主元消去法。多使用列主元消去法。第16頁(yè)/共42頁(yè)2.3 矩陣的三角分解與Gauss消去法的變形GaussGauss消去法的實(shí)質(zhì)是將矩陣消去法的實(shí)質(zhì)是將矩陣 分解為分解為A其中其中 -單位下三角矩陣，單位下三角矩陣， -上三角矩陣。上三角矩陣。LU事實(shí)上，線性方程組事實(shí)上，線性方程組Axb 經(jīng)過(guò)經(jīng)過(guò) 步消元過(guò)程后，有等價(jià)方程組步消元過(guò)程后，有等價(jià)方程組k,kkA xb 其中：其中： 而而 和和 的形式為：的形式為：11,AA bb kAkbAL U ( ) 第17頁(yè)/共42頁(yè)(1)(1)(1)1111( )( )( )( )( )( ),nkkkkkkkknk

12、kkknknnnaabAbaabaab （1）可以直接驗(yàn)證可以直接驗(yàn)證 1kkkALA 第18頁(yè)/共42頁(yè)( ),( )1,11,11ki kki kkkkkkn kaLllal 其中其中1,(0,0,) ,1,2,1,Tkkkn klllkn 記記則則TkkkLIle 1111,(2, )kkkkALL AbLL b kn第19頁(yè)/共42頁(yè)111nLLL 令令11nLL 乘積乘積是下三角陣，且對(duì)角元全部等于是下三角陣，且對(duì)角元全部等于1 1 則則 也是對(duì)角元等于也是對(duì)角元等于1 1的下三角陣的下三角陣 L 用矩陣用矩陣 依次左乘原給方程組依次左乘原給方程組兩邊，得等價(jià)方程組兩邊，得等價(jià)方程組

13、 11,nLL nnA xb Axb 1TkkkLIle 我們可以計(jì)算得到我們可以計(jì)算得到111111111nTnnkkkLLLLIle 則則其中其中121,nnnALLL A 121nnnbLLL b 第20頁(yè)/共42頁(yè)211,1111nn nlll 由于由于 為上三角陣，記為上三角陣，記 nA()nijAUu , ,于是得到于是得到111211,110101nnnnn nuulAL Uull (2)第21頁(yè)/共42頁(yè)GaussGauss逐步消去法等價(jià)于下述過(guò)程：逐步消去法等價(jià)于下述過(guò)程：2. 2. 求解三角形方程組求解三角形方程組 （回代過(guò)程）。（回代過(guò)程）。1UxL b ( (注意上面的

14、全部討論中要求注意上面的全部討論中要求 ) )( ),0,1,2,1kk kakn 定義定義 稱稱1111kkkkaaaa 為為 的的 階順序主子矩陣階順序主子矩陣Ak1,2,kn 其中其中第22頁(yè)/共42頁(yè)證明證明11kkALL A 根根據(jù)據(jù)我們得到我們得到111121kkkkALLLALA (3)(3)其中其中 形如形如(1)(1)式式0kkkn kMLHI 我們可以將我們可以將 寫成寫成KL其其中中和表示和表示如下如下kkMH定理定理5.10 5.10 kA第23頁(yè)/共42頁(yè)1,11,12,12,121,1,1110101,01kkkkkkkknn kkkklllllMHllll 將（將

15、（3 3）寫成分塊形式為）寫成分塊形式為( )( )11121112( )( )212221220kkkkkkn kMAAAAHIAAAA 其中其中 為為 的的 階順序主子陣，階順序主子陣， ( )11kAkAk 為為 的的 階順序主子陣。階順序主子陣。 11AAk第24頁(yè)/共42頁(yè)A于是得到于是得到( )1111kkAMA 從而從而( )1111det()det() det()kkAMA ( )(1)(2)( )111122det()kkkkAaaa 因此因此( )0kkka (1,2,1)kn 即即 有有 分解形式的充分必要條件為分解形式的充分必要條件為 的所有順序主子陣非奇異。的所有順序

16、主子陣非奇異。ALU第25頁(yè)/共42頁(yè)最后最后, ,我們假設(shè)我們假設(shè)1122LUL UA 是是A的兩個(gè)的兩個(gè)形如形如(2)(2)的分解，那么的分解，那么111212BLLUU既是對(duì)角元等于既是對(duì)角元等于1 1的上三角陣，又是對(duì)角元等于的上三角陣，又是對(duì)角元等于1 1的的下三角陣，即下三角陣，即 ，所以，所以BI 12,LL 12UU 從而從而 的分解形式是唯一的。的分解形式是唯一的。ALU 證畢證畢第26頁(yè)/共42頁(yè)定理定理5.115.11第27頁(yè)/共42頁(yè)Doolittle分解算法：分解算法： 第28頁(yè)/共42頁(yè)第29頁(yè)/共42頁(yè)第30頁(yè)/共42頁(yè)111211112121212222221,

17、11210110nnnnnn nnnnnnnaaauuulaaauullaaau 比較等式兩邊對(duì)應(yīng)元素可算出比較等式兩邊對(duì)應(yīng)元素可算出Doolittle分解也可通過(guò)令分解也可通過(guò)令第31頁(yè)/共42頁(yè)1111,1, ,1,1, ,iikikijjkjikikikjjijiiualuki inlalukinu 111111,1,2, ,/,2, ,kkkkuaknlaukn 11.nnnnnnjjnjualu 21,in第32頁(yè)/共42頁(yè)111112112121222122221,11201101nnnnnn nnnnnnnlaaauullaaaulllaaa Crout分解：分解：比較兩邊對(duì)應(yīng)的

18、元素，得到比較兩邊對(duì)應(yīng)的元素，得到第33頁(yè)/共42頁(yè)1111,1, ,1,1, ,ikikikjjijiikikijjkjiilaluki inualukinl 21,in11.nnnnnnjjnjlalu 111111,1,2, ,/,2, ,kkkklaknualkn 第34頁(yè)/共42頁(yè)12110012122321002113011/21001/2A 100100121210020011/211/21001/2001 例例ALDU 實(shí)際上，進(jìn)一步可以做分解實(shí)際上，進(jìn)一步可以做分解其中其中12(,)，nDdiag d dd 、 分別為單位下、上三角陣分別為單位下、上三角陣 LU第35頁(yè)/共4

19、2頁(yè)當(dāng)當(dāng) 為對(duì)稱正定矩陣時(shí)，為對(duì)稱正定矩陣時(shí)， A存在三角分解存在三角分解ATAL L 其中其中L為下三角矩陣。為下三角矩陣。 1. 對(duì)稱正定陣的Cholesky分解首先我們來(lái)看一個(gè)命題首先我們來(lái)看一個(gè)命題:證明證明:我們對(duì)我們對(duì)A做分解做分解ALDU 12(,)nDdiag d dd 其中其中 、 分別為單位下、上三角陣分別為單位下、上三角陣 L U又由于又由于TAA 則則TUL 第36頁(yè)/共42頁(yè)于是有于是有TALDL 由于由于 正定，故有正定，故有 A0id 1, 2,in 取取1/21/21/21(,)nDdiag dd 令令1/2LL D 1/21/21/21/2()(),TTTALDDLLDLDL L 即得即得證畢證畢我們將上面的這種分解稱為我們將上面的這種分解稱為CholeskyCholesky分解分解。下面我們討論下面我們討論CholeskyCholesky分解的算法。分解的算法。 第37頁(yè)/共42頁(yè)11111211121121222122222,11,11200nnnn nnn nnnnnnnnnlaaalllllaaalllllaaal 比較兩邊對(duì)應(yīng)的元素，有：比較兩邊對(duì)應(yīng)的元素，有：21111la 因因 正定，就有正定，就有A110a ，故，故11