線性方程組的數值解法素材PPT學習教案

1、會計學1線性方程組的數值解法素材線性方程組的數值解法素材 當階數較高時用這種方法求解是不現實的。 階行列式有 項，每項又是 個數的乘積。對較大的 ，其計算量之大，是一般計算機難以完成的。而且，這時的舍入誤差對計算結果的影響也較大。n!nnn例如，求解一個20階線性方程組，用加減消元法需3000次乘法運算，而用克萊姆法則要進行 次運算，如用每秒1億次乘法運算的計算機要30萬年。209.7 10第2頁/共93頁線性代數方程組的計算機解法常用方法：直接法 迭代法消去法消去法矩陣三角分解法矩陣三角分解法第3頁/共93頁第4頁/共93頁3.1 消去法消去法的基本思想：是通過將一個方程乘或除以某個常數，以

2、及將兩個方程相加減，逐步減少方程中的變元數，最終使每個方程只含一個變元，從而得出所求的解。消去法常用方法：高斯消去法選主元消去法高斯約旦消去法第5頁/共93頁消去法3.1 高斯消去法 按自然順序進行的消元法第6頁/共93頁例例 1 用高斯消元法求解方程組用高斯消元法求解方程組 12312312328214613225xxxxxxxxx解解 用第一個方程削去后兩個方程中的用第一個方程削去后兩個方程中的 得得 ,1x 9962214282232321xxxxxx再用第再用第2個方程消去第個方程消去第3個方程中的個方程中的 得得,2x 18962214282332321xxxxxx第7頁/共93頁最

3、后，經過回代求得原方程組的解為最后，經過回代求得原方程組的解為 52281412262918321323 xxxxxx例例 2 解方程組解方程組 02115472321321321xxxxxxxxx第8頁/共93頁解：消元 0121111547112 3235 . 2rr 620033307112 5 . 35 . 05 . 203330711231212124rrrr 回代得, 3263 x, 233332 xx127321 xxx第9頁/共93頁消去法 1ijabAx 11bxA 1A 1b 1ibnji, 2 , 1, 1 0111 a niaamii, 3 , 2,111111 第10

4、頁/共93頁i1im n1x 22bxA 22211212222222211112111nnnnnnnbbbxxxaaaaaaa njibmbbamaaiiijiijij, 3 , 2,1111211112第11頁/共93頁 k 12 nk1 k kkbxA knnknkkknkkknnkaaaaaaaaaaA2222322211112111 knkkkbbbbb2211 0 kkka nkiaamkkkkikik, 1, 第12頁/共93頁 0 kkka1 n nnbxA nnnnnnnnbbbxxxaaaaaa2211212222211112111 第13頁/共93頁 0 nnna11,x

5、xxnn 1 , 2 , 1 ,1 niaxabxabxiiinijjiijiiinnnnnn nkakkk, 2 , 1, 第14頁/共93頁 0 kkka1, 2 , 1 nk nkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik, 2, 1, 11)()( 1 , 2 , 1 ,1 niaxabxabxiiinijjiijiiinnnnnn第15頁/共93頁nkkiaaaikkkik, 2, 1,第16頁/共93頁nkkjibbabaaaaijikiijkjikij, 2, 1, 1 , 2 , 1 1 nibaxabbabiiinijjijinnnnn

6、bbb,21nxxx,21第17頁/共93頁定理2 Ax=b 可用高 斯消元法求解的充分必要條件是：系數矩陣 A 的各階順序主子式均不為零。高斯消元法的條件定理1 如果在消元過程中A的主元素 (k=1,2,n) ,則可通過高斯消元法求出Ax=b 的解。0)( kkka1110Da11110,2,3,kkkkkaaDknaa引理 A的主元素 (k=1,2,n) 的充要條件是矩陣A的各階順序主子式不為零，即0)( kkka第18頁/共93頁33n高斯消去法的計算量無法進行；或| akk(k) |1時，帶來舍入誤差的擴散。如何處理？ 0)( kkka第19頁/共93頁例例 1 解方程組解方程組 00

7、00. 10000. 10000. 10001. 20000. 30003. 02121xxxx 0 .66660 .99990001. 20000. 30003. 0221xxx解法一解法一 用高斯消元法求解（取用高斯消元法求解（取5位有效數字），用位有效數字），用第第 一個方程消去第二個方程中的一個方程消去第二個方程中的,1x3.1.2 高斯主元素消元法第20頁/共93頁因而再回代，得因而再回代，得 216666.00.66679999.02.00013.00000.666700.0003xx而精確值為而精確值為 顯然該解與精確值相差顯然該解與精確值相差太遠，為了控制誤差，采用另一種消元過

8、程。太遠，為了控制誤差，采用另一種消元過程。32,3121 xx解法二解法二 為了避免絕對值很小的元素作為主元，先交為了避免絕對值很小的元素作為主元，先交換兩個方程，得到換兩個方程，得到 0001. 20000. 30003. 00000. 10000. 10000. 12121xxxx第21頁/共93頁消去第二個方程中的消去第二個方程中的 得得 ,1x 9998. 19997. 20000. 10000. 10000. 1221xxx再回代，解得再回代，解得 3333. 06667. 00000. 10000. 16667. 09997. 29998. 112 xx結果與準確解非常接近。這個

9、例子告訴我們，在采用高斯消元法解方程組時，用做除法的小主元素可能使舍入誤差增加，主元素的絕對值越小，則舍入誤差影響越大。固應避免采用絕對值小的主元素，同時選主元素盡量的大，可使該法具有較好的數值穩(wěn)定性。第22頁/共93頁列主元素消元法kkakka第23頁/共93頁例：例：求解線性方程組求解線性方程組 000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0321xxx解法一：用列主元素消元法，方程組增廣矩陣為：解法一：用列主元素消元法，方程組增廣矩陣為： 000. 3643. 5072. 1000. 200

10、0. 2623. 4712. 3000. 1000. 1000. 3000. 2001. 0A第24頁/共93頁 002. 1003. 3001. 20500. 0801. 1176. 30000. 3643. 5072. 1000. 2000. 1000. 3000. 2001. 0000. 2623. 4712. 3000. 1000. 3643. 5072. 1000. 2 687. 0868. 100500. 0801. 1176. 30000. 3643. 5072. 1000. 2回代計算解為回代計算解為 Tx3678. 0 ,05113. 0,4990. 0* 第25頁/共93頁

11、全選主元素消元法 第26頁/共93頁第27頁/共93頁回代計算得回代計算得0.367, 0.0511, 0.491Ty從而原方程的解為從而原方程的解為 Tx367. 0 ,051. 0,491. 0 第28頁/共93頁3.1.3 高斯-約當(Jordan)消去法 消元時將主元上方元素也消為0，最后系數矩陣化為對角矩陣。這種算法只有消元，沒有回代，這種方法稱做高斯-約當(Jordan)消去法。 第29頁/共93頁例 用高斯-約當消去法解下列線性方程組 123123123223347712457xxxxxxxxx 解解 對線性方程組第 1 次消元，0211a，確定乘數 212111422ama，3

12、13111212ama 第30頁/共93頁) 1 ()3() 1 ()2(3121mm12312312322330350684xxxxxxxxx 第2次 消 元 ，2230a， 確 定 乘 數12122221.53ama，323222623ama，有 第31頁/共93頁1232(1)(2)(3)(2)mm12323371020330350066xxxxxx 第 3 次消元，3360a，確定乘數1313337/36ama，23233316ama有第32頁/共93頁1323(1)(3)(2)(3)mm12323200403060066xxxxx 解出 1232,2,1xxx 第33頁/共93頁消去

13、法小結第34頁/共93頁3.2 矩陣三角分解法nbAx n1 nnbxA LULUA ALU第35頁/共93頁ALUUALALU 1112121nnlll 1112112nnuuu 第36頁/共93頁1131313111311121212111211111232322131211323121333231232221131211)3 , 2 , 1(11113,ualluaualluajauuakuuuuuulllaaaaaaaaanULjjjj得由；得由時：為例的各元素，以此分解在于如何算出第37頁/共93頁)(32233213313333332332133133221231323223321

14、2313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得時：由得由；得由；得時：杜里特爾分解第38頁/共93頁niulaniuaiiii, 3 , 2, 2 , 1,111111 由矩陣乘法規(guī)則LUA nnnnnnnnnnirrinnuuuuuulllaaaaaaaaaaa222112112121212222111211111由此可得 的第一行元素和 的第一列元素niualniauiiii, 3 , 2, 2 , 1,111111 UL第39頁/共93頁 當已得出 的前 行元素和 的前 列元素，

15、則對于 ，由rruirlrkkruiklnkkruiklirariurkkiurklnkkiurklria 111111nrri, 1, U1 rL1 r又可得計算 的第 行元素和 的第 列元素的公式:nrrirrurkkruiklirairlnrrirkkiurklriariu, 2, 1 ,11, 1, ,11 UrLr第40頁/共93頁例例 求矩陣求矩陣2144416512A 的LU分解。 u11=2 u12=1 u13=4 1213532 l22421 l32631 l212422u231247u 7)7(1431233u第41頁/共93頁所以所以2141002144412100276

16、512311007 700720412113012001UL第42頁/共93頁a11 a12 a1k a1n u11 u12 u1k u1n 第1框 a21 a22 a2k a2n l21 u22 u2k u2n 第2框 ak1 ak2 akk akn lk1 lk2 ukk ukn 第k框 an1 an2 ank ann ln1 ln2 lnk unn 第n框 按下圖所示順序逐框進行,先求 u 后求 l。矩陣三角分解算法總結：第43頁/共93頁 有了矩陣 A 的LU分解計算公式，當求解線性方程組 時，等價于求解 。這時可歸結為利用遞推計算相繼求解兩個三角形方程組（系數矩陣為三角矩陣）。用順代

17、，由 求出 ，再利用回代，由 求出 。bAx bLUx bLy yUx xy3.2.2 解線性方程組的三角分解法 用杜里特爾三角分解法解線性方程組 的計算方法：bAx 第44頁/共93頁 對于 ，計算 和 。 求解 ，即計算 求解 ，即計算。nr, 3 , 2 nrriuri, 1, nrrilir, 2, 1, bLy niylbybyikkikii, 3 , 2,1111 yUx 1 , 2 , 1,1 niuxuyxuyxiinikkikiinnnn 計算 和 。niui, 2 , 1,1 nili, 3 , 2,1 第45頁/共93頁 30191063619134652. 1321xx

18、x方程組方程組試用杜里特爾分解求解試用杜里特爾分解求解例例第46頁/共93頁。，；，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuuuuulllALU第47頁/共93頁LUAululaukuulalulauulauk473652143121434/ )(7)6(21935213223321331333322123132321321232312212222所以時：，時：第48頁/共93頁TyyyyyyybLy)4 , 1,10(43034, 12019,1030191014312112321321即

19、得）解（、解方程組第49頁/共93頁。所以方程組的解為所以方程組的解為解得：解得：解解TxxxxxxxyUx)1 , 2 , 3(3, 2,2(123321 第50頁/共93頁第51頁/共93頁用LU 直接分解的方法求解線性方程組的計算量為 ，和高斯消去法的計算量的數量級基本相同。33n當方程組系數矩陣不變，只有右側向量b變化時，用LU分解法比消去法速度快。因為右側向量b的改變不影響LU的變化。高斯消去法和LU分解法是等價的，其關鍵是把一般方程組變?yōu)槿欠匠探M，只是實現途徑不同。第52頁/共93頁3.4 向量與矩陣的范數向量與矩陣的范數 問題的提出 向量范數概念是三維

20、歐氏空間中向量長度概念的推廣,在數值分析中起著重要作用. 為了研究線性方程組近似解的誤差估計和迭代法的收斂性，我們需要對 （n維向量空間）中向量及 （ 維矩陣空間）中矩陣的“大小”及“距離”引進某種度量向量與矩陣范數的概念.nRnn nnR 第53頁/共93頁平面向量 x 大小：用 距離 反映。2221xxx 3.4 向量與矩陣的范數向量與矩陣的范數 引入范數的目的：實數大小：用絕對值反映復數大?。河媚７从掣呔S空間向量 x “大小” 用 反映？ 將度量長度數值的計算方法引入高維空間，用來反映空間向量的大小，就是范數的概念。第54頁/共93頁 非負性 |x|0 ，等號僅當 x=0 時成立； 齊次

21、性 對任何實數 , | x|=| | |x|； 三角不等式 |x+y| |x| +|y| ； 則稱 |x| 為向量 x 的范數。定義 對任意 n 維向量 x Rn，若對應非負實數 |x| ， 滿足 3.4.1 向量的范數第55頁/共93頁 由定義可知，向量 的范數 是按一定規(guī)律與 對應的實數，該實數的值沒有確定，但只要滿足這三個條件，這個實數就是向量 的一種范數。因此定義中的三個條件稱為范數公理。xxxx當 時，0 x1 xx向量范數 有如下性質x證：利用條件，有11 xxxxxx yxyx yyxyyxx yxyx 證：第56頁/共93頁它們分別叫做向量的-范數、1-范數、2-范數、p -范

22、數（0p+）。 p -范數是以上范數的統(tǒng)一表達形式。常用的向量范數: 滿足定義的范數不是唯一的.inixx 1maxnxxxx 211222212nxxxx ppnpppxxxx121)( 設設 x = ( x1 , x2 , , xn)T ，常用的向量范數有，常用的向量范數有 第57頁/共93頁 對于范數，有當 時，有 ， 只有當 時，才有 對任意實數 ，因為 ，所以 。對任意向量 ，有 0 x0max1 inixx0 x0 x Tnxxxx ,21 xxxxiiini maxmax1nRy 111maxmaxmaxmaxiiiiiii nii ni nxyxyxyxyxy iixxmax

23、例：范數的證明第58頁/共93頁可以證明這幾種范數滿足下述關系可以證明這幾種范數滿足下述關系 xnxxxnxx21事實上，對 Rn 上任意兩種向量范數 |x| , |x| ，都存在與 x 無關的正常數 c1 , c2 使 這種性質稱為向量范數的等價性。 xcxxc21 第59頁/共93頁12abac xxcx|x|a , |x|bRn第60頁/共93頁設給定 中的向量序列 ，其中 若對任何 ，都有，則向量 稱為向量序列 的極限，或者說向量序列收斂于向量 ，記為：nR kx Tknkkkxxxx,21 nii, 2 , 1 *limikixx Tnxxxx*2*1*, kx*x *limxxkk

24、 向量收斂的定義：第61頁/共93頁向量序列收斂性定理： 向量序列收斂 (即 )的充要條件是 ，其中 為向量的任一種范數。 *limxxkk 0lim* xxkk 按不同方式規(guī)定的范數,其值一般不同。但在各種范數下考慮向量序列收斂性的結論是一致的。即向量序列如對某一種范數收斂則對其它范數也收斂，且有相同的極限。這樣，在研究某一具體問題時，可以選擇一較易簡單的范數。第62頁/共93頁3.4.2 矩陣的范數第63頁/共93頁 定義：設 ， ，定義矩陣 的范數 對于每一種向量范數 ，相應的矩陣范數 為其中 是指 的最大可能值。即遍取所有不為0的 ，比值 中最大的，定義為 的矩陣范數。 nnRA nR

25、x AxAxA0 x maxpxppxpxAxA0max pAmaxxAxxxAxA第64頁/共93頁矩陣范數的性質： ,且僅當 時， ； 對任意實數 ， ； 對同維方陣 ，有: 0 A0 A0 A AA B ,BABA BAAB 相容性條件： 由矩陣范數的定義可直接得到 ，即有 ，稱為相容性條件。即所給的矩陣范數與向量范數是相容的。xAxA xAAx 證明 p92第65頁/共93頁矩陣范數與向量范數的關系： 矩陣范數與向量范數密切相關，向量范數有相應的矩陣范數，即： （如 ）pxpAxAp1max , 2 , 1pxxAxAxAxx00maxmax AxxAxxA 第66頁/共93頁矩陣范數

26、與向量范數的關系： 矩陣范數與向量范數密切相關，向量范數有相應的矩陣范數，即： （如 ）pxpAxAp1max , 2 , 1p常用的矩陣范數有（矩陣范數的求?。┏Ｓ玫木仃嚪稊涤校ň仃嚪稊档那笕。?(maxmaxmax211111AAAaAaATniijnjnjijni （矩陣的行范數）（矩陣的行范數）（矩陣的列范數）（矩陣的列范數）)(maxmaxmax211111AAAaAaATniijnjnjijni （矩陣的行范數）（矩陣的行范數）（矩陣的列范數）（矩陣的列范數）它們分別叫做矩陣的-范數、1-范數、譜范數。 max()TA ATA Amax2()TAA A（譜范數） 表示的最大特征值。

27、第67頁/共93頁例例4 設設 4321,5, 3AxT則則 TAx11, 7 求相應各范數。求相應各范數。解11751868111 AxAxAxAx35114818111 xAAxxAAx第68頁/共93頁3.5 方程組的性態(tài) 前幾節(jié)討論了求解線性代數方程組的直接法.給出系數矩陣A和自由項b,求未知向量x.實踐中,A和b往往是實驗觀測數據或是計算所得結果.因此我們處理的線性方程組 實際上變成了bAx bbxxAA )(的關系怎樣,是人們十分關心的問題.xbA 和和3.5.1 方程組的性態(tài)和矩陣的條件數第69頁/共93頁例例 1 解方程組解方程組 其中其中,bAx 61514151413141

28、3121A 現用絕對精確的計算（即不帶任何舍入誤差的計算）現用絕對精確的計算（即不帶任何舍入誤差的計算） 求解，可以看出求解，可以看出11232123312372240180240900720180720600 xbbbxbbbxbbb 此時，我們發(fā)現對于兩組不同的自由項此時，我們發(fā)現對于兩組不同的自由項 TTbbbbbbbb 321321, 600720180720900240180240721A第70頁/共93頁它的差只有它的差只有 ,Tbbb 而所得解而所得解 與與 之差卻是之差卻是xx Txxx 1500,1860,492 兩組不同的右端其分量之差不過是兩組不同的右端其分量之差不過是

29、可是解的差高可是解的差高 達達 之之1860倍像這樣的方程組或矩陣倍像這樣的方程組或矩陣A 就叫做病態(tài)的就叫做病態(tài)的 , 定義1 若方程組 Ax=b 的系數矩陣 A 或右端向量 b 的微小變化（小擾動）引起解產生巨大變化,則稱此方程組為病態(tài)方程組; A稱為病態(tài)矩陣, 否則稱為良態(tài)方程組, A 稱為良態(tài)矩陣。 第71頁/共93頁定理：設 非奇異， ，且 則 0 bAxA bbxxA bbAAxx 1 為了定量地刻劃方程組的“病態(tài)”程度，下面就一般方程組 進行討論。首先考察右端項b 的擾動對解的影響。bAx 第72頁/共93頁證： 設x為Ax=b的準確解，當方程組右端有小擾動b而A準確時,受擾解為

30、 x +x , 即 A(x +x)=b+ b 因為 Ax=b 所以 x=A-1 b 又由xAAxb 得得bAx 1因此bAbAx 11 bbAAxx 1bAx 1 即：即：第73頁/共93頁此不等式表明,解的相對誤差不超過b的相對誤差的 |A| |A-1| 倍.bbAAxx 1 bbAAAAAAAAxx111若系數矩陣A也有小擾動A ,則還可進一步導出更一般的誤差估計式第74頁/共93頁定義定義2 設設A 為非奇異矩陣，稱數為非奇異矩陣，稱數cond(A)= |A| |A-1| 為為A 矩陣的條件數矩陣的條件數矩陣的條件數與范數有關，通常使用的條件數有 AAAAAAAcondAAAcondTT

31、minmax21221 所以，Cond(A)越大,A的病態(tài)程度越嚴重。 對任何非奇異矩陣對任何非奇異矩陣A，都有，都有 。 1 Acond不難證明，條件數具有如下不難證明，條件數具有如下性質性質第75頁/共93頁例例 求矩陣求矩陣A 的條件數，其中的條件數，其中 615141514131413121A解：解：1213max3131 jijiaA 600720180720900240180240721A于是于是 從而從而,18601 A 20151 AAAcond所以A是病態(tài)的第76頁/共93頁矩陣的某些行或列近似相關，這樣的矩陣則有可能是病態(tài)矩陣。第77頁/共93頁3.5.2 直接法的精度分析

32、定理：設 是方程組 的一個近似解，其精確解記為 ， 為 的余量，則有xbAx *xrxbrAAxxx1* 求得方程組 的一個近似解 后，希望能判斷其精度。檢驗精度的一個簡單辦法是將近似解再回代到原方程組去求其余量 。如果 很小，就認為解 是相當準確的。bAx xxAbr rxx第78頁/共93頁該定理給出了方程組近似解的相對誤差界。即相對誤差的事后估計證：由于 ，而 ，故有 bAx *rxxA *bAxxAAxb *1rArAxx11* 所以brAAxxx1* 第79頁/共93頁生成向量序列 x(k) ，若 xxkk)(lim稱為迭代格式（1）的迭代矩陣。則有x* =Bx*+f ， 即x*為原

33、方程組Ax=b 的解，B迭代法基本思想：將方程組 Ax=b ( |A|0 ) 轉化為與其等價的方程組x = Bx+fx(k+1) = Bx(k) + f （k=0,1,2,) (1)取初始向量 x(0)按下列迭代格式第80頁/共93頁雅可比迭代法 對線性方程組可以建立不同的迭代格式。下面介紹構造迭代格式的幾種常用方法，雅克比迭代法和高斯塞德爾迭代法。設方程組 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111第81頁/共93頁其中 aii0 ( i=1 , 2 , , n)11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba 分別從上式n個方程中分離出n個變量，如下：第82頁/共93頁建立迭代格式 )(1)(1)(1)(11)(11) 1(2)(2)(323)(12122) 1(21)(1)(313)(21