38第八節(jié)雅可比與高斯塞德爾迭代法精編版

1、數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 第八節(jié) 雅可比迭代法 與高斯塞德爾迭代法 取初始向量 x(0)按下列迭代格式 基本思想： 將方程組 Ax=b ( | A|? ?0 ) 轉(zhuǎn)化為與其 等價(jià)的方程組 x = Bx+f (k+1) (k)x= Bx + f （k=0,1,2,?) (1) 生成向量序列 x(k) ，若 則有x* =Bx*+f ， 即x*為原方程組Ax=b 的解，B 稱為迭代格式（1 ）的迭代矩陣。 k? ? ? ?lim x(k)? ?x? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 問題： 如何構(gòu)造迭代格式，迭代法產(chǎn)生的 向量 序列x(k)的收斂條件，收斂速度，誤差估計(jì)等。 一、雅可比迭代法 設(shè)方程組

2、 ? ?a11x1? ?a12x2? ? ?a1nxn? ?a x? ?a x? ? ?a x? ?21 122 22nn? ? ? ? ?an1x1? ?an2x2? ? ?annxn? ?b1? ?b2? ?bn數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 等 價(jià) 方 程 組 1? ?x? ? ?a x? ? ?a x? ?b 112 21nn1? ?a11? ?1? ?x2? ? ?a21x1? ? ? ?a2nxn? ?b2? ?a22? ? ?1? ?an1x1? ?an2x2? ? ?bn? ?xn? ?ann? ?其中 aii? ?0 ( i=1 , 2 , , n) 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系

3、建立迭代格式 ? ?(k? ?1 )1(k)(k)(k)x? ?(? ?a x? ?a x? ? ?a x? ?b )11221331 n n1? ?a11? ? ?x(k? ?1 )? ?1(? ?a x(k)(k)(k)? ?a23x3? ? ?a2 nxn? ?b2)? ?2211a22? ? ? ? ?x(k? ?1 )? ?1(? ?a x(k)? ? ?a(k)xn? ?1? ?bn)nn1 1nn? ?1? ?ann? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 或縮寫為 x(k? ?1 )i1(k)? ?(? ? ?aijxj? ?aiij? ?1i? ?1j? ?i? ?1? ?aijxn

4、(k)j? ?bi)(i? ?1 ,2 ,?,n)稱為雅可比(Jacobi)迭代法，又稱簡(jiǎn)單迭代法。 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 記矩陣 A=D- -L- -U ，其中 ? ?a11? ?a21? ?A? ? ? ?a? ?n1? ?0? ?a21? ? ?L? ? ? ?a? ?n1a12a22an20an2a1n? ? ?a2n? ? ? ?ann? ? ? ? ? ? ?0? ? ?a11? ?D? ? ? ? ? ?a22? ? ? ? ? ?ann? ? ?0 a12? ?0? ?U? ? ? ? ? ?a1n? ? ?a2n? ? ? ?0? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 于是雅可

5、比迭代法可寫為 矩陣形式 x(k? ?1)? ?D (L? ?U)x? ?1(k)? ?D ba1n? ? ? ?a11? ?a2n? ? ?a22? ? ? ?0 ? ? ? ? ?1其Jacobi 迭代矩陣為 B1=BJ -1-1=D (L+U) ，即 ? ?0? ? ?a21? ? ? ?1BJ? ?D (L? ?U)? ? ?a22? ? ?a? ? ?n1? ?a? ?nna12? ?a110?an2? ?ann數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 例如 已知線性方程組 Ax=b 的矩陣為 ? ?2? ?1? ?A ? ? ? ? ?1 1.5? ?其雅可比迭代矩陣為 2 001? ? ? ?

6、 ? ?1BJ? ?D (L? ?U)? ? ? ? ?3? ?0? ?1 0? ? ? ?2? ?11? ?20? ? ?01? ? ?02? ? ? ? ? ? ?2? ? ?2? ?0? ?0? ?1 0? ? ?3? ? ? ?3? ? ?1數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 二、高斯塞德爾迭代法 在 Jacobi 迭代中,計(jì)算xi(k+1)（2? ? i ? ? n）時(shí),使用xj(k+1)代替xj(k) （1? ? j ? ? i-1 ），即 ? ?(k? ?1 )1(k)(k)(k)x? ?(? ?a x? ?a x? ? ?a x? ?b)112 213 31 nn1a11建 ? ? ?

7、立 ? ?(k? ?1 )1(k? ?1 )(k)(k)x? ?(? ?a x? ?a x? ? ?a x? ?b )221 123 32 nn2? ?迭 a22? ?代 ? ?格 ? ?1(k? ?1 )(k? ?1 )(k? ?1 )? ?式 xn? ?(? ?an1x1? ? ?ann? ?1xn? ?1? ?bn)? ?ann? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 或縮寫為 (k? ?1)xii? ?11(k? ?1 )? ?bi? ? ?aijxj? ?aiij? ?1(k)aijxjj? ?i? ?1n? ?i? ?1 ,2 ,?n稱為高斯塞德爾（Gauss Seidel）迭代法。 于是

8、高斯塞德爾迭代法可寫為 矩陣形式 x? ?(D? ?L) Ux其G-S 迭代矩陣為 (k? ?1)? ?1(k)? ?(D? ?L) b? ?1B2 = BG =(D- -L)- -1U 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 例如 已知線性方程組 Ax=b 的矩陣為 ? ?2? ?1? ?A ? ? ? ? ?1 1.5? ?其G-S 迭代矩陣為 2 00 1? ? ? ? ? ?1BG? ?(D? ?L) U? ? ? ? ?3? ?10 0? ? ? ?2? ?131? ?20? ? ?0 1? ? ?02? ? ? ? ? ? ? ? ?1? ?3? ? ?1 2? ? ?0 0? ? ?0? ?

9、3? ? ?1數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 例1 用雅可比迭代法解方程組 ? ?10 x1? ?x2? ?2x3? ?7 .2? ? ? ?x1? ?10 x2? ?2x3? ?8 .3? ? ?x? ?x? ?5x? ?4 .2? ?1231? ?(k? ?1 )(k)(k)解： x? ?(x? ?2x? ?7 .2 )123? ?10Jacobi ? ?迭代格式為 ? ?(k? ?1 )1(k)(k)? ?( x1? ?2x3? ?8 .3 )? ?x210? ? ?(k? ?1 )1(k)(k)x? ?( x? ?x? ?4 .2 )312? ?5? ?精? ?1 .1? ? ?確? ?

10、?x ? ?1 .2? ? ?解? ? ?是 ? ?1 .3? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 1? ?(k? ?1)(k )(k )x? ?(x? ?2x? ?7.2)123? ?10? ?1? ?(k? ?1)(k )(k )x? ?( x? ?2x? ?8.3)? ?21310? ?1? ?(k? ?1)(k )(k )x? ?( x? ?x? ?4.2)312? ?5? ? 取 x(0)? ?(0 ,0 ,0)T計(jì)算如下 k x1(k) x2(k) x3(k) 1 0.72 0.83 0.84 2 0.971 1.07 1.15 11 1.099993 1.199993 1.299991

11、 12 1.099998 1.199998 1.299997 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 例2 用GaussSeidel 迭代法解上題。 ? ?10 x1? ?x2? ?2x3? ?7.2? ? ? ?x1? ?10 x2? ?2x3? ?8.3? ? ?x? ?x? ?5x? ?4.2? ?123? ?(k? ?1)1(k)(k)x? ?(x? ?2x? ?7 .2 )123 解： ? ?10Gauss-Seidel ? ? ?(k? ?1)1(k? ?1)(k)? ?( x1? ?2x3? ?8 .3 )迭代格式為 ? ?x210? ? ?(k? ?1)1(k? ?1)(k? ?1)x?

12、?( x? ?x? ?4 .2 )312? ?5? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 ? ?(k? ?1)1(k)(k)x? ?(x? ?2x? ?7.2)123? ?10? ? ?(k? ?1)1(k? ?1)(k)? ?( x1? ?2x3? ?8.3)? ?x210? ? ?(k? ?1)1(k? ?1)(k? ?1)x? ?( x? ?x? ?4 .2)312? ?5? ?取 x(0)=(0,0,0)T 計(jì)算如下： k 1 8 x1(k) 0.72 1.099998 x2(k) 0.902 1.199999 x3(k) 1.1644 1.3 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 三、迭代收斂的充分條

13、件 定理 1 在下列任一條件下，雅克比迭代法收斂。 ? ?1? ? ?2? ? ?3? ?B1? ? ?max? ?innaijaiiaijaii? ?1j? ?1j? ?iB11? ?max? ?j? ?1T? ? ?1ni? ?1j? ?iI? ?D A? ?max? ?jaijajj? ?1i? ?1i? ?j數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 定理 2 設(shè)B1, B2分別為雅克比迭代矩陣與高斯塞德爾迭代矩陣，則 . B2? ? ?B1? ?naijB1? ? ?max? ? ?1時(shí)， 從而，當(dāng) ij? ?1aii高斯塞德爾迭代法收斂。 (證明見書P77) 定 義1 設(shè)n 階矩陣A=(aij)n

14、n，如果 |aii|? ? ?|aij|( i? ?1,2,? ,n)j? ?ij? ?i或 |ajj|? ? ?|aij|i? ?j( j? ?1,2,?,n) 則稱矩陣A為行（或列）嚴(yán)格對(duì)角占優(yōu)。 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 定理3 若矩陣A行（或列）嚴(yán)格對(duì)角占優(yōu)，則解線性方程組Ax=b的Jacobi 迭代法和Gauss-Seidel 迭代法均收斂 。 證 設(shè)矩陣A 行嚴(yán)格對(duì)角占優(yōu), 由 ? ?0? ? ? ? ?a21? ?1BJ? ?D(L? ?U)? ? ? ?a22? ? ?a? ? ?n1? ?anna12? ?a110?an2? ?ann?a1n? ? ? ?a11? ?a2n

15、? ? ?a22? ? ? ?0? ? ?數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 因?yàn)?所以有 BJ? ?|aii|? ? ?|aij|j? ?i( i? ?1,2,?,n)aijaii1? ?max1? ?i? ?naii? ?max1? ?i? ?nj? ?i,j? ?1? ?n? ?j? ?i,j? ?1? ?naij? ?1所以 Jacobi 迭代收斂. 由此根據(jù)第五節(jié)定理4 知道(I- -BJ)是非奇異矩陣，因此 A=D(I- -BJ)也是非奇異矩陣. 結(jié)論 若矩陣A行(或列)嚴(yán)格對(duì)角占優(yōu)，則A是非奇異矩陣. 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 下面證明GaussSeidel 迭代法收斂. ? ?1由

16、BG? ?(D? ?L) U，得 det(? ?I? ?BG)? ?det? ?I? ?(D? ?L) U? ?det( D? ?L) det? ?(D? ?L)? ?U? ?0? ?det? ?(D? ?L)? ?U? ?0(1 )這說明? ?(D- -L)- -U是奇異矩陣. 下面證明|? ? |1. 若不然, 即有? ? 使|? ? |? ?1, 則 |? ?aii|? ? ?|? ?aij|? ? ?|? ?aij|? ?j? ?ij? ?1i? ?1j? ?i? ?1? ?1? ?1? ?|aij|n( i? ?1,2,?,n)數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 |? ?aii|? ? ?|

17、? ?aij|? ? ?|? ?aij|? ?i? ?1即矩陣 j? ?ij? ?1j? ?i? ?1? ?|aij|n(i? ?1,2,? ,n)是行嚴(yán)格對(duì)角占優(yōu)矩陣 , 由結(jié)論知它是非奇異矩陣, 這與式(1) 矛盾, 所以|? ? |1, 從而 ? ?(BG)0 。 令 -Ly, y=a+ib，則由復(fù)向量?jī)?nèi)積的性質(zhì)有 L y,y? ?y,Ly? ?Ly,y? ? ? ?(a? ?ib)L y,y? ?a? ?ib? ? ? ?,Dy,y? ?Ly,y(? ? ?a)? ?iba? ?b|? ?|? ? ?122(? ? ?a)? ?b所以|? ? |1 ，從而 ? ?( BG)1，故Gau

18、ssSeidel 迭代法收斂。 222TT數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 定理5 若 Jacobi 迭代矩陣BJ 為非負(fù)矩陣，則下 列關(guān)系有一個(gè)且僅有一個(gè)成立： (1) ? ?(BJ )= ? ?(BG )=0 ； (2) 0 ? ?(BG) ? ?(BJ )1； (3) ? ?(BJ )= ? ?(BG )=1 ； (4) 1 ? ?(BJ ) ? ?(BG ). 說明：當(dāng) Jacobi 迭代矩陣 BJ 為非負(fù)矩陣時(shí), Jacobi 方法和 Gauss Seidel 方法同時(shí)收斂或同時(shí)發(fā)散, 若為同時(shí)收斂, 則后者比前者收斂快。 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 例 3 已知方程組 ? ?0.50? ? ?x1? ? ?0.7? ? ?1? ? ?0.5? ? ? ? ? ?1? ?0.5 x2? ?0.8? ? ? ? ? ? ?0? ?