秦 设修正量为△x.显然△x满足方程A△x=b一Ax1).但由于直接求解该方程 比较困难，因此我们还是求解近似 M△x=b-Ax(). 于是得到修正后的近似解 x(②=x(0)+△x=x四+M-1(b-Ax) 若x②)已经满足精度要求，则停止计算，否则继续按以上的方式进行修正。 http://math.ecnu.edu.cn/~jypan 6/86
设修正量为 ∆x. 显然 ∆x 满足方程 A∆x = b − Ax(1) . 但由于直接求解该方程 比较困难, 因此我们还是求解近似 M∆x = b − Ax(1) . 于是得到修正后的近似解 x (2) = x (1) + ∆x = x (1) + M−1 (b − Ax(1)) 若 x (2) 已经满足精度要求, 则停止计算, 否则继续按以上的方式进行修正. http://math.ecnu.edu.cn/~jypan 6/86
不断重复以上步骤，于是，我们就得到一个序列 秦 x0,x2）,,x 满足以下递推关系 xk+)=x因+M-1(b-A) k=1,2,… 由于每次迭代的格式是一样的，因此称为定常迭代 通常，构造一个好的定常迭代，需要考虑以下两点： (1)以M为系数矩阵的线性方程组必须要比原线性方程组更容易求解； (2)M应该是A的一个很好的近似，或者迭代序列{xk}要收敛 http://math.ecnu.edu.cn/~jypan 7/86
不断重复以上步骤, 于是, 我们就得到一个序列 x (1), x(2), . . . , , x(k) , . . . . 满足以下递推关系 x (k+1) = x (k) + M−1 (b − Ax(k) ) , k = 1, 2, . . . . 由于每次迭代的格式是一样的, 因此称为 定常迭代 . 通常, 构造一个好的定常迭代, 需要考虑以下两点: (1) 以 M 为系数矩阵的线性方程组必须要比原线性方程组更容易求解; (2) M 应该是 A 的一个很好的近似, 或者迭代序列 {xk} 要收敛. http://math.ecnu.edu.cn/~jypan 7/86
秦 本小节我们介绍几个常见的基于矩阵分裂的定常迭代方法： ·Jacobi算法 ·Gauss-Seidel算法 ·SOR(Successive Over--Relaxation)算法 ·SSOR(Symmetric SOR)算法 http://math.ecnu.edu.cn/~jypan 8/86
本小节我们介绍几个常见的基于矩阵分裂的定常迭代方法: • Jacobi 算法 • GaussSeidel 算法 • SOR (Successive OverRelaxation) 算法 • SSOR (Symmetric SOR) 算法 http://math.ecnu.edu.cn/~jypan 8/86
秦 1.1 矩阵分裂迭代方法 迭代方法的基本思想 给定一个迭代初始值x©)，通过一定的迭代格式生成一个迭代序列 x1),x②)，x3),.,x 使得 limx=x*会A-1b +00 http://math.ecnu.edu.cn/~jypan 9/86
1.1 矩阵分裂迭代方法 迭代方法的基本思想 给定一个迭代初始值 x (0) , 通过一定的迭代格式生成一个迭代序列 x (1), x(2), x(3), . . . , x(k) , . . . 使得 lim k→∞ x (k) = x∗ ≜ A −1 b http://math.ecnu.edu.cn/~jypan 9/86
秦 定义（矩阵分裂Matrix splitting) 设A∈Rnxn非奇异，称 A=M-N (6.1) 为A的一个矩阵分裂，其中M非奇异 原方程组等价于Mx=Nx+b.于是我们就可以构造迭代格式 2(k+1)=M-1Nz(k)+M-1bGz(k)+g k=0,1, (6.2) 其中G=M一1N称为该迭代格式的迭代矩阵 http://math.ecnu.edu.cn/~jypan 10/86
定义 (矩阵分裂 Matrix splitting) 设 A ∈ R n×n 非奇异, 称 A = M − N (6.1) 为 A 的一个矩阵分裂, 其中 M 非奇异. 原方程组等价于 Mx = Nx + b. 于是我们就可以构造迭代格式 x (k+1) = M−1Nx(k) + M−1 b ≜ Gx(k) + g , k = 0, 1, . . . , (6.2) 其中 G = M−1N 称为该迭代格式的迭代矩阵. http://math.ecnu.edu.cn/~jypan 10/86