《計(jì)算方法》第三章 線性方程組的解法

1、1計(jì) 算 方 法華中科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院第三章第三章 線性方程組的解法線性方程組的解法計(jì)算方法課程組23 線性方程組的解法線性方程組的解法3.0 引言引言3.1 雅可比（雅可比（Jacobi）迭代法）迭代法3.2 高斯高斯塞德爾迭代法塞德爾迭代法3.3 超松馳迭代法超松馳迭代法3.4 迭代法的收斂性迭代法的收斂性3.5 高斯消元法高斯消元法3.6 高斯列元素消去法高斯列元素消去法3.7 三角分解法三角分解法3.8 追趕法追趕法3.9 其它應(yīng)用其它應(yīng)用3.10 誤差分析誤差分析33.03.0 引引 言言重要性重要性：解線性代數(shù)方程組的有效方法在計(jì)算數(shù)學(xué)和：解線性代數(shù)方程組的有效方法在計(jì)算數(shù)學(xué)和

2、科學(xué)計(jì)算中具有特殊的地位和作用。如科學(xué)計(jì)算中具有特殊的地位和作用。如彈性力學(xué)、電彈性力學(xué)、電路分析、熱傳導(dǎo)和振動(dòng)路分析、熱傳導(dǎo)和振動(dòng)、以及社會(huì)科學(xué)及定量分析商、以及社會(huì)科學(xué)及定量分析商業(yè)經(jīng)濟(jì)中的各種問題。業(yè)經(jīng)濟(jì)中的各種問題。 求解線性方程組求解線性方程組 的求解方法，其中的求解方法，其中 ， 。 A xbn nAR,nx bR假設(shè)假設(shè) 非奇異，則方程組有唯一解非奇異，則方程組有唯一解. .*12(,)Tnxx xxA43.03.0 引引 言言 分類分類： 線性方程組的解法可分為線性方程組的解法可分為直接法直接法和和迭代法迭代法兩種方法。兩種方法。直直接法接法： 對(duì)于給定的方程組，在沒有舍入誤差

3、的假設(shè)下，對(duì)于給定的方程組，在沒有舍入誤差的假設(shè)下，能在預(yù)定的運(yùn)算次數(shù)內(nèi)求得精確解。最基本的直接法是能在預(yù)定的運(yùn)算次數(shù)內(nèi)求得精確解。最基本的直接法是Gauss消去法，重要的直接法全都受到消去法，重要的直接法全都受到Gauss消去法的啟發(fā)。消去法的啟發(fā)。 計(jì)算代價(jià)高計(jì)算代價(jià)高.(a)迭代法：迭代法：基于一定的遞推格式，產(chǎn)生逼近方程組精確解的基于一定的遞推格式，產(chǎn)生逼近方程組精確解的近似序列近似序列.收斂性是其為迭代法的前提，此外，存在收斂速收斂性是其為迭代法的前提，此外，存在收斂速度與誤差估計(jì)問題。度與誤差估計(jì)問題。簡(jiǎn)單實(shí)用簡(jiǎn)單實(shí)用, 誘人。誘人。53.1 雅可比雅可比Jacobi迭代法迭代法

4、(AX=b)迭代法的基本思想迭代法的基本思想例題分析例題分析Jacobi迭代公式迭代公式6 與解與解f (x)=0 的不動(dòng)點(diǎn)迭代相類似，將的不動(dòng)點(diǎn)迭代相類似，將AX=b改寫改寫為為X=BX+f 的形式，建立雅可比方法的迭代格式：的形式，建立雅可比方法的迭代格式： 其中，其中，B稱為迭代矩陣。其計(jì)算精度可控，特別稱為迭代矩陣。其計(jì)算精度可控，特別適用于求解系數(shù)為大型稀疏矩陣適用于求解系數(shù)為大型稀疏矩陣(sparse matrices)的的方程組。方程組。3.1 3.1 雅可比雅可比JacobiJacobi迭代法迭代法 (AX=b)(AX=b)迭代法的基本思想迭代法的基本思想 (1)( )kkxB

5、xf 7問題問題: :(a) 如何建立迭代格式？如何建立迭代格式？(b) 向量向量序列序列 x(k) 是否收斂以及收斂條件是否收斂以及收斂條件? ?(1)( )kkxBxf AXb 82 例題分析例題分析: 其準(zhǔn)確解為其準(zhǔn)確解為X*= 1.1, 1.2, 1.3 ?？紤]解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2 (1)3.1Jacobi迭代法迭代法92 例題分析例題分析: 建立與式建立與式(1)(1)相等價(jià)的形式：相等價(jià)的形式：.xxxxxxxxx1232133120 10 20 720 10 20 830 20 20 84 (2)其準(zhǔn)確解為其準(zhǔn)

6、確解為X*=1.1, 1.2, 1.3?？紤]解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2 (1)3.1Jacobi迭代法迭代法102 例題分析例題分析: 其準(zhǔn)確解為其準(zhǔn)確解為X*=1.1, 1.2, 1.3。建立與式建立與式(1)(1)相等價(jià)的形式：相等價(jià)的形式：.xxxxxxxxx1232133120 10 20 720 10 20 830 20 20 84考慮解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2( )( )( )xxx0001230取迭代初值取迭代初值據(jù)此建立迭代公式：據(jù)此建立迭代公式： (

7、 +1)( )( )123( +1)( )( )213( +1)( )( )312=0.1+0.2+0.72=0.1+0.2+0.83=0.2+0.2+0.84kkkkkkkkkxxxxxxxxx11迭代結(jié)果如下表迭代結(jié)果如下表：迭 代 次 數(shù)迭 代 次 數(shù) x1 x2 x30 0 0 01 0 . 7 2 0 . 8 3 0 . 8 42 0 . 9 7 1 1 . 0 7 1 . 1 53 1 . 0 5 7 1 . 1 5 7 1 1 . 2 4 8 24 1 . 0 8 5 3 5 1 . 1 8 5 3 4 1 . 2 8 2 8 25 1 . 0 9 5 0 9 8 1 . 1 9

8、 5 0 9 9 1 . 2 9 4 1 3 86 1 . 0 9 8 3 3 8 1 . 1 9 8 3 3 7 1 . 2 9 8 0 3 97 1 . 0 9 9 4 4 2 1 . 1 9 9 4 4 2 1 . 2 9 9 3 3 58 1 . 0 9 9 8 1 1 1 . 1 9 9 8 1 1 1 . 2 9 9 7 7 79 1 . 0 9 9 9 3 6 1 . 1 9 9 9 3 6 1 . 2 9 9 9 2 41 0 1 . 0 9 9 9 7 9 1 . 1 9 9 9 7 9 1 . 2 9 9 9 7 51 1 1 . 0 9 9 9 9 3 1 . 1 9 9

9、 9 9 3 1 . 2 9 9 9 9 11 2 1 . 0 9 9 9 9 8 1 . 1 9 9 9 9 8 1 . 2 9 9 9 9 71 3 1 . 0 9 9 9 9 9 1 . 1 9 9 9 9 9 1 . 2 9 9 9 9 91 4 1 . 1 1 . 2 1 . 31 5 1 . 1 1 . 2 1 . 312 11,0(1,2, )1()(1,2, )nijjiiiiniiijjjiij ia xbainxba xina(1)11()(1,2, )nkkiiijijiij ixba xina 設(shè)方程組設(shè)方程組 AX=b , 通過分離變量的過程建立通過分離變量的過程建立

10、Jacobi迭代公式，即迭代公式，即 由此我們可以得到由此我們可以得到 Jacobi 迭代公式迭代公式：3.1 Jacobi3.1 Jacobi迭代公式迭代公式13(1)1( )1()kkxDLU xD b 雅可比迭代法的矩陣表示雅可比迭代法的矩陣表示 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111.1.1.10 iia寫成矩陣形式：寫成矩陣形式：A =LUD()()AxbDLU xbDxLU xb 11()xDLU xD b B

11、fJacobi 迭代陣迭代陣143.2 3.2 高斯高斯- -塞德爾迭代法塞德爾迭代法 (AX=b)(AX=b)(1)kix kkkixxx (1)(1)(1)121,( )( )( )121,kkkixxx 注意到利用注意到利用JacobiJacobi迭代公式計(jì)算迭代公式計(jì)算時(shí)，已經(jīng)計(jì)算好了時(shí)，已經(jīng)計(jì)算好了的值，而的值，而JacobiJacobi迭代公式并不利用這些最新的近似值計(jì)算，迭代公式并不利用這些最新的近似值計(jì)算，仍用仍用1(1)(1)111()(1,2, )inkkkiiijjijjjj iiixba xa xina 這啟發(fā)我們可以對(duì)其加以改進(jìn)這啟發(fā)我們可以對(duì)其加以改進(jìn), ,即在每個(gè)

12、分量的計(jì)算中盡即在每個(gè)分量的計(jì)算中盡量利用最新的迭代值，得到量利用最新的迭代值，得到上式稱為上式稱為 Gauss-Seidel 迭代法迭代法. .15)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 寫成寫成矩陣形式：矩陣形式：(1)1(1)()1()kk

13、kxDLxUxDb (1)()()kkDL xUxb (1)1( )1()()kkxDLUxDLb BfGauss-Seidel 迭代陣迭代陣3.2 3.2 高斯高斯- -塞德爾迭代法塞德爾迭代法16其準(zhǔn)確解為其準(zhǔn)確解為X*=1.1, 1.2, 1.3。.kkkkkkkkkxxxxxxxxx1232133121111110 10 20 720 10 20 830 20 20 84考慮解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2高斯高斯- -塞德爾迭代法算例塞德爾迭代法算例高斯高斯- -塞德爾迭代格式塞德爾迭代格式17迭代次數(shù)迭代次數(shù) x1 x2 x

14、3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.318開始Niyxii10,01i0T iiiiaTbx/ )(Ni 1iiix y jjxyNj,1Ni ix打印結(jié)果1ii( 0 )()1, 2.1, 21, 2,.0,

15、0,1, 23 .0,1, 2114 .1ijiiiijiiikiijjiiiNAaBbXxYyabbainajnbinnxxyinxkninjnbaxijxai 線 形 方 程 組 組 數(shù)系 數(shù) 矩 陣常 數(shù) 矩 陣迭 代 過 程 中 的 解 上 一 輪 迭 代 的 解將的 值 賦 給計(jì) 算 步 驟 ： 輸 入 原 始 數(shù) 據(jù) 輸 入 初 使 迭 代 值迭 代 計(jì) 算如， 則精 度 判 斷15 .1, 2iiiiinxyjnyxxin 如則轉(zhuǎn) 第 三 步 再 計(jì) 算打 印 計(jì) 算 結(jié) 果的 值TFTFT,1i jiabNijN輸 入1,ijjjNij TTa x 如19 逐次超松弛迭代法逐次

16、超松弛迭代法(Successive Over Relaxation Method，簡(jiǎn)寫為，簡(jiǎn)寫為SOR)可以看作帶參數(shù)可以看作帶參數(shù)的高斯的高斯-塞德塞德爾迭代法，是爾迭代法，是 G-S 方法的一種修正或加速，是求解大方法的一種修正或加速，是求解大型稀疏矩陣方程組的有效方法之一。型稀疏矩陣方程組的有效方法之一。3.3 3.3 超松馳迭代法超松馳迭代法SOR方法方法1. SOR基本思想基本思想 20 設(shè)方程組設(shè)方程組AX=b, 其中，其中，A=(aij) 為非奇異陣，為非奇異陣， x=(x1, x2, , xn)T, b=(b1, b2, , bn)T.假設(shè)已算出假設(shè)已算出 x(k) ，3.3

17、3.3 超松馳迭代法超松馳迭代法SOR方法方法2. SOR算法的構(gòu)造算法的構(gòu)造 ), 2 , 1()(1111) 1() 1(nixaxabaxnijkjijijkjijiiiki(1)(1)( )(1)( )( )(1)()kkkiiikkkiiixxxxxx 稱為松弛因子稱為松弛因子 利用高斯利用高斯-塞德爾迭代法得塞德爾迭代法得:213.3 3.3 超松馳迭代法超松馳迭代法SOR方法方法2. SOR算法的構(gòu)造算法的構(gòu)造 ( (基于基于G-S迭代迭代) ) 解方程組解方程組AX=b的逐次超松弛迭代公式：的逐次超松弛迭代公式： ), 2 , 1()()(11)1()()1(nixaxabax

18、xxxnijkjijijkjijiiiiikiki顯然，當(dāng)取顯然，當(dāng)取=1=1時(shí)，上式就是高斯時(shí)，上式就是高斯- -塞德爾迭代公式塞德爾迭代公式. .223.3 3.3 超松馳迭代法超松馳迭代法SOR方法方法2. SOR算法的構(gòu)造算法的構(gòu)造(基于基于Jacobi迭代迭代) 得到解方程組得到解方程組 AX=b 的逐次超松弛迭代公式：的逐次超松弛迭代公式： (1)( )( )1() (1,2, )kkiiinkiiijjjiixxxxba xina 顯然，上式就是顯然，上式就是 基于基于Jacobi 迭代的迭代的 SOR 方法方法.23下面令下面令 ，希望通過選取合適的希望通過選取合適的 來加速收

19、斂，這就是來加速收斂，這就是松弛法松弛法 。inkkiijjijjjba xa x- -1 1( ( + +1 1) )( ( ) )= =1 1j j= =i i- - -3. SOR算法的進(jìn)一步解釋算法的進(jìn)一步解釋 SOR方法方法inkkkiiijjijjj iiixba xa xa- -1 1( ( + +1 1) )( ( + +1 1) )( ( ) )j j= =1 1= = + +1 11 1= =- - -kkiiiirxa( ( + +1 1) )( ( ) )= =+ +其中其中ri(k+1) =相當(dāng)于在相當(dāng)于在 的基礎(chǔ)上的基礎(chǔ)上加個(gè)余項(xiàng)加個(gè)余項(xiàng)生成生成 。)(kix)1(

20、 kix0 1(漸次漸次)超松弛法超松弛法1kkkiiiiirxxaw( ( + +1 1) )( () )( ( ) )= =+ +24利用利用SOR方法方法解方程組解方程組SOR例題分析例題分析: :其準(zhǔn)確解為其準(zhǔn)確解為x* *=1, 1, 2.=1, 1, 2.xxxxxxxxx1 12 23 31 12 23 31 12 23 34 4- - 2 2- -= = 0 0- -2 2+ + 4 4- - 2 2= = - -2 2( (1 1) )- - - 2 2+ + 3 3= = 3 3xxxxxxxxx123123213213312312= 0.5+0.25= 0.5+0.25=

21、 0.5+0.5-0.5(2)= 0.5+0.5-0.5(2)1212=+1=+13333建立與式建立與式(1)(1)相等價(jià)的形式：相等價(jià)的形式：25據(jù)此建立據(jù)此建立G-S迭代公式：迭代公式：(k+1)(k)k123(k+1)(k+1)(k)213(k+1)(k+1)(k+1)312= 0.5+ 0.25= 0.5+ 0.5- 0.5(3)12=+ 133xxxxxxxxx取迭代初值取迭代初值: :( (0 0) )( (0 0) )( (0 0) )1 12 23 3= = = =1 1xxx,=1.5,=1.5,迭代結(jié)果如下表迭代結(jié)果如下表. . SORSOR迭代公式為：迭代公式為：(k+

22、1)(k)(k)(k)1123(k+1)(k)(k+1)(k)2213(k+1)(k)(k+1)(k+1)3312= (1-)+(0.5+0.25)x= (1-)+(0.5+0.5-0.5)(4)12= (1-)+(+1)33xw xwxxw xwxxxw xwxx26GS迭代法須迭代迭代法須迭代85次得到準(zhǔn)確值次得到準(zhǔn)確值 x*=1, 1, 2;而而SOR方法只須方法只須55次即得準(zhǔn)確值次即得準(zhǔn)確值. 由此可見，適當(dāng)?shù)剡x擇松弛由此可見，適當(dāng)?shù)剡x擇松弛因子因子，SOR法具有法具有明顯的明顯的加速收斂效果加速收斂效果. . 逐次超松弛迭代法逐次超松弛迭代法次數(shù)次數(shù) x1 x2 x3 1 0.62

23、5000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 15 0.991521 0.985318 1.987416 25 0.998596 0.998234 1.998355 55 1.00000 1.0000 2.000027 關(guān)于關(guān)于SOR方法的說明：方法的說明：u顯然，當(dāng)顯然，當(dāng) 時(shí)，時(shí)，SOR方法就是方法就是Gauss- Seidel方法。方法。uSOR 方法每一次迭

24、代的主要運(yùn)算量是計(jì)算一次矩陣與向量方法每一次迭代的主要運(yùn)算量是計(jì)算一次矩陣與向量的乘法。的乘法。u 時(shí)稱為超松弛方法，時(shí)稱為超松弛方法， 時(shí)稱為低松弛方法。時(shí)稱為低松弛方法。u計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用 控制迭代終止，或用控制迭代終止，或用 uSOR方法可以看成是方法可以看成是Gauss-Seidel方法的一種修正。方法的一種修正。111(1)( )11maxmaxkkiiii ni nxxx ( )( )kkrbAx28 （迭代法基本定理）（迭代法基本定理） 設(shè)有方程組設(shè)有方程組 ，對(duì)于任意的初始向，對(duì)于任意的初始向量量 ，迭代公式，迭代公式 收斂的充要條件是迭收斂的充要條件是迭代矩陣

25、代矩陣 的譜半徑的譜半徑 . . 3.4 3.4 迭代法的收斂性迭代法的收斂性- -充要條件充要條件xBxf(1)( )kkxBxf(0)xB( )1B 迭代法的基本定理在理論分析中有重要意義。迭代法的基本定理在理論分析中有重要意義。29 （迭代法收斂的充分條件）（迭代法收斂的充分條件） 設(shè)方程組設(shè)方程組 迭代法為迭代法為如果有如果有 的某種算子范數(shù)滿足的某種算子范數(shù)滿足 ，則，則 在具體使用上，由于在具體使用上，由于 ，因此，我們利，因此，我們利用范數(shù)可以建立判別迭代法收斂的充分條件。用范數(shù)可以建立判別迭代法收斂的充分條件。 ( )BBxBxf(1)( )kkxBxf1BLB()*limkk

26、xx 3.4 3.4 迭代法的收斂性迭代法的收斂性- -充分條件充分條件30關(guān)于解某些特殊方程組迭代法的收斂性關(guān)于解某些特殊方程組迭代法的收斂性定義：定義：( (對(duì)角占優(yōu)陣對(duì)角占優(yōu)陣) ) 設(shè)設(shè)(1) (1) 如果如果 元素滿足元素滿足 稱稱 為為嚴(yán)格對(duì)角占優(yōu)陣嚴(yán)格對(duì)角占優(yōu)陣(2) (2) 如果如果 元素滿足元素滿足 且上式至少有一個(gè)不等式嚴(yán)格成立，且上式至少有一個(gè)不等式嚴(yán)格成立， 稱稱 為為弱對(duì)角占優(yōu)陣弱對(duì)角占優(yōu)陣。()ijn nAaA1(1,2, )niiijjjiaainAA1(1,2, )niiijjj iaainA31 設(shè)設(shè) ，如果：，如果： 為嚴(yán)格對(duì)角占優(yōu)，則解為嚴(yán)格對(duì)角占優(yōu)，則解

27、 的的Jacobi迭代法，迭代法， Gauss-Seidel迭代法均收斂。迭代法均收斂。AxbAAxb3233103)(2103)(151)1(3)(321)(141)1(2512)(351)(252)1(15kkkkkkkkkxxxxxxxxx(1), =1,2,3kixi(1)( )( )2112123555(1)( )( )1112222310205(1)( )( )112132320810kkkkkkkkkxxxxxxxxxSeidel迭代格式為迭代格式為 從式中解出從式中解出故可得故可得Seidel迭代矩陣為迭代矩陣為2155111102011208000sB從例中可以看出從例中可以

28、看出Jacobi迭代矩陣迭代矩陣Bj的主對(duì)角線為零，而的主對(duì)角線為零，而Seidel迭代矩陣迭代矩陣Bs的第的第1列都是零，這對(duì)一般情況也是成立的。列都是零，這對(duì)一般情況也是成立的。 34舉例檢驗(yàn)舉例檢驗(yàn)JacoaiJacoai迭代的收斂性迭代的收斂性首先將原方程組寫為迭代形式的方程組，即：首先將原方程組寫為迭代形式的方程組，即：求任一行之和的最大值求任一行之和的最大值1,1,即：即： |M|=max5/8,5/11,9/12=9/121i或求任一列之和的最大值或求任一列之和的最大值1,即：即： |M|1=max114/132,60/96,30/88=114/1321時(shí)，則方程組是時(shí)，則方程組是“病態(tài)病態(tài)”的；的；當(dāng)當(dāng)cond(A)較小時(shí)，則方程組是較小時(shí)，則方程組是“良態(tài)良態(tài)”的的.通常的條件數(shù)有：通常的條件數(shù)有：:特別地，若特別地，若 A 對(duì)稱，則對(duì)稱，則|min|max)( 2Acond 11Cond AAA()( )|-=12222maxminTTCond AAAA AA A()( )|()/()-=ll71例題例題已知已知, 求求A的條件數(shù)的條件數(shù).解：由解：由0)det(AI000050504. 0980050504. 121212)(Acond 說明由說明由A構(gòu)成的系數(shù)矩陣方程組是構(gòu)成的系數(shù)矩陣方程組是“病態(tài)病態(tài)”的的 。392061