第5章解線(xiàn)性方程組的直接方法PPT課件

1、1第第5 5章章 解線(xiàn)性方程組的直接方法解線(xiàn)性方程組的直接方法5.1 5.1 引言與預(yù)備知識(shí)引言與預(yù)備知識(shí)5.2 5.2 高斯消去法高斯消去法5.3 5.3 高斯主元消去法高斯主元消去法5.4 5.4 矩陣三角分解法矩陣三角分解法5.5 5.5 向量和矩陣的范數(shù)向量和矩陣的范數(shù)5.6 5.6 誤差分析誤差分析5.7 5.7 矩陣的正交三角化及應(yīng)用矩陣的正交三角化及應(yīng)用25.1 引言與預(yù)備知識(shí)引言與預(yù)備知識(shí) 5.1.1 引言引言 實(shí)際中，存在大量的解線(xiàn)性方程組的問(wèn)題。實(shí)際中，存在大量的解線(xiàn)性方程組的問(wèn)題。很多數(shù)值方法到最后也會(huì)涉及到線(xiàn)性方程組的求解很多數(shù)值方法到最后也會(huì)涉及到線(xiàn)性方程組的求解問(wèn)題

2、：如最小二乘法等問(wèn)題。問(wèn)題：如最小二乘法等問(wèn)題。3nnnnnnnbxaxabxaxa11111110)det(A對(duì)線(xiàn)性方程組：對(duì)線(xiàn)性方程組：或者：或者：bAx 我們有我們有GramGram法則：當(dāng)且僅當(dāng)法則：當(dāng)且僅當(dāng)時(shí)，有唯一的解為：時(shí)，有唯一的解為：iiDxD11111111111detiininninninnaabaaDaabaadet( )DA4線(xiàn)性方程組的數(shù)值解法一般有兩類(lèi)：線(xiàn)性方程組的數(shù)值解法一般有兩類(lèi)： 1. 1. 直接法直接法 ( (解低階稠密方程組解低階稠密方程組) ) 經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得方程組精確解的方法經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得方程組精確解的方法( (若若計(jì)算過(guò)程中

3、沒(méi)有舍入誤差計(jì)算過(guò)程中沒(méi)有舍入誤差). ). 但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線(xiàn)性方程組的近似解也只能求得線(xiàn)性方程組的近似解. . 2. 2. 迭代法迭代法 ( (解低大型稀疏方程組解低大型稀疏方程組) ) 是用某種極限過(guò)程去逐步逼近線(xiàn)性方程組精確解的方法是用某種極限過(guò)程去逐步逼近線(xiàn)性方程組精確解的方法. . 本章介紹直接法。本章介紹直接法。5 （A A）特殊矩陣）特殊矩陣 設(shè)設(shè) .R)(nnijaA (1) (1) 對(duì)角矩陣對(duì)角矩陣 (2) (2) 三對(duì)角矩陣三對(duì)角矩陣.01ijaji，如果當(dāng) (3) (3) 上三角矩陣上

4、三角矩陣 .0ijaji，時(shí)如果當(dāng) (4) (4) 對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣 .TAA如果.0ijaji，時(shí)如果當(dāng)復(fù)習(xí)線(xiàn)性代數(shù)中的相關(guān)知識(shí)：復(fù)習(xí)線(xiàn)性代數(shù)中的相關(guān)知識(shí)：6 (5) (5) 對(duì)稱(chēng)正定矩陣對(duì)稱(chēng)正定矩陣 , (a) AAT如果. 0)(,R (b) AxxxAx,xTn對(duì)任意非零向量 (6) (6) 正交矩陣正交矩陣 .T1AA如果 (7) (7) 初等置換陣初等置換陣 由單位矩陣由單位矩陣 交換第交換第 行與第行與第 行行( (或交換第或交換第 列與列與第第 列列) )，得到的矩陣記為，得到的矩陣記為 , ,且且 IijijijIAAIij（為交換（為交換 第第 行與第行與第 行得到的矩陣）

5、；行得到的矩陣）；Aij（為交換（為交換 第第 列與第列與第 列得到的矩陣）；列得到的矩陣）；iAjBAIij (8) (8) 置換陣置換陣由初等置換陣的乘積得到的矩陣由初等置換陣的乘積得到的矩陣. . 7 定理定理1 1設(shè)設(shè) ，nnRA(1) (1) 對(duì)任何對(duì)任何 方程組方程組 有惟一解有惟一解. . ,RnbbAx 則下述命題等價(jià)：則下述命題等價(jià)： (2) (2) 齊次方程組齊次方程組 只有惟一解只有惟一解 . .0Ax0 x(4) (4) 存在存在. . 1A(5) (5) 的秩的秩A.)(ranknA.0)det(A(3)(3)(B) (B) 幾個(gè)重要定理：幾個(gè)重要定理：8 定理定理2

6、 2設(shè)設(shè) 為對(duì)稱(chēng)正定陣，則為對(duì)稱(chēng)正定陣，則 nnRA (1) (1) 為非奇異矩陣，且為非奇異矩陣，且 亦是對(duì)稱(chēng)正定陣亦是對(duì)稱(chēng)正定陣. . A1A (2) (2) 記記 為為 的順序主子陣，則的順序主子陣，則 kAA).,2, 1(1111nkaaaakkkkkA),2, 1(nkkA亦是對(duì)稱(chēng)正定矩陣，亦是對(duì)稱(chēng)正定矩陣，其中其中 (3) (3) 的特征值的特征值 A).,2, 1(0nii (4) (4) 的順序主子式都大于零，即的順序主子式都大于零，即 A)., 2 , 1(0)det(nkkA9 定理定理3 3設(shè)設(shè) 為對(duì)稱(chēng)矩陣為對(duì)稱(chēng)矩陣. . nnRA), 2 , 1(nk或或 的特征值的

7、特征值A(chǔ)),2, 1(0nii0)(detkA如果如果則則 為為A對(duì)稱(chēng)正定陣對(duì)稱(chēng)正定陣. .10下面三種方程組我們可以直接解出：下面三種方程組我們可以直接解出：niabxaaadiagAiiiinn, 1,),(2211n次運(yùn)算次運(yùn)算nilxlbxllllllAiiijjijiinnnn, 1,1121222111(n1)n/2次運(yùn)算次運(yùn)算預(yù)備知識(shí)（補(bǔ)充）：預(yù)備知識(shí)（補(bǔ)充）：111 ,122211211niuxubxuuuuuuAiinijjijiinnnn(n1)n/2次運(yùn)算直接法的基本思想就是對(duì)方程組做些直接法的基本思想就是對(duì)方程組做些等價(jià)的變換等價(jià)的變換，變，變?yōu)槲覀円阎臑槲覀円阎?

8、 3種類(lèi)型之一，而后求解。種類(lèi)型之一，而后求解。12思路：首先將A化為上三角陣，再回代求解 。nnnnnnnbaaabaaabaaa21222221111211=)()()3(3)3(3)3(33)2(2)2(2)2(23)2(2211131211000000nnnnnnnnbabaabaaabaaaa5.2 高斯消去法13步驟如下：第一步：11111(),2,iiamiina 第 行第 行nnnnnnnbaaabaaabaaa21222221111211)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa運(yùn)算量： (n-1)*(1+n)14)3()3

9、()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(221113121100000nnnnnnnbaabaabaaabaaaa運(yùn)算量： (n-2)*(1+n-1)=(n-2)n第二步：(2)22(2)222(),3,iiamiina 第 行第 行)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa15第k步：( )( )k(),1,kikikkkkamiikna 第 行第 行類(lèi)似的做下去，我們有：運(yùn)算量： (nk)*(1nk1)=(nk)(nk2)()()3(3)3(3)3(33)2(2)2(2)2(23)2(2211131211000

10、000nnnnnnnnbabaabaaabaaaan1步以后，我們可以得到變換后的矩陣為：16因此，消元過(guò)程總的運(yùn)算量為：11)2)(nkknkn加上 解上述上三角陣的運(yùn)算量(n+1)n/2，總共為：)(33323nOnnn17在高斯消元法中，我們注意到，計(jì)算過(guò)程中)(kkka處在被除的位置，所以，Gauss消元法的可行條件為：0)(kkka就是要求A的所有順序主子式均不為0，即niaaaaiiii, 1, 0det1111因此，有些有解的問(wèn)題，不能用Gauss消元法求解。因此整個(gè)計(jì)算過(guò)程要保證它不為0。（證明參見(jiàn)課本P146定理6）18Gauss消元法的第k步：( )( )k(),1,kik

11、ikkkkamiikna 第 行第 行從矩陣?yán)碚搧?lái)看，相當(dāng)于左乘矩陣11,1,11iknkiknmm利用上面矩陣行變換與左乘的關(guān)系分析高斯消元法：矩陣的LU分解：19因此，整個(gè)Gauss消元法相當(dāng)于左乘了一個(gè)單位下三角陣211111111kknnknnmLmmmmL AU即，20那么，211111111kknnknnmLmmmm因此，存在L，使得其中L為單位下三角陣，U為上三角陣。1( )ALULU其中，ALU21注意：分解的理論由Gauss消元得出，因此分解能夠進(jìn)行的條件與Gauss消元一樣22 定理設(shè) 為 階非奇異陣，An 證明現(xiàn)在證明惟一性， 設(shè) ,11ULLUA其中 為單位下三角矩陣，

12、 為上三角矩陣. 1,LL1,UU(矩陣的LU分解)如果 的A順序主子式),2, 1(0niiD則 可分解為一個(gè)單位A下三角矩陣 和一個(gè)上三角矩陣 的乘積，LU且這種分解是惟一的. 根據(jù)以上高斯消去法的矩陣分析，存在性已得證， 矩陣的LU分解定理：23.1111UULL上式右邊為上三角矩陣，左邊為單位下三角矩陣，從而上式兩邊都必須等于單位矩陣， 由于 存在，故 11U,11UULL故 惟一性得證. 24200140111112010001A.LU 例,122140111A可分解為對(duì)于矩陣 25后面將討論兩個(gè)問(wèn)題：1、矩陣的LU分解有什么用？2、矩陣LU分解的算法？26在高斯消元法中，我們注意到

13、，計(jì)算過(guò)程中)(kkka處在被除的位置，另外，如果某個(gè))(kkka很小的話(huà)，會(huì)引入很大的誤差。因此整個(gè)計(jì)算過(guò)程要保證它不為0。5.3 高斯主元素消去法27例：以8位機(jī)器上解方程組 211021219xxxx/* 精確解為 和 */.1000.00. 1101191 x8個(gè).8999.99. 0212 xx8個(gè)用高斯消元法計(jì)算：911212110/ aam999212210101010.0 . 011 ma8個(gè)92121012 mb 9991010011100, 112 xx小主元可能導(dǎo)致計(jì)算失敗。28列主元消元法：在Gauss消元第k步之前，做如下的事情：|max)()(kjkkiknikaa

14、若交換 k 行和 j 行行的交換，不改變方程組的解，同時(shí)又有效地克服了Gauss消元的缺陷,)()()2(2)1(121)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnkknkknnknkkknkkknknkbbbbxxxxaaaaaaaaaaa29 高斯高斯- -若當(dāng)消去法：若當(dāng)消去法： 高斯消去法中，若同時(shí)消去對(duì)角線(xiàn)下方和上方的元素， 設(shè)用高斯-若當(dāng)消去法已完成 步， 化為等價(jià)1kbAx 方程組 ，其中)()(kkbxA.101001)(,1,1,1222111)()(nnnknknkkkknkkknknkkkbaabaabaabaabaabA這種方法稱(chēng)為

15、高斯-若當(dāng)(Gauss-Jordan)消去法. 30上述過(guò)程結(jié)束后有 .111)()(21)1()1(nkkbbbbAbA 用高斯-若當(dāng)方法將 約化為單位矩陣，計(jì)算解就在常數(shù)項(xiàng)位置得到，用不著回代求解，計(jì)算量大約需要 次乘除法，比高斯消去法大。 A2/3n高斯-若當(dāng)方法可用來(lái)求逆矩陣。315.35.3 矩陣三角分解法矩陣三角分解法 5.3.1 直接三角分解法直接三角分解法 直接從矩陣直接從矩陣 的元素得到計(jì)算的元素得到計(jì)算 元素的遞推公式，元素的遞推公式，而不需任何中間步驟，而不需任何中間步驟，這就是這就是直接三角分解法直接三角分解法. . AUL, 一旦實(shí)現(xiàn)了矩陣一旦實(shí)現(xiàn)了矩陣 的的 分解，

16、那么求解分解，那么求解 的問(wèn)的問(wèn)題就等價(jià)于求解兩個(gè)三角形方程組題就等價(jià)于求解兩個(gè)三角形方程組 ALUbAx 求求,bLy ;y 求求 ,yUx . x32 設(shè)設(shè) 為非奇異矩陣，且有分解式為非奇異矩陣，且有分解式 A,LUA .111222112112121nnnnnnuuuuuulllA其中其中 為單位下三角陣，為單位下三角陣， 為上三角陣，即為上三角陣，即 LU三個(gè)問(wèn)題：三個(gè)問(wèn)題：1 1、分解公式、分解公式2 2、計(jì)算量、計(jì)算量3 3、存儲(chǔ)問(wèn)題、存儲(chǔ)問(wèn)題33比較第比較第2行：行：jjjjjjulaunjuula1211221212 , 2 比較第比較第2列：列：22121222221212u

17、 , 3 uuulalnillaiiiiii比較第比較第k行：行：1111 , krrjkrkjkjkjkrrjkrkjulaunkjuula比較第比較第k列：列：kkkrrkirikikkkikkrrkirikuulalnkiulula1111 , 1 k-1次次k-11次次比較第比較第1行：行：jjjjaunjua1111 , 1 比較第比較第1列：列：11111111 , 2 uualnilaiiii 的元素可以由的元素可以由 步直接計(jì)算定出，其中第步直接計(jì)算定出，其中第 步步定出定出 的第的第 行和行和 的第的第 列元素列元素. . UL,nrUrLr分解公式分解公式: :34兩次回代

18、兩次回代1 , , , 1 , 111niuxuyxniylbyiinijjijiiijjijii);, 1,(11nrriulaurkkirkriri), 2(/), 2 , 1(111111niualniauiiii);, 1(/ )(11nrnriuulalrrrkkrikirir且分解公式：分解公式： 以上的分解公式又稱(chēng)為以上的分解公式又稱(chēng)為杜利特爾分解杜利特爾分解. . 35運(yùn)算量為：運(yùn)算量為：332) 1(2) 1()() 1)(1(2311nnnnnnnkknkknnk 直接分解法大約需要直接分解法大約需要 次乘除法，和高斯消去法次乘除法，和高斯消去法計(jì)算量基本相同計(jì)算量基本相同

19、. . 3/3n36 當(dāng)當(dāng) 計(jì)算好后計(jì)算好后 就不用了，故可將就不用了，故可將 仍存放在仍存放在 的相應(yīng)位置的相應(yīng)位置. . riuriariuria44434241343332312423222114131211aaaaaaaaaaaaaaaaA最后在存放最后在存放 的數(shù)組中得到的數(shù)組中得到 的元素的元素. . UL,A 存儲(chǔ)問(wèn)題：存儲(chǔ)問(wèn)題：44434241343332312423222114131211ullluulluuuluuuu 當(dāng)當(dāng) 計(jì)算好后計(jì)算好后 就不用了，故可將就不用了，故可將 仍存放在仍存放在 的相應(yīng)位置的相應(yīng)位置. . irlirairlria37 例例.20181451

20、3252321321xxx 解解用直接三角分解法解用直接三角分解法解 用分解公式計(jì)算得用分解公式計(jì)算得 , 11111au, 11/2/112121ual, 122512212222ulau,21212au,31313au，31/3/113131ual,432213212323ulau,51/ )231(/ )(2212313232uulal.24)4()5(335233213313333ululau382400410321153012001A回代求解回代求解 T(14,18,20) ,bLyT(14, 10, 72) ,yUx.LU從而從而,)72,10,14(Ty得得回代求解回代求解.)3

21、,2, 1(Tx得得39 5.3.25.3.2 平方根法平方根法 平方根法是利用平方根法是利用對(duì)稱(chēng)正定矩陣對(duì)稱(chēng)正定矩陣的三角分解而得到的的三角分解而得到的求解對(duì)稱(chēng)正定方程組的一種有效方法求解對(duì)稱(chēng)正定方程組的一種有效方法. . 設(shè)設(shè) 為對(duì)稱(chēng)矩陣，且為對(duì)稱(chēng)矩陣，且 的所有順序主子式均不為零，的所有順序主子式均不為零，AA那么，那么， 可惟一分解為可惟一分解為 A.111222112112121nnnnnnuuuuuulllA40111222222311111122211uuuuuuuuuuunnnnU其中其中 為對(duì)角陣，為對(duì)角陣， 為單位上三角陣為單位上三角陣. . D0U.0LDULUA又又 T

22、AA 于是于是 ,0DU),(TT0DLU由分解的惟一性由分解的惟一性, , 得得 .T0LU于是于是, ,可以得到對(duì)稱(chēng)矩陣可以得到對(duì)稱(chēng)矩陣 的分解式的分解式 A.TLDLA 為了利用為了利用 的對(duì)稱(chēng)性，將的對(duì)稱(chēng)性，將 再分解為再分解為 AU41 定理定理設(shè)設(shè) 為為 階對(duì)稱(chēng)陣，階對(duì)稱(chēng)陣，An且且 的所有順序主子式均不為零，的所有順序主子式均不為零，A則則 可惟一分解為可惟一分解為 A,TLDLA 其中其中 為對(duì)角陣，為對(duì)角陣， 為單位下三角陣為單位下三角陣. . DL( (對(duì)稱(chēng)陣的三角分解定理對(duì)稱(chēng)陣的三角分解定理) )42ndd1Dnndddd11,2121DD那么那么 TLDLA 其中其中

23、為下三角矩陣為下三角矩陣. . 211LDL T2121LDLDT2121)(LDLD,T11LL 設(shè)設(shè) 為對(duì)稱(chēng)正定矩陣，則在分解式為對(duì)稱(chēng)正定矩陣，則在分解式 中，中， 的對(duì)角元素的對(duì)角元素 均為正數(shù)均為正數(shù). . ATLDLA Did43 定理定理如果如果 為為 階對(duì)稱(chēng)正定矩陣，則存在一個(gè)實(shí)的非奇異下三階對(duì)稱(chēng)正定矩陣，則存在一個(gè)實(shí)的非奇異下三角陣角陣An,L( (對(duì)稱(chēng)正定矩陣的三角分解或?qū)ΨQ(chēng)正定矩陣的三角分解或Cholesky分解分解) ),TLLA 使使當(dāng)限定當(dāng)限定 的對(duì)角元素為正時(shí)，這種的對(duì)角元素為正時(shí)，這種L分解是惟一的分解是惟一的. . 44 可以用直接分解方法來(lái)確定計(jì)算可以用直接分

24、解方法來(lái)確定計(jì)算 元素的遞推公式元素的遞推公式. . L因?yàn)橐驗(yàn)?,2221211121222111nnnnnnnnllllllllllllA其中其中).,2, 1(0nilii45 對(duì)于對(duì)于 nj,2, 1.21112jkjkjjjjlal根據(jù)矩陣乘法，按等式兩邊對(duì)應(yīng)元素相等可得分解公式：根據(jù)矩陣乘法，按等式兩邊對(duì)應(yīng)元素相等可得分解公式：)., 1(/11njilllaljjjkjkikijij46求解求解 即求解兩個(gè)三角形方程組：即求解兩個(gè)三角形方程組： ,bAx ;,1ybLy求）（).1 , 1,(/1nnilxlbxiinikkkiii).,2, 1(/11nilylbyiiikki

25、kii.,)2(TxyxL求回代解得：回代解得：47 當(dāng)求出當(dāng)求出 的第的第 列元素時(shí)，列元素時(shí)， 的第的第 行元素也算出行元素也算出. . LjTLj所以平方根法約需所以平方根法約需 次乘除法，大約為一般直接分解次乘除法，大約為一般直接分解法計(jì)算量的一半法計(jì)算量的一半. . 6/3n運(yùn)算量：運(yùn)算量：48存儲(chǔ)問(wèn)題：存儲(chǔ)問(wèn)題：11212212nnnnaaaaaa 由于由于 為對(duì)稱(chēng)陣，因此在計(jì)算機(jī)實(shí)現(xiàn)時(shí)只需存儲(chǔ)為對(duì)稱(chēng)陣，因此在計(jì)算機(jī)實(shí)現(xiàn)時(shí)只需存儲(chǔ) 的的下三角部分下三角部分. .AA 下三角部分共需存儲(chǔ)下三角部分共需存儲(chǔ) 個(gè)元素，可按行主序個(gè)元素，可按行主序用一維數(shù)組存放，用一維數(shù)組存放，2/)1(

26、nn即即.,)2/)1(21222111nnnnaaaaaannA矩陣元素矩陣元素 在一維數(shù)組中表示為在一維數(shù)組中表示為ija()A iij(1)/ 2iiii 49 用平方根法解對(duì)稱(chēng)正定方程組時(shí)，需要用到開(kāi)方運(yùn)算用平方根法解對(duì)稱(chēng)正定方程組時(shí)，需要用到開(kāi)方運(yùn)算. .因此不常用。為了避免開(kāi)方，還是用如下分解式因此不常用。為了避免開(kāi)方，還是用如下分解式, , ,TLDLA 即即 .1111112121212121nnnnnllldddlllA改進(jìn)的平方根法：改進(jìn)的平方根法：50由矩陣乘法，比較對(duì)應(yīng)的元素可得到：由矩陣乘法，比較對(duì)應(yīng)的元素可得到：nnnnnnnnnnndlddldlddlllaaaaaaaaa2221121112121212222111211111也就是也就是51);1,2, 1(/11ijdldlaljjkjkkikijij1,2,in 對(duì)于對(duì)于 .112ikkikiiidlad).1 ,2, 1(/;/1nixldyxdyxnikkkiiiinnn).,2(;1111niylbybyikkikii 以上的公式被稱(chēng)為以上的公式被稱(chēng)為改進(jìn)的平方根法改進(jìn)的平方根法. . 回代求解回代求解 計(jì)算公式計(jì)算