第3章線性方程組的數(shù)值解法

1、 n n階線性代數(shù)方程組的一般形式為階線性代數(shù)方程組的一般形式為：11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb第三章第三章 線性方程組的數(shù)值解法線性方程組的數(shù)值解法問(wèn)題的提出問(wèn)題的提出：寫成矩陣寫成矩陣- -向量形式向量形式 bAx 若矩陣若矩陣 非奇異，即非奇異，即 的行列式的行列式 ，根據(jù)，根據(jù)克萊姆（克萊姆（Gramer）法則，方程組有唯一）法則，方程組有唯一 解：解：AA0det ADDxii ni, 2 , 1 nnnnaaaaA1111 nxxx1 nbbb1Axb其中其中 為系數(shù)矩陣，為系數(shù)矩陣，

2、為解向量，為解向量， 為右端常向量。為右端常向量。其中其中 表示表示 ， 表示表示 中第中第 列換成列換成 后后所得的行列式。所得的行列式。ibiDDAdetD 當(dāng)階數(shù)較高時(shí)用這種方法求解是不現(xiàn)實(shí)的。當(dāng)階數(shù)較高時(shí)用這種方法求解是不現(xiàn)實(shí)的。 階階行列式有行列式有 項(xiàng)，每項(xiàng)又是項(xiàng)，每項(xiàng)又是 個(gè)數(shù)的乘積。對(duì)較大個(gè)數(shù)的乘積。對(duì)較大的的 ，其，其計(jì)算量之大計(jì)算量之大，是一般計(jì)算機(jī)難以完成的。，是一般計(jì)算機(jī)難以完成的。而且，這時(shí)的而且，這時(shí)的舍入誤差舍入誤差對(duì)計(jì)算結(jié)果的影響也較大。對(duì)計(jì)算結(jié)果的影響也較大。n!nnn例如，求解一個(gè)例如，求解一個(gè)20階線性方程組，用加減消元法需階線性方程組，用加減消元法需30

3、00次乘法運(yùn)算，而用克萊姆法則要進(jìn)行次乘法運(yùn)算，而用克萊姆法則要進(jìn)行 次次運(yùn)算，如用每秒運(yùn)算，如用每秒1億次乘法運(yùn)算的計(jì)算機(jī)要億次乘法運(yùn)算的計(jì)算機(jī)要30萬(wàn)年。萬(wàn)年。209.7 10線性代數(shù)方程組的計(jì)算機(jī)解法常用方法：線性代數(shù)方程組的計(jì)算機(jī)解法常用方法：直接法直接法 迭代法迭代法消去法消去法矩陣三角分解法矩陣三角分解法 直接法直接法：經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得方程組：經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得方程組的精確解的方法（若在計(jì)算過(guò)程中沒(méi)有舍入誤差）的精確解的方法（若在計(jì)算過(guò)程中沒(méi)有舍入誤差） 迭代法迭代法：用某種極限過(guò)程去逐步逼近線性方程：用某種極限過(guò)程去逐步逼近線性方程組精確解的方法組精確解的方法

4、迭代法具有占存儲(chǔ)單元少，程序設(shè)計(jì)簡(jiǎn)單，原迭代法具有占存儲(chǔ)單元少，程序設(shè)計(jì)簡(jiǎn)單，原始系數(shù)矩陣在迭代過(guò)程中不變等優(yōu)點(diǎn)，但存在收始系數(shù)矩陣在迭代過(guò)程中不變等優(yōu)點(diǎn)，但存在收斂性及收斂速度等問(wèn)題斂性及收斂速度等問(wèn)題3.1 消去法消去法消去法的基本思想：消去法的基本思想：是通過(guò)將一個(gè)方程乘或除以是通過(guò)將一個(gè)方程乘或除以某個(gè)常數(shù)，以及將兩個(gè)方程相加減，逐步減少方程中某個(gè)常數(shù)，以及將兩個(gè)方程相加減，逐步減少方程中的變?cè)獢?shù)，最終使每個(gè)方程只含一個(gè)變?cè)?，從而得出的變?cè)獢?shù)，最終使每個(gè)方程只含一個(gè)變?cè)?，從而得出所求的解。所求的解。消去法常用方法：消去法常用方法：高斯消去法高斯消去法選主元消去法選主元消去法高斯約旦消去

5、法高斯約旦消去法消去法消去法3.1 高斯消去法高斯消去法 按自然順序進(jìn)行的消元法按自然順序進(jìn)行的消元法例例 1 用高斯消元法求解方程組用高斯消元法求解方程組 12312312328214613225xxxxxxxxx解解 用第一個(gè)方程削去后兩個(gè)方程中的用第一個(gè)方程削去后兩個(gè)方程中的 得得 ,1x 9962214282232321xxxxxx再用第再用第2個(gè)方程消去第個(gè)方程消去第3個(gè)方程中的個(gè)方程中的 得得,2x 18962214282332321xxxxxx最后，經(jīng)過(guò)回代求得原方程組的解為最后，經(jīng)過(guò)回代求得原方程組的解為 52281412262918321323 xxxxxx例例 2 解方程組

6、解方程組 02115472321321321xxxxxxxxx解：解：消元消元 0121111547112 3235 . 2rr 620033307112 5 . 35 . 05 . 203330711231212124rrrr 回代回代得得, 3263 x, 233332 xx127321 xxx消去法消去法 1ijabAx 11bxA 1A 1b 1ibnji, 2 , 1, 1 0111 a niaamii, 3 , 2,111111 i1im n1x 22bxA 22211212222222211112111nnnnnnnbbbxxxaaaaaaa njibmbbamaaiiijiij

7、ij, 3 , 2,1111211112 k 12 nk1 k kkbxA knnknkkknkkknnkaaaaaaaaaaA2222322211112111 knkkkbbbbb2211 0 kkka nkiaamkkkkikik, 1, 0 kkka1 n nnbxA nnnnnnnnbbbxxxaaaaaa2211212222211112111 0 nnna11,xxxnn 1 , 2 , 1 ,1 niaxabxabxiiinijjiijiiinnnnnn nkakkk, 2 , 1, 0 kkka1, 2 , 1 nk nkkjibmbbamaaaamkkikkikikkjikki

8、jkijkkkkikik, 2, 1, 11)()( 1 , 2 , 1 ,1 niaxabxabxiiinijjiijiiinnnnnnnkkiaaaikkkik, 2, 1,nkkjibbabaaaaijikiijkjikij, 2, 1, 1 , 2 , 1 1 nibaxabbabiiinijjijinnnnnbbb,21nxxx,21定理定理2 Ax=b 可用高可用高 斯消元法求解的充分必要條件是：斯消元法求解的充分必要條件是：系數(shù)矩陣系數(shù)矩陣 A 的各階順序主子式均不為零。的各階順序主子式均不為零。高斯消元法的條件高斯消元法的條件定理定理1 如果在消元過(guò)程中如果在消元過(guò)程中A的主元

9、素的主元素 (k=1,2,n) ,則可通過(guò)高斯消元法求出則可通過(guò)高斯消元法求出Ax=b 的解。的解。0)( kkka1110Da11110,2,3,kkkkkaaDknaa 引理引理 A的主元素的主元素 (k=1,2,n) 的充要條件的充要條件是矩陣是矩陣A的各階的各階順序主子式順序主子式不為零，即不為零，即0)( kkka33n高斯消去法的計(jì)算量高斯消去法的計(jì)算量無(wú)法進(jìn)行；無(wú)法進(jìn)行；或或| akk(k) |1時(shí)，帶來(lái)舍入誤差的擴(kuò)散。時(shí)，帶來(lái)舍入誤差的擴(kuò)散。如何處理？如何處理？ 0)( kkka例例 1 解方程組解方程組 0000. 10000. 10000. 10001. 20000. 30

10、003. 02121xxxx 0 .66660 .99990001. 20000. 30003. 0221xxx解法一解法一 用高斯消元法求解（取用高斯消元法求解（取5位有效數(shù)字），用第位有效數(shù)字），用第 一個(gè)方程消去第二個(gè)方程中的一個(gè)方程消去第二個(gè)方程中的,1x3.1.2 高斯主元素消元法高斯主元素消元法因而再回代，得因而再回代，得 216666.00.66679999.02.00013.00000.666700.0003xx而精確值為而精確值為 顯然該解與精確值相差顯然該解與精確值相差太遠(yuǎn)，為了控制誤差，采用另一種消元過(guò)程。太遠(yuǎn)，為了控制誤差，采用另一種消元過(guò)程。32,3121 xx解法二

11、解法二 為了避免絕對(duì)值很小的元素作為主元，先交為了避免絕對(duì)值很小的元素作為主元，先交換兩個(gè)方程，得到換兩個(gè)方程，得到 0001. 20000. 30003. 00000. 10000. 10000. 12121xxxx消去第二個(gè)方程中的消去第二個(gè)方程中的 得得 ,1x 9998. 19997. 20000. 10000. 10000. 1221xxx再回代，解得再回代，解得 3333. 06667. 00000. 10000. 16667. 09997. 29998. 112 xx結(jié)果與準(zhǔn)確解非常接近。這個(gè)例子告訴我們，在采用高結(jié)果與準(zhǔn)確解非常接近。這個(gè)例子告訴我們，在采用高斯消元法解方程組時(shí)

12、，用做除法的小主元素可能使舍入斯消元法解方程組時(shí)，用做除法的小主元素可能使舍入誤差增加，誤差增加，主元素的絕對(duì)值越小，則舍入誤差影響越大主元素的絕對(duì)值越小，則舍入誤差影響越大。固應(yīng)避免采用絕對(duì)值小的主元素，同時(shí)選主元素盡量的固應(yīng)避免采用絕對(duì)值小的主元素，同時(shí)選主元素盡量的大，可使該法具有較好的數(shù)值穩(wěn)定性。大，可使該法具有較好的數(shù)值穩(wěn)定性。列主元素消元法列主元素消元法kkakka例：例：求解線性方程組求解線性方程組 000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0321xxx解法一：用列主元素消元法，

13、方程組增廣矩陣為：解法一：用列主元素消元法，方程組增廣矩陣為： 000. 3643. 5072. 1000. 2000. 2623. 4712. 3000. 1000. 1000. 3000. 2001. 0A 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回代

14、計(jì)算解為回代計(jì)算解為 Tx3678. 0 ,05113. 0,4990. 0* 全選主元素消元法全選主元素消元法 回代計(jì)算得回代計(jì)算得0.367, 0.0511, 0.491Ty從而原方程的解為從而原方程的解為 Tx367. 0 ,051. 0,491. 0 3.1.3 3.1.3 高斯高斯- -約當(dāng)約當(dāng)(Jordan)(Jordan)消去法消去法 消元時(shí)將主元上方元素也消為消元時(shí)將主元上方元素也消為0 0，最后，最后系數(shù)矩陣化為對(duì)角矩陣。這種算法只有消系數(shù)矩陣化為對(duì)角矩陣。這種算法只有消元，沒(méi)有回代，這種方法稱做高斯元，沒(méi)有回代，這種方法稱做高斯- -約當(dāng)約當(dāng)(Jordan)(Jordan)

15、消去法。消去法。 例 用高斯-約當(dāng)消去法解下列線性方程組 123123123223347712457xxxxxxxxx 解解 對(duì)線性方程組第 1 次消元，0211a，確定乘數(shù) 212111422ama，313111212ama ) 1 ()3() 1 ()2(3121mm12312312322330350684xxxxxxxxx 第2次 消 元 ，2230a， 確 定 乘 數(shù)12122221.53ama，323222623ama，有 1232(1)(2)(3)(2)mm12323371020330350066xxxxxx 第 3 次消元，3360a，確定乘數(shù)1313337/36ama，2323

16、3316ama有1323(1)(3)(2)(3)mm12323200403060066xxxxx 解出 1232,2,1xxx 比較而言比較而言,Gauss,Gauss順序消去法條件苛刻順序消去法條件苛刻, ,且且數(shù)值不穩(wěn)定數(shù)值不穩(wěn)定; Gauss; Gauss全主元消去法工作量偏大，全主元消去法工作量偏大，算法復(fù)雜；對(duì)于算法復(fù)雜；對(duì)于Gauss-JordanGauss-Jordan消去法形式上消去法形式上比其他消元法簡(jiǎn)單，且無(wú)回代求解，但計(jì)算比其他消元法簡(jiǎn)單，且無(wú)回代求解，但計(jì)算量大。因此從算法優(yōu)化的角度考慮，量大。因此從算法優(yōu)化的角度考慮， GaussGauss列主元消去法比較好。列主元消

17、去法比較好。消去法小結(jié)消去法小結(jié)3.2 矩陣三角分解法矩陣三角分解法nbAx n1 nnbxA LULUA ALUALUUALALU 1112121nnlll 1112112nnuuu 1131313111311121212111211111232322131211323121333231232221131211)3 , 2 , 1(11113,ualluaualluajauuakuuuuuulllaaaaaaaaanULjjjj得由；得由時(shí)：為例的各元素，以此分解在于如何算出杜里特爾分解杜里特爾分解 A=LU)(3223321331333333233213313322123132322332

18、12313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得時(shí)：由得由；得由；得時(shí)：杜里特爾分解杜里特爾分解杜里特爾分解杜里特爾分解(一般算法一般算法)niulaniuaiiii, 3 , 2, 2 , 1,111111 由矩陣乘法規(guī)則由矩陣乘法規(guī)則LUA nnnnnnnnnnirrinnuuuuuulllaaaaaaaaaaa222112112121212222111211111由此可得由此可得 的第一行元素和的第一行元素和 的第一列元素的第一列元素niualniauiiii, 3 , 2, 2

19、 , 1,111111 UL 當(dāng)已得出當(dāng)已得出 的前的前 行元素和行元素和 的前的前 列元素，則對(duì)于列元素，則對(duì)于 ，由，由rruirlrkkruiklnkkruiklirariurkkiurklnkkiurklria 111111nrri, 1, U1 rL1 r又可得計(jì)算又可得計(jì)算 的第的第 行元素和行元素和 的第的第 列元列元素的公式素的公式: :nrrirrurkkruiklirairlnrrirkkiurklriariu, 2, 1 ,11, 1, ,11 UrLr例例 求矩陣求矩陣2144416512A 的的LU分解。分解。 u11=2 u12=1 u13=4 1213532 l2

20、2421 l32631 l212422u2312 47u 7)7(1431233u所以所以2141002144412100276512311007 700720412113012001ULa11 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框框 按下圖所示順序逐框進(jìn)行按下圖所示順序逐框進(jìn)行,先求先求 u 后求后求 l。矩陣三角分解算法總結(jié)矩陣三角分解算

21、法總結(jié)： 有了矩陣有了矩陣 A A 的的LULU分解計(jì)算公式，當(dāng)求解線性方分解計(jì)算公式，當(dāng)求解線性方程組程組 時(shí)，等價(jià)于求解時(shí)，等價(jià)于求解 。這時(shí)可歸結(jié)。這時(shí)可歸結(jié)為利用遞推計(jì)算相繼求解兩個(gè)三角形方程組（系數(shù)為利用遞推計(jì)算相繼求解兩個(gè)三角形方程組（系數(shù)矩陣為三角矩陣）。矩陣為三角矩陣）。用順代，用順代，由由 求出求出 ，再利用再利用回代，回代，由由 求出求出 。bAx bLUx bLy yUx xy3.2.2 解線性方程組的三角分解法解線性方程組的三角分解法用用杜里特爾杜里特爾三角分解法解線性方程組三角分解法解線性方程組 的的計(jì)算方法計(jì)算方法：bAx 對(duì)于對(duì)于 ，計(jì)算，計(jì)算 和和 。求解求解

22、，即計(jì)算，即計(jì)算求解求解 ，即計(jì)算。，即計(jì)算。nr, 3 , 2 nrriuri, 1, nrrilir, 2, 1, bLy niylbybyikkikii, 3 , 2,1111 yUx 1 , 2 , 1,1 niuxuyxuyxiinikkikiinnnn計(jì)算計(jì)算 和和 。niui, 2 , 1,1 nili, 3 , 2,1 30191063619134652. 1321xxx方程組方程組試用杜里特爾分解求解試用杜里特爾分解求解例例。，；，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuu

23、uuulllALULUAululaukuulalulauulauk473652143121434/ )(7)6(21935213223321331333322123132321321232312212222所以時(shí)：，時(shí)：TyyyyyyybLy)4 , 1,10(43034, 12019,1030191014312112321321即得）解（、解方程組。所以方程組的解為所以方程組的解為解得：解得：解解TxxxxxxxyUx)1 , 2 , 3(3, 2,2(123321 其它其它矩陣分解法矩陣分解法求解特殊的線性方程組：求解特殊的線性方程組：平方根法：主要用于求解平方根

24、法：主要用于求解正定矩陣正定矩陣的線性方程組的線性方程組追趕法：主要用于求解特殊矩陣的三對(duì)角方程組追趕法：主要用于求解特殊矩陣的三對(duì)角方程組 見(jiàn)書見(jiàn)書 P78P87用用LU LU 直接分解的方法求解線性方程組的計(jì)算量直接分解的方法求解線性方程組的計(jì)算量為為 ，和高斯消去法的計(jì)算量的數(shù)量級(jí)基本相同，和高斯消去法的計(jì)算量的數(shù)量級(jí)基本相同。33n當(dāng)方程組系數(shù)矩陣不變，只有右側(cè)向量當(dāng)方程組系數(shù)矩陣不變，只有右側(cè)向量b b變化時(shí)，變化時(shí)，用用LULU分解法比消去法速度快。因?yàn)橛覀?cè)向量分解法比消去法速度快。因?yàn)橛覀?cè)向量b b的的改變改變不影響不影響LULU的變化。的變化。高斯消去法和高斯消去法和LU分解法

25、是等價(jià)的，其關(guān)鍵是把一分解法是等價(jià)的，其關(guān)鍵是把一般方程組變?yōu)槿欠匠探M，只是實(shí)現(xiàn)途徑不同般方程組變?yōu)槿欠匠探M，只是實(shí)現(xiàn)途徑不同。3.4 向量與矩陣的范數(shù)向量與矩陣的范數(shù) 問(wèn)題的提出問(wèn)題的提出 向量范數(shù)向量范數(shù)概念是三維歐氏空間中向量長(zhǎng)度概念的概念是三維歐氏空間中向量長(zhǎng)度概念的推廣推廣, ,在數(shù)值分析中起著重要作用在數(shù)值分析中起著重要作用. . 為了研究線性方程組近似解的誤差估計(jì)和迭代為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要對(duì)法的收斂性，我們需要對(duì) （n n維向量空間）中向維向量空間）中向量及量及 （ 維矩陣空間）中矩陣的維矩陣空間）中矩陣的“大小大小”及及“距離距離”引

26、進(jìn)某種度量引進(jìn)某種度量向量與矩陣范數(shù)向量與矩陣范數(shù)的概念的概念.nRnn nnR 平面向量平面向量 x 大?。河么笮。河?距離距離 反映。反映。2221xxx 3.4 向量與矩陣的范數(shù)向量與矩陣的范數(shù) 引入范數(shù)的目的：引入范數(shù)的目的：實(shí)數(shù)大?。河媒^對(duì)值反實(shí)數(shù)大?。河媒^對(duì)值反映映復(fù)數(shù)大?。河媚７从硰?fù)數(shù)大?。河媚７从掣呔S空間向量高維空間向量 x “大小大小” 用用 反映？反映？ 將將度量長(zhǎng)度數(shù)值度量長(zhǎng)度數(shù)值的計(jì)算方法引入高維空間，的計(jì)算方法引入高維空間，用來(lái)反映空間向量的大小，就是用來(lái)反映空間向量的大小，就是范數(shù)范數(shù)的概念的概念。 非負(fù)性非負(fù)性 |x| 0 ，等號(hào)僅當(dāng)，等號(hào)僅當(dāng) x=0 時(shí)成立；時(shí)

27、成立； 齊次性齊次性 對(duì)任何實(shí)數(shù)對(duì)任何實(shí)數(shù) , | x|=| | |x|； 三角不等式三角不等式 |x+y| |x| +|y| ； 則稱則稱 |x| 為向量為向量 x 的范數(shù)。的范數(shù)。定義定義 對(duì)任意對(duì)任意 n 維向量維向量 x Rn，若對(duì)應(yīng)非負(fù)實(shí)數(shù)，若對(duì)應(yīng)非負(fù)實(shí)數(shù) |x| ， 滿滿足足 3.4.1 向量的范數(shù)向量的范數(shù) 由定義可知，向量由定義可知，向量 的范數(shù)的范數(shù) 是按一定規(guī)律是按一定規(guī)律與與 對(duì)應(yīng)的實(shí)數(shù)，該實(shí)數(shù)的值沒(méi)有確定，但只要滿對(duì)應(yīng)的實(shí)數(shù)，該實(shí)數(shù)的值沒(méi)有確定，但只要滿足這三個(gè)條件，這個(gè)實(shí)數(shù)就是向量足這三個(gè)條件，這個(gè)實(shí)數(shù)就是向量 的一種范數(shù)。的一種范數(shù)。因此定義中的三個(gè)條件稱為因此定義

28、中的三個(gè)條件稱為范數(shù)公理范數(shù)公理。xxxx當(dāng)當(dāng) 時(shí)時(shí)，0 x1 xx向量范數(shù)向量范數(shù) 有如下性質(zhì)有如下性質(zhì)x證：利用條件，有證：利用條件，有11 xxxxxx yxyx yyxyyxx yxyx 證：證：它們分別叫做向量的它們分別叫做向量的 -范數(shù)范數(shù)、1-范數(shù)范數(shù)、2-范數(shù)范數(shù)、p -范數(shù)（范數(shù)（0p+ ）。 p -范數(shù)是以上范數(shù)的統(tǒng)一表范數(shù)是以上范數(shù)的統(tǒng)一表達(dá)形式。達(dá)形式。常用的向量范數(shù)常用的向量范數(shù): 滿足定義的范數(shù)不是唯一的滿足定義的范數(shù)不是唯一的.inixx 1maxnxxxx 211222212nxxxx ppnpppxxxx121)( 設(shè)設(shè) x = ( x1 , x2 , , x

29、n)T ，常用的向量范數(shù)有，常用的向量范數(shù)有 對(duì)于對(duì)于范數(shù)，有范數(shù)，有當(dāng)當(dāng) 時(shí)，有時(shí)，有 ， 只有當(dāng)只有當(dāng) 時(shí)，才有時(shí)，才有 對(duì)任意實(shí)數(shù)對(duì)任意實(shí)數(shù) ，因?yàn)?，因?yàn)?，所以，所以 。對(duì)任意向量對(duì)任意向量 ，有，有 0 x0max1 inixx0 x0 x Tnxxxx ,21 xxxxiiini maxmax1nRy 111maxmaxmaxmaxiiiiiii nii ni nxyxyxyxyxy iixxmax 例：例：范數(shù)的證明范數(shù)的證明可以證明這幾種范數(shù)滿足下述關(guān)系可以證明這幾種范數(shù)滿足下述關(guān)系 xnxxxnxx21事實(shí)上，對(duì)事實(shí)上，對(duì) Rn 上任意兩種向量范數(shù)上任意兩種向量范數(shù) |x|

30、, |x| ，都存在與，都存在與 x 無(wú)關(guān)的正常數(shù)無(wú)關(guān)的正常數(shù) c1 , c2 使使 這種性質(zhì)稱為這種性質(zhì)稱為向量范數(shù)的等價(jià)性向量范數(shù)的等價(jià)性。 xcxxc21 定理：定理：設(shè)設(shè)Rn上的任意兩種范數(shù)上的任意兩種范數(shù)|x|a , |x|b , 都存都存在與在與x無(wú)關(guān)的正常數(shù)無(wú)關(guān)的正常數(shù)c1,c2使得使得12abac xxcx|x|a , |x|bRn設(shè)給定設(shè)給定 中的向量序列中的向量序列 ，其中其中 若對(duì)任何若對(duì)任何 ，都有，都有，則向量則向量 稱為向量序列稱為向量序列 的極限，的極限，或者說(shuō)向量序列收斂于向量或者說(shuō)向量序列收斂于向量 ，記為：，記為：nR kx Tknkkkxxxx,21 ni

31、i, 2 , 1 *limikixx Tnxxxx*2*1*, kx*x *limxxkk 向量收斂的定義向量收斂的定義：向量序列收斂性定理：向量序列收斂性定理： 向量序列向量序列收斂收斂 ( (即即 ) )的充要條件的充要條件是是 ，其中，其中 為向量的任一種范數(shù)。為向量的任一種范數(shù)。 *limxxkk 0lim* xxkk 按按不同方式規(guī)定的范數(shù)不同方式規(guī)定的范數(shù), ,其值一般不同。但在各種其值一般不同。但在各種范數(shù)下考慮向量序列范數(shù)下考慮向量序列收斂性的結(jié)論是一致的收斂性的結(jié)論是一致的。即向量。即向量序列如對(duì)某一種范數(shù)收斂則對(duì)其它范數(shù)也收斂，且有序列如對(duì)某一種范數(shù)收斂則對(duì)其它范數(shù)也收斂，

32、且有相同的極限。這樣，在研究某一具體問(wèn)題時(shí)，可以選相同的極限。這樣，在研究某一具體問(wèn)題時(shí)，可以選擇一較易簡(jiǎn)單的范數(shù)。擇一較易簡(jiǎn)單的范數(shù)。矩陣范數(shù)是用于定義矩陣矩陣范數(shù)是用于定義矩陣“大小大小”的量。的量。由于在大多數(shù)與估計(jì)誤差有關(guān)的問(wèn)題中由于在大多數(shù)與估計(jì)誤差有關(guān)的問(wèn)題中,矩矩陣和向量的乘積陣和向量的乘積經(jīng)常出現(xiàn)經(jīng)常出現(xiàn),所以希望引進(jìn)一種矩所以希望引進(jìn)一種矩陣的范數(shù)陣的范數(shù),它與向量范數(shù)有某種關(guān)系。它與向量范數(shù)有某種關(guān)系。3.4.2 矩陣的范數(shù)矩陣的范數(shù) 定義定義：設(shè)：設(shè) ， ，定義矩陣，定義矩陣 的范數(shù)的范數(shù) 對(duì)于每一種向量范數(shù)對(duì)于每一種向量范數(shù) ，相應(yīng)的矩陣范數(shù)，相應(yīng)的矩陣范數(shù) 為為其中其

33、中 是指是指 的最大可能值。即遍取所有不為的最大可能值。即遍取所有不為0 0的的 ，比值比值 中最大的中最大的，定義，定義為為 的矩陣范數(shù)的矩陣范數(shù)。 nnRA nRx AxAxA0 x maxpxppxpxAxA0max pAmaxxAxxxAxA矩陣范數(shù)的性質(zhì)矩陣范數(shù)的性質(zhì)： , ,且僅當(dāng)且僅當(dāng) 時(shí)，時(shí)， ； 對(duì)任意實(shí)數(shù)對(duì)任意實(shí)數(shù) ， ； 對(duì)同維方陣對(duì)同維方陣 ，有，有: : 0 A0 A0 A AA B ,BABA BAAB 相容性條件：相容性條件： 由矩陣范數(shù)的定義可直接得到由矩陣范數(shù)的定義可直接得到 ，即有，即有 ，稱為，稱為相容性條件。即相容性條件。即所給的所給的矩陣范數(shù)與向量范數(shù)

34、是相容的。矩陣范數(shù)與向量范數(shù)是相容的。xAxA xAAx 證明證明 p92矩陣范數(shù)與向量范數(shù)的關(guān)系矩陣范數(shù)與向量范數(shù)的關(guān)系： 矩陣范數(shù)與向量范數(shù)密切相關(guān)，向量范數(shù)有相應(yīng)矩陣范數(shù)與向量范數(shù)密切相關(guān)，向量范數(shù)有相應(yīng)的矩陣范數(shù)，即：的矩陣范數(shù)，即： （如（如 ）pxpAxAp1max , 2 , 1pxxAxAxAxx00maxmax AxxAxxA 矩陣范數(shù)與向量范數(shù)的關(guān)系矩陣范數(shù)與向量范數(shù)的關(guān)系： 矩陣范數(shù)與向量范數(shù)密切相關(guān)，向量范數(shù)有相應(yīng)矩陣范數(shù)與向量范數(shù)密切相關(guān)，向量范數(shù)有相應(yīng)的矩陣范數(shù)，即：的矩陣范數(shù)，即： （如（如 ）pxpAxAp1max , 2 , 1p常用的矩陣范數(shù)有（矩陣范數(shù)的求

35、取）常用的矩陣范數(shù)有（矩陣范數(shù)的求?。?(maxmaxmax211111AAAaAaATniijnjnjijni （矩矩陣陣的的行行范范數(shù)數(shù)）（矩矩陣陣的的列列范范數(shù)數(shù)）)(maxmaxmax211111AAAaAaATniijnjnjijni （矩矩陣陣的的行行范范數(shù)數(shù)）（矩矩陣陣的的列列范范數(shù)數(shù)）它們分別叫做矩陣的它們分別叫做矩陣的 -范數(shù)范數(shù)、1-范數(shù)、譜范數(shù)范數(shù)、譜范數(shù)。 max()TA ATA Amax2()TAA A（譜范數(shù)）（譜范數(shù)） 表示表示的最大特征值。的最大特征值。例例4 設(shè)設(shè) 4321,5, 3AxT則則 TAx11, 7 求相應(yīng)各范數(shù)。求相應(yīng)各范數(shù)。解解11751868

36、111 AxAxAxAx35114818111 xAAxxAAx3.5 3.5 方程組的性態(tài)方程組的性態(tài) 前幾節(jié)討論了求解線性代數(shù)方程組的直接法前幾節(jié)討論了求解線性代數(shù)方程組的直接法. .給出給出系數(shù)矩陣系數(shù)矩陣A A和自由項(xiàng)和自由項(xiàng)b,b,求未知向量求未知向量x.x.實(shí)踐中實(shí)踐中,A,A和和b b往往往是實(shí)驗(yàn)觀測(cè)數(shù)據(jù)或是計(jì)算所得結(jié)果往是實(shí)驗(yàn)觀測(cè)數(shù)據(jù)或是計(jì)算所得結(jié)果. .因此我們處理因此我們處理的線性方程組的線性方程組 實(shí)際上變成了實(shí)際上變成了bAx bbxxAA )(的關(guān)系怎樣的關(guān)系怎樣, ,是人們十分關(guān)心的問(wèn)題是人們十分關(guān)心的問(wèn)題. .xbA 和和3.5.1 3.5.1 方程組的性態(tài)和矩陣

37、的條件數(shù)方程組的性態(tài)和矩陣的條件數(shù)例例 1 解方程組解方程組 其中其中,bAx 615141514131413121A 現(xiàn)用絕對(duì)精確的計(jì)算（即不帶任何舍入誤差的計(jì)算）現(xiàn)用絕對(duì)精確的計(jì)算（即不帶任何舍入誤差的計(jì)算） 求解，可以看出求解，可以看出11232123312372240180240900720180720600 xbbbxbbbxbbb 此時(shí)，我們發(fā)現(xiàn)對(duì)于兩組不同的自由項(xiàng)此時(shí)，我們發(fā)現(xiàn)對(duì)于兩組不同的自由項(xiàng) TTbbbbbbbb 321321, 600720180720900240180240721A它的差只有它的差只有 ,Tbbb 而所得解而所得解 與與 之差卻是之差卻是xx Txxx

38、1500,1860,492 兩組不同的右端其分量之差不過(guò)是兩組不同的右端其分量之差不過(guò)是 可是解的差高可是解的差高 達(dá)達(dá) 之之1860倍像這樣的方程組或矩陣倍像這樣的方程組或矩陣A 就叫做病態(tài)的就叫做病態(tài)的 , 定義定義1 若方程組若方程組 Ax=b 的系數(shù)矩陣的系數(shù)矩陣 A 或或右端向量右端向量 b 的微小變化（小擾動(dòng)）引起解產(chǎn)生巨大變化的微小變化（小擾動(dòng)）引起解產(chǎn)生巨大變化,則稱則稱此方程組為此方程組為病態(tài)方程組病態(tài)方程組; A稱為稱為病態(tài)矩陣病態(tài)矩陣, 否則稱為否則稱為良態(tài)方程組良態(tài)方程組, A 稱為稱為良態(tài)矩陣良態(tài)矩陣。 定理定理：設(shè)：設(shè) 非奇異，非奇異， ，且且 則則 0 bAxA

39、bbxxA bbAAxx 1 為了定量地刻劃方程組的為了定量地刻劃方程組的“病態(tài)病態(tài)”程度，下程度，下面就一般方程組面就一般方程組 進(jìn)行討論。首先考察右進(jìn)行討論。首先考察右端項(xiàng)端項(xiàng)b b 的擾動(dòng)對(duì)解的影響的擾動(dòng)對(duì)解的影響。bAx 證證： 設(shè)設(shè)x為為Ax=b的準(zhǔn)確解，當(dāng)方程組右端有小擾動(dòng)的準(zhǔn)確解，當(dāng)方程組右端有小擾動(dòng) b而而A準(zhǔn)確時(shí)準(zhǔn)確時(shí),受擾解為受擾解為 x + x , 即即 A(x + x)=b+ b 因?yàn)橐驗(yàn)?Ax=b 所以所以 x=A-1 b 又由又由xAAxb 得得bAx 1因此因此bAbAx 11 bbAAxx 1bAx 1 即：即：此不等式表明此不等式表明,解的相對(duì)誤差不超過(guò)解的相

40、對(duì)誤差不超過(guò)b的相對(duì)誤差的的相對(duì)誤差的 |A| |A-1| 倍倍.bbAAxx 1 bbAAAAAAAAxx111若系數(shù)矩陣若系數(shù)矩陣A也有小擾動(dòng)也有小擾動(dòng) A ,則還可進(jìn)一步導(dǎo)出更一則還可進(jìn)一步導(dǎo)出更一般的誤差估計(jì)式般的誤差估計(jì)式定義定義2 設(shè)設(shè)A 為非奇異矩陣，稱數(shù)為非奇異矩陣，稱數(shù)cond(A)= |A| |A-1| 為為A 矩陣的條件數(shù)矩陣的條件數(shù)矩陣的條件數(shù)與范數(shù)有關(guān)，通常使用的條件數(shù)有矩陣的條件數(shù)與范數(shù)有關(guān)，通常使用的條件數(shù)有 AAAAAAAcondAAAcondTTminmax21221 所以，所以，Cond(A)越大越大,A的病態(tài)程度越嚴(yán)重。的病態(tài)程度越嚴(yán)重。 對(duì)任何非奇異矩陣

41、對(duì)任何非奇異矩陣A，都有，都有 。 1 Acond不難證明，條件數(shù)具有如下不難證明，條件數(shù)具有如下性質(zhì)性質(zhì)例例 求矩陣求矩陣A 的條件數(shù)，其中的條件數(shù)，其中 615141514131413121A解：解：1213max3131 jijiaA 600720180720900240180240721A于是于是 從而從而,18601 A 20151 AAAcond所以所以A是病態(tài)的是病態(tài)的 由于計(jì)算條件數(shù)涉及到計(jì)算逆矩陣，很麻煩。由于計(jì)算條件數(shù)涉及到計(jì)算逆矩陣，很麻煩。因此實(shí)際計(jì)算中一般通過(guò)可能產(chǎn)生病態(tài)的現(xiàn)象來(lái)判斷。因此實(shí)際計(jì)算中一般通過(guò)可能產(chǎn)生病態(tài)的現(xiàn)象來(lái)判斷。 若在消元過(guò)程中出現(xiàn)小主元，則若在消

42、元過(guò)程中出現(xiàn)小主元，則 A A可能是病態(tài)可能是病態(tài)矩陣。但病態(tài)矩陣未必一定有這種小主元。矩陣。但病態(tài)矩陣未必一定有這種小主元。 若解方程組時(shí)出現(xiàn)很大的解，則若解方程組時(shí)出現(xiàn)很大的解，則A A可能是病態(tài)矩可能是病態(tài)矩陣。但病態(tài)矩陣也可能有一個(gè)小解。陣。但病態(tài)矩陣也可能有一個(gè)小解。 從矩陣本身看，若元素間數(shù)量級(jí)相差很大且無(wú)從矩陣本身看，若元素間數(shù)量級(jí)相差很大且無(wú)一定規(guī)律；或者矩陣的某些行或列近似相關(guān)，這樣的一定規(guī)律；或者矩陣的某些行或列近似相關(guān)，這樣的矩陣則有可能是病態(tài)矩陣。矩陣則有可能是病態(tài)矩陣。3.5.2 直接法的精度分析直接法的精度分析定理定理：設(shè)：設(shè) 是方程組是方程組 的一個(gè)近似解，的一個(gè)

43、近似解，其精確解記為其精確解記為 ， 為為 的余量，則有的余量，則有xbAx *xrxbrAAxxx1* 求得方程組求得方程組 的一個(gè)近似解的一個(gè)近似解 后，希望能判后，希望能判斷其精度。檢驗(yàn)精度的一個(gè)簡(jiǎn)單辦法是將近似解斷其精度。檢驗(yàn)精度的一個(gè)簡(jiǎn)單辦法是將近似解再回代到原方程組去求其余量再回代到原方程組去求其余量 。如果。如果 很很小，就認(rèn)為解小，就認(rèn)為解 是相當(dāng)準(zhǔn)確的。是相當(dāng)準(zhǔn)確的。bAx xxAbr rxx該定理給出了方程組近似解的相對(duì)誤差界。該定理給出了方程組近似解的相對(duì)誤差界。即相對(duì)誤差的事后估計(jì)即相對(duì)誤差的事后估計(jì)證：證：由于由于 ，而，而 ，故有，故有 bAx *rxxA *bAx

44、xAAxb *1rArAxx11* 所以所以brAAxxx1* 生成向量序列生成向量序列 x(k) ，若，若 xxkk)(lim稱為迭代格式（稱為迭代格式（1）的）的迭代矩陣。迭代矩陣。則有則有x* =Bx*+f ， 即即x*為原方程組為原方程組Ax=b 的解，的解，B迭代法基本思想迭代法基本思想：將方程組將方程組 Ax=b ( |A| 0 ) 轉(zhuǎn)化為與其等價(jià)的方程組轉(zhuǎn)化為與其等價(jià)的方程組x = Bx+fx(k+1) = Bx(k) + f （k=0,1,2,) (1)取初始向量取初始向量 x(0)按下列按下列迭代格式迭代格式雅可比迭代法雅可比迭代法 對(duì)線性方程組可以建立不同的迭代格式。下面對(duì)線性方程組可以建立不同的迭代格式。下面介紹構(gòu)造迭代