3e基本的矩阵迭代法ppt课件.ppt

1,第三章线性方程组的迭代解法,计算方法, 基本的矩阵分裂迭代法,2,本讲内容,Jacobi 迭代算法 Gauss-Seidel 迭代算法 SOR 迭代算法 收敛性分析,矩阵分裂迭代法的典型代表,3,Jacobi 迭代,考虑线性方程组,Ax = b,其中 A=(aij)nn 非奇异，且对角线元素全不为 0。,将 A 分裂成 A = D - L- U， 其中,4,Jacobi 迭代,k = 0, 1, 2, ,令 M = D，N = L + U，可得 雅可比 (Jacobi) 迭代方法,Jacobi 迭代,迭代矩阵记为：,5,6,Gauss-Seidel 迭代,在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。,7,Gauss-Seidel 迭代,写成矩阵形式:,此迭代方法称为 高斯-塞德尔 (Gauss-Seidel) 迭代法,k = 0, 1, 2, ,可得,迭代矩阵记为：,8,SOR 迭代,为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子，于是可得迭代格式,在 G-S 迭代中,9,SOR 迭代,写成矩阵形式:,可得, SOR (Successive Over-Relaxation) 迭代方法,迭代矩阵记为：,SOR 的优点：通过选取合适的 ，可获得更快的收敛速度 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.1350, -1.0257 )T,x(7) = ( 2.0000, 3.0000, -1.0000 )T,如何确定 SOR 迭代中的最优松弛因子是一件很困难的事,14,15,收敛性分析,定理：对任意初始向量 x(0)，上述迭代格式收敛的充要条件是,16,Jacobi 迭代收敛的充要条件 (J)1 G-S 迭代收敛的充要条件 (G)1 SOR 迭代收敛的充要条件 (L)1,收敛性,收敛性定理,Jacobi 迭代收敛的充分条件 |J| 1 G-S 迭代收敛的充分条件 |G| 1 SOR 迭代收敛的充分条件 |L| 1,谱半径,17,18,收敛性分析,B = M-1N,定理：若存在算子范数 | |，使得 |B| = q 1，则,证明：P112,迭代法收敛,19,系数矩阵法-对角占优矩阵,且至少有一个不等式严格成立，则称 A 为 弱对角占优；若所有不等式都严格成立，则称 A 为 严格对角占优。,( i = 1, 2, . , n ),定义：设 ARnn，若,20,Jacobi、G-S 收敛性,引理3-2：若 A 严格对角占优，则 A 非奇异,21,SOR 收敛性,定理：若 SOR 迭代收敛，则 0 2。,SOR 收敛的必要条件,22,举例,例：设 ，给出 Jacobi 和 G-S 收敛的充要条件,23,举例,解法二：,Jacobi 的迭代矩阵为,设 是 J 的特征值，则由 det(I - J) = 0 可得,( - a)2 ( +2a) = 0,Jacobi 收敛的充要条件是 (J)1 |1，即 -0.5a0.5,24,作业,1. 教材 页，习题 2. 教材 页，习题,