第三章 線性代數(shù)方程組的直接解法1

1、在沒有在沒有舍入誤差舍入誤差的情況下，經(jīng)過有限次的情況下，經(jīng)過有限次運算可以得到方程組的運算可以得到方程組的精確解精確解的方法。的方法。 第三章第三章 線性方程組的直接解法線性方程組的直接解法/*Direct Method for Solving Linear Systems*/求解求解,n nAxb AR 0det( )A Cramer法則法則: :1 2, ,iiDxinD所需乘除法的運算量大約為所需乘除法的運算量大約為( (n+1)!+)!+nn=20時，每秒時，每秒1億億次運算速度的計算機要算次運算速度的計算機要算30多萬年！多萬年！直接法直接法3.1 三角形方程組和三角分解三角形方程

2、組和三角分解一、一、 三角形方程組的解法三角形方程組的解法 考慮考慮下下三角形方程組三角形方程組Lyb L 32l2nl21l31l1nl1nnl 11l22l33lnnl1122,nnybybybyb的計算公式為的計算公式為：iy1111 2, , ;iiiijjjiiybl yinl 算法算法3.1.1 下三角形方程組的下三角形方程組的前代前代法：法：11:jnfor( )( ) ( , )b jb jl j j 111(: )(: )( ) (: , )b jnb jnb j l jn j ( )( ) ( , )b nb n l n n end 考慮考慮上上三角形方程組三角形方程組Ux

3、y 11121222.nnnnuuuuuuU 1122,nnxyxyxyxy的計算公式為的計算公式為：ix1111, ;niiijjj iiixyu xin nu 算法算法3.1.2 上三角形方程組的上三角形方程組的回代回代法：法：1 2:jnfor( )( )( , )y jy ju j j 111111( :)( :)( ) ( :, )yjyjy j ujj 1111( )( )( , )yyu end兩種算法的工作量兩種算法的工作量(加減乘除運算次數(shù)之和加減乘除運算次數(shù)之和)均為均為2n 三角分解法的基本思想三角分解法的基本思想:AxbLUxbLybUxy 記記yUx 方程組可化為下面

4、兩個方程組可化為下面兩個易求解易求解的的三角三角方程組方程組ALU 設已知方程組系數(shù)矩陣的三角分解為設已知方程組系數(shù)矩陣的三角分解為其中其中, 為為下下三角矩陣三角矩陣, 為為上上三角矩陣三角矩陣.LU二、二、 高斯高斯( (Gauss) )變換變換111kL 11,kkl , nkl 取下三角形矩陣取下三角形矩陣eTkkkLIl 則則 可表示為可表示為kL其中為其中為 單位矩陣單位矩陣,I 1,0,0,Tkkkn klll 稱下三角形陣稱下三角形陣 為為高斯高斯(Gauss)變換變換, 為高斯向量為高斯向量.kLkl Gauss變換的定義變換的定義 高斯高斯(Gauss)變換的性質變換的性質

5、性質性質1 設向量設向量 且且則存在唯一的則存在唯一的下三角陣下三角陣 ,滿足滿足12(,)Tnxx xx 0kx Tkk kLIl e 100(, , ) .TkkL xxx 證明：證明：尋找滿足條件的尋找滿足條件的初等初等下三角陣下三角陣Tkk kLIl e 100(, , )Tkyxx 記記()TTkkkkkkkL xIl exxl e xxl xy100,( , ,)Tkkkn klll 寫成分量形式：寫成分量形式：01ik i kxx likn,1,ii kkxliknx 唯一唯一確定確定性質性質2 1kL 11111,kkl , nkleTkkIl 性質性質3()ijL Lji 1

6、1111jjl ,n jl ,11iil ,12jil ,n il ,性質性質41kL 11111,kkl , nkl若記若記 ,則有則有111121nL LLL 32l112nl121l31l1nl11, nnl 2 13 13 21211111,nnn nlllLlll 即即單位單位下三角陣下三角陣可以分解為一系列可以分解為一系列初等初等下三角陣的乘積下三角陣的乘積11111221nnLL LLL 三、三、 三角分解的計算三角分解的計算 Gauss消去法消去法設給定矩陣設給定矩陣1472583610A 1100210301L 取取Gauss變換變換矩陣矩陣則有則有11470360611L

7、A2100010021L 再取再取Gauss變換變換矩陣矩陣21147036001L L AU1112AL L ULU其中其中1112100210321LL L設給定設給定 階矩陣階矩陣n n nijAaR 記記11( )( )()()ijijAaaA Gauss消去法的矩陣表示消去法的矩陣表示1111111( )( )TarAcA 令令Step 1：如果如果1110( )a 1111111( )( )TarAcA 高斯變換高斯變換11110( )Tar 11 1TLIl e 取取12110( ,)Tnlll 其中其中1111112 3( )( ), ,iialina 記記2111( )( )

8、AL A 111 1TLIl e 21111110( )( )nAcIa 111111( )TarcA 1111221 111110( )( )( )( )()TTijarAac rAa 1121111112 3( )( )( )( )( ), ,ijijija aaai jna類似地，對類似地，對 中的中的 部分部分重復重復以上做法以上做法2( )A1 11111( )Tc rAa Step k：第第k步步消元消元過程的計算公式過程的計算公式10( )()( )( )kijkkkijijikkjaaal a 11, ;,ik jn11, , ;, ,i kn j kn 11, ;,ikn j

9、k1 21, ,kn整個整個消元消元過程的矩陣表示過程的矩陣表示 111111221( )nnLLL L AU 上三角上三角矩陣矩陣12( )( ),kikkikkkalikkna計算計算121nAL LLULU 2131321231111nnnlllLlll 111213122232333nnnnnuuuuuuuuuUu 1111112122222( )( )( )( )( )().nnnnnaaaaaa 21l1nl31l32l2nl1, nnl 經(jīng)過經(jīng)過n-1次消元，并將次消元，并將 存放在矩陣零元素位置存放在矩陣零元素位置iklijijikkjaaa a ;ikikkkaaa 1 21

10、, ,knfor12,jkkn for12,ikknforGauss消去法的消元過程算法消去法的消元過程算法Gauss消去法工作量為消去法工作量為3223()nO n 三角分解的計算過程三角分解的計算過程: :11u12u13u1nuStep121l31l1nlStep222u23u2nuStep332l2nlStep433u3nuStep53nlStep6nnuStep2n-1Step2(n-1)先計算先計算 的的行行再計算再計算 的的列列依次依次交替交替進行進行LU對方程組求解對方程組求解, ,只要得到了系數(shù)矩陣的三角分解形式只要得到了系數(shù)矩陣的三角分解形式, ,再利用再利用前代前代算法和

11、算法和回代回代算法解兩個三角方程組即得算法解兩個三角方程組即得. .例例1 1：用用Gauss消去消去法求解下列方程組法求解下列方程組123412312341346262414535xxxxxxxxxxxxxx 解：解：系數(shù)矩陣系數(shù)矩陣6211241011411 013A 131616 6211 1032313151103710910 937 19174111311165911161037L 62111021333379101019174U 6323519174y 1111x 3 1 1. .Th（Gauss消去法的實現(xiàn)條件）消去法的實現(xiàn)條件）全不為全不為零零的充要條件是的充要條件是1 2(

12、)(, , ()iiiaik kn的各階的各階順序主子式順序主子式都不等于都不等于零零，即，即A11121212221201 2, , ()iiiiiiiaaaaaaiknaaa 證明：證明：歸納法證明歸納法證明( (對對k歸納歸納) )設直到設直到k-1成立成立, ,只要證明只要證明121,k 非非零零時，時，非非零零的充要條件是的充要條件是 即可。即可。k 0( )kkka 在歸納假設下，在歸納假設下，Gauss消去法可進行到第消去法可進行到第k-1步步11111221( )kkkALLL L A 1112220( )( )( )kkkAAA 其中其中 是對角元為是對角元為 的的上三角矩陣

13、上三角矩陣11( )kA121112211( )( )(),kkkaaa ( )kk ( )kA矩陣矩陣 的的k階階主子式主子式 是是上三角上三角的的00( )( )kkkkka111121( ) kkkkkkkkLLL均為單位均為單位下三角下三角矩陣矩陣11 21(, ,)jLjk 其中其中11det()jL k 00( )kkkka 因此，若矩陣的各階因此，若矩陣的各階順序主子式順序主子式均不為均不為零零，可以采用可以采用Gauss消元法進行三角分解。消元法進行三角分解。結論得證結論得證若若 的的順序主子式順序主子式 均非奇異均非奇異, ,則存在唯一的則存在唯一的單位下三角單位下三角陣陣

14、和上和上三角陣三角陣 , ,滿足滿足3 1 2. .Th（矩陣三角分解的一個充分條件矩陣三角分解的一個充分條件) )n nAR 121(, ,)k kkARkn n nLR n nUR .ALU 證明可參照定理證明可參照定理3.1.1.3.1.1.2Def給定矩陣給定矩陣 ，如果滿足：，如果滿足：()n nijAaR ijp ()ij 且且jiq ()ji 時，時，0ija 則稱則稱 為上半帶寬為為上半帶寬為 ，下半帶寬為，下半帶寬為 的的帶狀帶狀矩陣，矩陣，Apq稱為稱為帶狀帶狀方程組；方程組；Axb 如果如果 ，則稱，則稱 為為pqt 的的半帶寬半帶寬，tA并稱之為并稱之為等帶寬等帶寬方程

15、組；方程組；21t 為為 的的總帶寬總帶寬。A四、四、 其他的其他的三角分解三角分解1Def如果矩陣如果矩陣 可以分解為一個可以分解為一個單位下三角陣單位下三角陣 和和一個上三一個上三AALU LU角陣角陣 的乘積，即的乘積，即 ，則稱，則稱此分解為此分解為Doolittle分解分解;如果矩陣如果矩陣 可以分解一個下三角陣可以分解一個下三角陣 和單位上三角陣和單位上三角陣 的乘積的乘積,則稱此分解為則稱此分解為Crout分解分解. ALU例如例如512;,npq1210021130011210011400021A 1pq1200021100011200011400021A 上半帶寬為上半帶寬為

16、2，下半帶寬為，下半帶寬為1總帶寬為總帶寬為311a12a11,ta 0021a22a21,ta 22,ta 011 ,ta 0011,tta 12 ,ta 12,tta 2 2 ,ta 21,tta 22,tta , n n ta ,n na2, n ta ,n t na 1,tna 2,tna 01, n ta 半帶寬半帶寬為為t的的等等帶狀帶狀矩陣矩陣的一般形式的一般形式: :3 1 3. .Th （保帶狀保帶狀結構定理）結構定理）設設 為上半帶寬為為上半帶寬為 ，下半帶寬為，下半帶寬為 的的帶狀帶狀矩陣，矩陣，Apq且其且其順序主子式順序主子式 ，則，則01 21(, ,)iin A

17、有唯一的三角分解有唯一的三角分解 ，ALU 其中其中 是是下半帶寬下半帶寬pL為為 的單位下三角陣，的單位下三角陣， 是是上半帶寬上半帶寬為為 的上三角陣。的上三角陣。qU證明證明可根據(jù)前面講過的可根據(jù)前面講過的三角分解三角分解公式公式保帶狀保帶狀結構定理說明：矩陣的三角分解中，結構定理說明：矩陣的三角分解中， 和和LU帶外帶外元素為元素為零零，因此不必計算，且不必參加，因此不必計算，且不必參加求和求和運算運算 三對角三對角線性方程組的三對角算法（線性方程組的三對角算法（追趕法追趕法）三對角三對角線性方程組線性方程組n nAxdAR 其中其中1b1c2a2b2c3a3b3cnanb1nc 1n

18、b 1na A d 1d2d3d1nd nd根據(jù)根據(jù)保帶狀保帶狀結構定理，系數(shù)矩陣可作如下三角分解：結構定理，系數(shù)矩陣可作如下三角分解：ALU 12l 13l1nl111nl L 1u1v2u2v3u3vnu1nv 1nu U 三對角三對角矩陣矩陣 分解的計算公式：分解的計算公式：LU1 21, ,jjjnvc 11ub 1iiialu 12 3, ,iiiiubl vin 1u2l2u3l3unlnu1nu 1nl A1c2c3c1nc 方程組求解的計算公式：方程組求解的計算公式： 解方程組解方程組Lyd 11yd 12,iiiiydl yin 解方程組解方程組Uxy nnnyxu 111,

19、iiiiiyc xxinu “追追”的過程的過程“趕趕”的過程的過程 追趕法追趕法實現(xiàn)的一個實現(xiàn)的一個充分充分條件條件( (補充補充) )3 1 3. .Th 設設 為前述為前述三對角三對角矩陣，且滿足下列條件：矩陣，且滿足下列條件：A11;nnbcba 02 31;, ,iiiiibaca cin 則則 非奇異非奇異，且，且A01 2, ,iuin A特殊情況：如果特殊情況：如果三對角三對角矩陣矩陣 為為嚴格對嚴格對角占優(yōu)角占優(yōu)矩陣，則可以采用矩陣，則可以采用追趕法追趕法求解。求解。例例2 2：用用追趕法追趕法求解三對角求解三對角方程組方程組 , 其中其中:22611271129112111

20、 11,Ad Axd 解：解：注意到本例并注意到本例并不滿足不滿足定理定理3.1.3的條件的條件,但仍然可但仍然可以利用以利用追趕法追趕法來求解來求解.因此因此,定理定理3.1.3的條件僅是的條件僅是充分充分條件條件.221121121121 1A 2205220522052205 2. 105105105105 1.L 2 22 22 22 22U 105105105105 1.L 2 22 22 22 22U Lyb 求解方程組求解方程組 6 10 14 18 10Ty Uxy 求解方程組求解方程組 1 2 3 4 5Tx 3.2 選主元三角分解選主元三角分解 選選主元主元三角分解的思想三

21、角分解的思想三角三角分解過程中存在的問題分解過程中存在的問題Gauss消元法消元法完成的條件是矩陣的各階完成的條件是矩陣的各階順序主子式順序主子式(n=1,2,n-1)均不為零均不為零.三角分解過程中的除法運算要求分母不三角分解過程中的除法運算要求分母不 能太小能太小,否則否則將可能產(chǎn)生將可能產(chǎn)生不穩(wěn)定不穩(wěn)定情況情況.選主元的目的就是為了完成消元且避免不穩(wěn)定情況的發(fā)生選主元的目的就是為了完成消元且避免不穩(wěn)定情況的發(fā)生例例3 3：在在8位制計算機上解方程組位制計算機上解方程組912121012xxxx 要求用要求用三角分解三角分解方法方法計算。計算。9992221110 001 101010.

22、.al 8個個解：解：910101L 911010U 9110Lyby 01Uxyx 小主元小主元 可能導可能導致計算失敗致計算失敗129122101xxxx 交換方程組的兩行交換方程組的兩行22211110 0011. .al 8個個910101L 1101U 21Lyby 11Uxyx 921211110/laa 121xx Gauss全主元全主元三角分解法三角分解法交換交換單位單位矩陣矩陣 的第的第 列列(行行)和第和第 列列(行行)得到的矩得到的矩 pDef(初等初等置換置換矩陣矩陣)qIpqI陣陣 ,稱之為初等置換矩陣稱之為初等置換矩陣. 1pqI p列列q列列()pq 111001

23、1Step 1(k=1)：第第1步選擇步選擇主元主元11111( )( ),maxiji ji j naa 尋求尋求 和和 滿足滿足1i1j然后交換矩陣然后交換矩陣 的第的第 行和行和 行，第行，第 列和列和 列列1( )A11i11j設給定設給定 階矩陣階矩陣n 0,det( )n nijAaRA 記記11( )( )()()ijijAaaA然后按照前面討論的方法進行三角分解然后按照前面討論的方法進行三角分解.用矩陣表示用矩陣表示:12211( )( )( )()ijP A QAa其中其中, 為初等置換矩陣為初等置換矩陣.11,P Q1 111111111111112311111122223

24、21211111332333132111111121311121111231i jiiii njnjnjnnjnnnnnaaaaaaaaaaaaaaaAaaaaaaaaaa ( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ) 1111111 11111111111213111111121222322111113132333311111112321111123jnjnjniiii ji nnnnnjnnaaaaaaaaaaaaaaaAaaaaaaaaaa ( )( )( )( )( )( )

25、( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ) 1111111 1111111111121311222221222322222231323333222221232222123( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ),( )( )( )( )jnjnjniiii ji nnnnnjnnaaaaalaaaalaaaaAlaaaalaaaa 2131111101001nllLl 122111( )( )( )()ijL P A QAa其中其中11111112

26、3( )( ), ,iiialinaa 2111 122( )( )( ), ;,ijijijaal ain jn 第第1步選步選主元主元完成后的計算公式完成后的計算公式:1 122, ;,ijijijaaa ain jn 第第1步選步選主元主元完成后的實際編程計算公式完成后的實際編程計算公式:對對 中右下角的中右下角的 矩陣矩陣重復重復以上做法即可以上做法即可.2( )A11() ()nn Step k：第第k( (k=1,2,n-1) )步選擇步選擇主元主元( )( ),maxkkkkiji jk i j naa 尋求尋求 和和 滿足滿足kikj再按照前面討論的方法進行三角分解再按照前面討

27、論的方法進行三角分解.用矩陣表示整個過程用矩陣表示整個過程:1221 112( )( )( )()kkkkkijL PL P LPA Q QQAa 11( )( )( ), ;,kkkijijikkjaal aikn jkn 第第k步選步選主元主元完成后的計算公式完成后的計算公式:12( )( ),kikikkkkalikkna 然后交換矩陣然后交換矩陣 的第的第 行和行和 行，第行，第 列和列和 列列( )kAkkikkj設上述過程可以進行到第設上述過程可以進行到第r步終止步終止,則有則有221 112rrrL PL P LPAQ QQU 令令1221rrQQ QQ PPP P ,1221

28、1()rrLP L PL P LP 則有結論則有結論:PAQLU 其中其中 為上三角陣為上三角陣, 為為單位下三角單位下三角陣陣,且它的第且它的第 列列對角線以下的元素是由構成對角線以下的元素是由構成 的的Gauss向量向量 做相應做相應的排列得到的的排列得到的,故故 的所有元素之模均不會超過的所有元素之模均不會超過1.LUkkLklL結論具有什么結論具有什么意義意義?令令111112 3( )( )(), ,kkkkkLLLP LP Lkr證明：證明：則有則有( ).rLL 下面利用歸納法證明下面利用歸納法證明 具有如下形式具有如下形式:( )kL( )( )11( )210,1,2,kkk

29、n kLLkrLI 其中其中 是所有元素模均小于是所有元素模均小于1的的 階單位下三角陣階單位下三角陣, 是所有是所有元素模均小于元素模均小于1的的 階矩陣階矩陣, 表示表示 階單位矩陣階單位矩陣.11( )kLk21( )kL()n kk n kI n k k=1時結論顯然成立時結論顯然成立.現(xiàn)假設對現(xiàn)假設對k-1上述結論成立上述結論成立,則則1111111210()( )()()kkkkkkkn kLLP LP LLL 其中其中 是由是由 交換了第交換了第1行和行和 行得到的行得到的, 且且121()kL 1p k 121()kL 1121101001kkkkn knkllLl , (1)

30、(1)1kikikkkkala Gauss全主元全主元三角分解法求解方程組三角分解法求解方程組設已經(jīng)得到三角分解式設已經(jīng)得到三角分解式PAQLU Axb 則原方程組等價于則原方程組等價于PAQQxPb LUQxPb 令令,zQx yPb 則則AxbLUzy 注意到注意到 的計算可在三角分解的過程中來完成的計算可在三角分解的過程中來完成y Gauss全主元全主元三角分解法存在的問題三角分解法存在的問題 選取主元的方法中選取主元的方法中計算量計算量太大太大; 選取主元的過程中用到選取主元的過程中用到列列變換變換,需要記錄需要記錄交換信息交換信息.3 2 1Th . .設設 ，則存在，則存在排列矩陣

31、排列矩陣 ,n nAR 以及單位下三角陣以及單位下三角陣 和上三角陣和上三角陣 ,使得使得LPAQLU n nP QR ,n nLR n nUR 而且而且 的所有元素均滿足的所有元素均滿足 , 的的非零對角元非零對角元的的1ijl U個數(shù)正好等于矩陣個數(shù)正好等于矩陣 的秩的秩.ADef(排列矩陣排列矩陣)有限個初等置換矩陣的有限個初等置換矩陣的乘積乘積稱之為排列矩陣稱之為排列矩陣. 全主元全主元Gauss消去法的算法見教材消去法的算法見教材:算法算法3.2.1 Gauss列主元列主元三角分解法三角分解法Gauss列主元列主元三角分解法與三角分解法與全主元全主元三角分解法的區(qū)別三角分解法的區(qū)別就是在消元過程中只作就是在消元過程中只作行變換行變換, 這樣即可以減少選擇這樣即可以減少選擇主元時的主元時的邏輯計算量邏輯計算量,又可以避免記錄又可以避免記錄交換信息交換信息.Step k：第第k( (k=1,2,n-1) )步選擇步選擇主元主元kkkiki kk i naa ( )( ),max尋求尋求 滿足滿足ki用矩陣表示整個過程用矩陣表示整個過程:1221 1kkkkijL PL P LPAAa ( )( )(