38第八节雅可比与高斯塞德尔迭代法精编版

1、数学学院 信息与计算科学系 第八节 雅可比迭代法 与高斯塞德尔迭代法 取初始向量 x(0)按下列迭代格式 基本思想： 将方程组 Ax=b ( | A|? ?0 ) 转化为与其 等价的方程组 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? ?数学学院 信息与计算科学系 问题： 如何构造迭代格式，迭代法产生的 向量 序列x(k)的收敛条件，收敛速度，误差估计等。 一、雅可比迭代法 设方程组

2、 ? ?a11x1? ?a12x2? ? ?a1nxn? ?a x? ?a x? ? ?a x? ?21 122 22nn? ? ? ? ?an1x1? ?an2x2? ? ?annxn? ?b1? ?b2? ?bn数学学院 信息与计算科学系 等 价 方 程 组 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) 数学学院 信息与计算科学系

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? ?数学学院 信息与计算科学系 或缩写为 x(k? ?1 )i1(k)? ?(? ? ?aijxj? ?aiij? ?1i? ?1j? ?i? ?1? ?aijxn

4、(k)j? ?bi)(i? ?1 ,2 ,?,n)称为雅可比(Jacobi)迭代法，又称简单迭代法。 数学学院 信息与计算科学系 记矩阵 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? ?数学学院 信息与计算科学系 于是雅可

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数学学院 信息与计算科学系 例如 已知线性方程组 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数学学院 信息与计算科学系 二、高斯塞德尔迭代法 在 Jacobi 迭代中,计算xi(k+1)（2? ? i ? ? n）时,使用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? ?数学学院 信息与计算科学系 或缩写为 (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 数学学院 信息与计算科学系 例如 已知线性方程组 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数学学院 信息与计算科学系 例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? ?数学学院 信息与计算科学系 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计算如下 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 数学学院 信息与计算科学系 例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? ?数学学院 信息与计算科学系 ? ?(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 计算如下： k 1 8 x1(k) 0.72 1.099998 x2(k) 0.902 1.199999 x3(k) 1.1644 1.3 数学学院 信息与计算科学系 三、迭代收敛的充分条

13、件 定理 1 在下列任一条件下，雅克比迭代法收敛。 ? ?1? ? ?2? ? ?3? ?B1? ? ?max? ?innaijaiiaijaii? ?1j? ?1j? ?iB11? ?max? ?j? ?1T? ? ?1ni? ?1j? ?iI? ?D A? ?max? ?jaijajj? ?1i? ?1i? ?j数学学院 信息与计算科学系 定理 2 设B1, B2分别为雅克比迭代矩阵与高斯塞德尔迭代矩阵，则 . B2? ? ?B1? ?naijB1? ? ?max? ? ?1时， 从而，当 ij? ?1aii高斯塞德尔迭代法收敛。 (证明见书P77) 定 义1 设n 阶矩阵A=(aij)n

14、n，如果 |aii|? ? ?|aij|( i? ?1,2,? ,n)j? ?ij? ?i或 |ajj|? ? ?|aij|i? ?j( j? ?1,2,?,n) 则称矩阵A为行（或列）严格对角占优。 数学学院 信息与计算科学系 定理3 若矩阵A行（或列）严格对角占优，则解线性方程组Ax=b的Jacobi 迭代法和Gauss-Seidel 迭代法均收敛 。 证 设矩阵A 行严格对角占优, 由 ? ?0? ? ? ? ?a21? ?1BJ? ?D(L? ?U)? ? ? ?a22? ? ?a? ? ?n1? ?anna12? ?a110?an2? ?ann?a1n? ? ? ?a11? ?a2n

15、? ? ?a22? ? ? ?0? ? ?数学学院 信息与计算科学系 因为 所以有 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 迭代收敛. 由此根据第五节定理4 知道(I- -BJ)是非奇异矩阵，因此 A=D(I- -BJ)也是非奇异矩阵. 结论 若矩阵A行(或列)严格对角占优，则A是非奇异矩阵. 数学学院 信息与计算科学系 下面证明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)数学学院 信息与计算科学系 |? ?aii|? ? ?|

17、? ?aij|? ? ?|? ?aij|? ?i? ?1即矩阵 j? ?ij? ?1j? ?i? ?1? ?|aij|n(i? ?1,2,? ,n)是行严格对角占优矩阵 , 由结论知它是非奇异矩阵, 这与式(1) 矛盾, 所以|? ? |1, 从而 ? ?(BG)0 。 令 -Ly, y=a+ib，则由复向量内积的性质有 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数学学院 信息与计算科学系 定理5 若 Jacobi 迭代矩阵BJ 为非负矩阵，则下 列关系有一个且仅有一个成立： (1) ? ?(BJ )= ? ?(BG )=0 ； (2) 0 ? ?(BG) ? ?(BJ )1； (3) ? ?(BJ )= ? ?(BG )=1 ； (4) 1 ? ?(BJ ) ? ?(BG ). 说明：当 Jacobi 迭代矩阵 BJ 为非负矩阵时, Jacobi 方法和 Gauss Seidel 方法同时收敛或同时发散, 若为同时收敛, 则后者比前者收敛快。 数学学院 信息与计算科学系 例 3 已知方程组 ? ?0.50? ? ?x1? ? ?0.7? ? ?1? ? ?0.5? ? ? ? ? ?1? ?0.5 x2? ?0.8? ? ? ? ? ? ?0? ?