第八节-雅可比与高斯—塞德尔迭代法课件.ppt

1、数学学院 信息与计算科学系生成向量序列生成向量序列 x(k)，若，若 xxkk)(lim称为迭代格式（称为迭代格式（1）的迭代矩阵。）的迭代矩阵。则有则有x*=Bx*+f，即即x*为原方程组为原方程组Ax=b 的解，的解，B基本思想：基本思想：将方程组将方程组 Ax=b(|A|0)转化为与其转化为与其 等价的方程组等价的方程组 x=Bx+fx(k+1)=Bx(k)+f （k=0,1,2,)(1)取初始向量取初始向量 x(0)按下列迭代格式按下列迭代格式 第八节第八节 雅可比迭代法雅可比迭代法 与高斯与高斯塞德尔迭代法塞德尔迭代法数学学院 信息与计算科学系序列序列x(k)的收敛条件的收敛条件，收

2、敛速度收敛速度，误差估计等误差估计等。问题问题：如何构造迭代格式如何构造迭代格式，迭代法产生的迭代法产生的 向量向量设方程组设方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111一、雅可比迭代法一、雅可比迭代法数学学院 信息与计算科学系其中其中 aii 0(i=1,2,n)等等价价方方程程组组11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba 数学学院 信息与计算科学系建立迭代格式建立迭代格式 )(1)(1)(1)(11)(11)1(2)(2)(323)(12122)

3、1(21)(1)(313)(21211)1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax数学学院 信息与计算科学系 称为称为雅可比雅可比(Jacobi)迭代法迭代法，又称简单迭代法又称简单迭代法。或缩写为或缩写为)(11)(11)()1(inijkjj iijkjj iiikibxaxaax ),2,1(ni 数学学院 信息与计算科学系111212122212nnnnnnaaaaaaAaaa 1122nnaaDa 2112000nnaLaa1212000nnaaaU记矩阵记矩阵 A=D-L-U，其中，其中数学学院 信息与计算科学系于是雅可比

4、迭代法可写为于是雅可比迭代法可写为矩阵形式矩阵形式bDxULDxkk1)(1)1()(其其Jacobi迭代矩阵迭代矩阵为为 B1=BJ=D-1-1(L+U)，即，即 )(1ULDBJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa数学学院 信息与计算科学系例如例如已知线性方程组已知线性方程组 Ax=b 的矩阵为的矩阵为1()JBDLU 其其雅可比迭代矩阵雅可比迭代矩阵为为2111.5A 1322001010 1223001010 122300 数学学院 信息与计算科学系在在 Jacobi 迭代中迭代中,计算计算xi(k+1)（2 i n）时）时,使用使用xj(k

5、+1)代替代替xj(k)（1 j i-1），即即 )(1)(1)(1)1(11)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax建建立立迭迭代代格格式式二、高斯二、高斯塞德尔迭代法塞德尔迭代法数学学院 信息与计算科学系或缩写为或缩写为nixaxabaxijnijkjijkjijiiiki,2,11111)()1()1(称为称为高斯高斯塞德尔塞德尔（Gauss Seidel）迭代法迭代法。其其G-S迭代矩阵迭代矩阵为为B2=BG=(D-L)-1UbLDx

6、ULDxkk1)(1)1()()(于是高斯于是高斯塞德尔迭代法可写为塞德尔迭代法可写为矩阵形式矩阵形式数学学院 信息与计算科学系例如例如已知线性方程组已知线性方程组 Ax=b 的矩阵为的矩阵为1()GBDLU 其其G-S迭代矩阵迭代矩阵为为2111.5A 1322001100 32010130012 121300 数学学院 信息与计算科学系 例例1 用雅可比迭代法解方程组用雅可比迭代法解方程组 2.453.82102.7210321321321xxxxxxxxx 3.12.11.1x )2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1

7、kkkkkkkkkxxxxxxxxx解：解：Jacobi 迭代格式为迭代格式为精精确确解解是是数学学院 信息与计算科学系kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15111.0999931.1999931.299991121.0999981.1999981.299997 取取计算如下计算如下Tx)0,0,0()0()2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx数学学院 信息与计算科学系 解：解：Gauss-Seidel迭代格式为迭代格式为 )2.4(51)

8、3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 例例2 用用GaussSeidel 迭代法解上题。迭代法解上题。2.453.82102.7210321321321xxxxxxxxx数学学院 信息与计算科学系取取 x(0)=(0,0,0)T 计算如下：计算如下：kx1(k)x2(k)x3(k)10.720.9021.164481.0999981.1999991.3 )2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxx

9、xxxx数学学院 信息与计算科学系定理定理 1 在下列任一条件下，雅克比迭代法收敛。在下列任一条件下，雅克比迭代法收敛。1max31max21max11111111 njiijjijjTnijiiiijjnijjiiijiaaADIaaBaaB三、迭代收敛的充分条件三、迭代收敛的充分条件数学学院 信息与计算科学系定理定理 2 设设B1,B2分别为雅克比迭代矩阵与高分别为雅克比迭代矩阵与高斯斯塞德尔迭代矩阵，则塞德尔迭代矩阵，则 .21BB 从而，当从而，当 时，时，1max11 nijjiiijiaaB高斯高斯塞德尔迭代法收敛。塞德尔迭代法收敛。定定 义义1 设设n 阶矩阵阶矩阵A=(aij)

10、nn，如果，如果 则称矩阵则称矩阵A为行（或列）为行（或列）严格对角占优严格对角占优。ijijiiniaa),2,1(|jiijjjnjaa),2,1(|或或(证明见书证明见书P77)数学学院 信息与计算科学系定理定理3 若矩阵若矩阵A行（或列）严格对角占优，则解行（或列）严格对角占优，则解线性线性方程组方程组Ax=b的的Jacobi 迭代法和迭代法和Gauss-Seidel 迭代迭代法均收敛法均收敛。证证 设矩阵设矩阵A 行严格对角占优行严格对角占优,由由)(1ULDBJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa数学学院 信息与计算科学系 由此根据第五节

11、定理由此根据第五节定理4知道知道(I-BJ)是非奇异矩是非奇异矩阵阵，因此因此 A=D(I-BJ)也是非奇异矩阵也是非奇异矩阵.因为因为所以所以 Jacobi 迭代收敛迭代收敛.ijijiiniaa),2,1(|11,1,11maxmax1nnijJiji ni nj i jj i jiiiiaBaaa 所以有所以有结论结论 若矩阵若矩阵A行行(或列或列)严格对角占优，则严格对角占优，则A是是非奇异矩阵非奇异矩阵.数学学院 信息与计算科学系)(det)det(1ULDIBIG 0)(det)det(1 ULDLD)1(0)(det ULD 下面证明下面证明GaussSeidel 迭代法收敛迭代

12、法收敛.ULDBG1)(，得，得 由由 ijnijijijijijiiniaaaa),2,1(|111 下面证明下面证明|1.若不然若不然,即有即有 使使|1,则则这说明这说明(D-L)-U是是奇异矩阵奇异矩阵.数学学院 信息与计算科学系 ijnijijijijijiiniaaaa),2,1(|111 是行严格对角占优矩阵是行严格对角占优矩阵,由结论知它是由结论知它是非奇异矩阵非奇异矩阵,这与式这与式(1)矛盾矛盾,所以所以|1,从而从而 (BG)0。所以所以|1，从而，从而 (BG)1，故，故GaussSeidel迭代法迭代法收敛。收敛。,)(,ibaibayyLyyDyyLT 1)(|22

13、222 baba )(,ibayyLyLyyyLT 令令 -Ly,y=a+ib，则由复向量内积的性质有，则由复向量内积的性质有数学学院 信息与计算科学系定理定理5 若若 Jacobi 迭代矩阵迭代矩阵BJ 为非负矩阵，为非负矩阵，则下则下 列关系有一个且仅有一个成立：列关系有一个且仅有一个成立：(1)(BJ)=(BG)=0；(2)0 (BG)(BJ)1；(3)(BJ)=(BG)=1；(4)1 (BJ)(BG).说明：说明：当当 Jacobi 迭代矩阵迭代矩阵 BJ 为非负矩阵时为非负矩阵时,Jacobi 方法和方法和 GaussSeidel 方法同时收敛或同时发方法同时收敛或同时发散散,若为同

14、时收敛若为同时收敛,则后者比前者收敛快。则后者比前者收敛快。数学学院 信息与计算科学系例例 3 已知方程组已知方程组12310.500.70.510.50.800.510.9xxx 判断雅可比迭代判断雅可比迭代法和高斯法和高斯塞德尔法的敛散性？塞德尔法的敛散性？00.500.500.500.50JB 解解 雅可比迭代矩阵雅可比迭代矩阵数学学院 信息与计算科学系20.50det()0.50.5(0.5)00.5JIB 15.0)(JB 故故Jacobi 迭代迭代法收敛。法收敛。再由定理再由定理5 的的 2)或由或由 A是对称是对称正定正定阵阵知知 GaussSeidel迭代法也收敛，且比迭代法也收敛，且比 Jacobi 迭代迭代法收敛得快。法收敛得快。