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

《第八节-雅可比与高斯—塞德尔迭代法课件.ppt》由会员分享，可在线阅读，更多相关《第八节-雅可比与高斯—塞德尔迭代法课件.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学学院 信息与计算科学系生成向量序列生成向量序列 x(k)，若，若称为迭代格式（称为迭代格式（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、估计等误差估计等。问题问题：如何构造迭代格式如何构造迭代格式，迭代法产生的迭代法产生的 向量向量设方程组设方程组一、雅可比迭代法一、雅可比迭代法数学学院 信息与计算科学系其中其中 aii 0(i=1,2,n)等等价价方方程程组组数学学院 信息与计算科学系建立迭代格式建立迭代格式数学学院 信息与计算科学系 称为称为雅可比雅可比(Jacobi)迭代法迭代法，又称简单迭代法又称简单迭代法。或缩写为或缩写为数学学院 信息与计算科学系记矩阵记矩阵 A=D-L-U，其中，其中数学学院 信息与计算科学系于是雅可比迭代法可写为于是雅可比迭代法可写为矩阵形式矩阵形式其其Jacobi迭代矩阵迭代矩阵为为 B1=B

3、J=D-1-1(L+U)，即，即数学学院 信息与计算科学系例如例如已知线性方程组已知线性方程组 Ax=b 的矩阵为的矩阵为其其雅可比迭代矩阵雅可比迭代矩阵为为数学学院 信息与计算科学系在在 Jacobi 迭代中迭代中,计算计算xi(k+1)（2 i n）时）时,使用使用xj(k+1)代替代替xj(k)（1 j i-1），即即建建立立迭迭代代格格式式二、高斯二、高斯塞德尔迭代法塞德尔迭代法数学学院 信息与计算科学系或缩写为或缩写为称为称为高斯高斯塞德尔塞德尔（Gauss Seidel）迭代法迭代法。其其G-S迭代矩阵迭代矩阵为为B2=BG=(D-L)-1U于是高斯于是高斯塞德尔迭代法可写为塞德尔

4、迭代法可写为矩阵形式矩阵形式数学学院 信息与计算科学系例如例如已知线性方程组已知线性方程组 Ax=b 的矩阵为的矩阵为其其G-S迭代矩阵迭代矩阵为为数学学院 信息与计算科学系 例例1 用雅可比迭代法解方程组用雅可比迭代法解方程组解：解：Jacobi 迭代格式为迭代格式为精精确确解解是是数学学院 信息与计算科学系kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15111.0999931.1999931.299991121.0999981.1999981.299997 取取计算如下计算如下数学学院 信息与计算科学系 解：解：Gauss-Seidel迭代格式为迭代格

5、式为 例例2 用用GaussSeidel 迭代法解上题。迭代法解上题。数学学院 信息与计算科学系取取 x(0)=(0,0,0)T 计算如下：计算如下：kx1(k)x2(k)x3(k)10.720.9021.164481.0999981.1999991.3数学学院 信息与计算科学系定理定理 1 在下列任一条件下，雅克比迭代法收敛。在下列任一条件下，雅克比迭代法收敛。三、迭代收敛的充分条件三、迭代收敛的充分条件数学学院 信息与计算科学系定理定理 2 设设B1,B2分别为雅克比迭代矩阵与高斯分别为雅克比迭代矩阵与高斯塞德尔迭代矩阵，则塞德尔迭代矩阵，则 .从而，当从而，当 时，时，高斯高斯塞德尔迭代

6、法收敛。塞德尔迭代法收敛。定定 义义1 设设n 阶矩阵阶矩阵A=(aij)nn，如果，如果 则称矩阵则称矩阵A为行（或列）为行（或列）严格对角占优严格对角占优。或或(证明见书证明见书P77)数学学院 信息与计算科学系定理定理3 若矩阵若矩阵A行（或列）严格对角占优，则解行（或列）严格对角占优，则解线性线性方程组方程组Ax=b的的Jacobi 迭代法和迭代法和Gauss-Seidel 迭代迭代法均收敛法均收敛。证证 设矩阵设矩阵A 行严格对角占优行严格对角占优,由由数学学院 信息与计算科学系 由此根据第五节定理由此根据第五节定理4知道知道(I-BJ)是非奇异矩是非奇异矩阵阵，因此因此 A=D(I

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

8、1，从而，从而 (BG)1，故，故GaussSeidel迭代法迭代法收敛。收敛。令令 -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 方法同时收敛或同时发方法同时收敛或同时发散散,若为同时收敛若为同时收敛,则后者比前者收敛快。则后者比前者收敛快。数学学院 信息与计算科学系例例 3 已知方程组已知方程组判断雅可比迭代判断雅可比迭代法和高斯法和高斯塞德尔法的敛散性？塞德尔法的敛散性？解解 雅可比迭代矩阵雅可比迭代矩阵数学学院 信息与计算科学系故故Jacobi 迭代迭代法收敛。法收敛。再由定理再由定理5 的的 2)或由或由 A是对称是对称正定正定阵阵知知 GaussSeidel迭代法也收敛，且比迭代法也收敛，且比 Jacobi 迭代迭代法收敛得快。法收敛得快。