《9月24ch0８线性方程组的迭代法》由会员分享，可在线阅读，更多相关《9月24ch0８线性方程组的迭代法（20页珍藏版）》请在金锄头文库上搜索。
1、1,第8章,线性方程组的迭代法, Jacobi, G-S and SOR,2,内容提要,迭代算法基本概念 Jacobi 迭代法和 GaussSeidel 迭代法 SOR（超松弛）迭代法,3,本讲内容,Jacobi 迭代法 GaussSeidel 迭代法 SOR（超松弛）迭代法 迭代法收敛性分析,几个基本的迭代法,4,Jacobi 迭代,考虑线性方程组,Ax = b,其中 A=(aij)nn 非奇异，且对角线元素全不为 0,将 A 分裂成 A = D - L- U， 其中,Jacobi 迭代法,5,Jacobi 迭代,k = 0, 1, 2, ,令 M = D，N = L + U，可得 雅可比
2、(Jacobi) 迭代方法,迭代矩阵记为：,Jacobi 迭代法,6,Gauss-Seidel 迭代,在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。,7,Gauss-Seidel 迭代,写成矩阵形式:,此迭代方法称为 高斯-塞德尔 (Gauss-Seidel) 迭代法,k = 0, 1, 2, ,可得,迭代矩阵记为：,8,SOR 迭代,为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子，于是可得迭代格式,G-S 迭代法的分量形式,9,SOR 迭代,写成矩阵形式:,可得, SOR (Successive Over-Relaxation) 迭代方法,迭代矩阵记为：,SOR 的优点：通
3、过选取合适的 ，可获得更快的收敛速度 SOR 的缺点：最优参数 的选取比较困难,10,Jacobi、G-S、SOR,Jacobi 迭代,SOR 迭代,G-S 迭代,11,举例,例：分别用 Jacobi、G-S、SOR 迭代解线性方程组,取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留 4 位。,12,举例,G-S 迭代：,x(1) = ( 0.5000, 2.8333, -1.0833 )T,x(9) = ( 2.0000, 3.0000, -1.0000 )T,迭代可得：,13,举例,SOR 迭代：,取 = 1.1，迭代可得,x(1) = ( 0.5500, 3.13
4、50, -1.0257 )T,x(7) = ( 2.0000, 3.0000, -1.0000 )T,如何确定 SOR 迭代中的最优松弛因子是一件很困难的事,14,Jacobi 迭代收敛的充要条件 (J)1 G-S 迭代收敛的充要条件 (G)1 SOR 迭代收敛的充要条件 (L)1,收敛性,Jacobi 迭代收敛的充分条件 |J| 1 G-S 迭代收敛的充分条件 |G| 1 SOR 迭代收敛的充分条件 |L| 1,收敛性分析,15,对角占优矩阵,且至少有一个不等式严格成立，则称 A 为 弱对角占优； 若所有不等式都严格成立，则称 A 为 严格对角占优。,( i = 1, 2, . , n ),
5、定义：设 ARnn，若,对角占优矩阵,16,可约与不可约,定义：设 ARnn，若存在排列矩阵 P 使得,则称 A 为 可约矩阵；否则称为 不可约矩阵 。,不可约矩阵,17,Jacobi、G-S 收敛性,定理：若 A 严格对角占优或不可约弱对角占优，则 A 非奇异,定理：设 A 对称且 D 正定，则 Jacobi 迭代收敛的充要条件是 A 和 2D-A 都正定。,Jacobi 和 G-S 迭代法的收敛性,定理：设 A 对称且 D 正定，则 G-S 迭代收敛的充要条件是 A 正定。,18,SOR 收敛性,定理：若 SOR 迭代收敛，则 0 2。,SOR 收敛的必要条件,定理：若 A 对称正定，且 0 2，则 SOR 迭代收敛。,SOR 收敛的充分条件,定理：若 A 严格对角占优或不可约弱对角占优，且 0 1，则 SOR 迭代收敛。,19,举例,例：设 ，给出 Jacobi 和 G-S 收敛的充要条件,20,举例,解法二：,Jacobi 的迭代矩阵为,设 是 J 的特征值，则由 det(I - J) = 0 可得,( - a)2 ( +2a) = 0,Jacobi 收敛的充要条件是 (J)1 |1， 即 -0.5a0.5,G-S 迭代收敛的充要条件 (G)1,
