第六讲 线性方程组的定常迭代解法 1 常用定常迭代方法 2 应用：Poisson方程求解 3 收敛性分析 4 加速方法 5交替方向与HSS算法 现代数位分析（数值线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan
第六讲 线性方程组的定常迭代解法 1 常用定常迭代方法 2 应用：Poisson 方程求解 3 收敛性分析 4 加速方法 5 交替方向与 HSS 算法 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan
线性方程组的数值求解 直接法 PLU分解，LDLT分解，Cholesky分解等 迭代法 -经典（定常，不动点）迭代法：Jacobi,,Gauss--Seidel,SOR,SSOR, -现代(Krylov子空间)迭代法：CG,MINRES,GMRES,BiCGStab,,. 快速算法（基于特殊结构和性质） -基于各类快速变换，如FFT,DCT,DST等 -代数多重网格法(Algebraic multigrid -快速多极子算法(Fast multipole) Hierarchical Matrices
线性方程组的数值求解 • 直接法 PLU 分解, LDLT 分解, Cholesky 分解等 • 迭代法 经典 (定常, 不动点) 迭代法: Jacobi, GaussSeidel, SOR, SSOR, ... 现代 (Krylov 子空间) 迭代法: CG, MINRES, GMRES, BiCGStab, ... • 快速算法 (基于特殊结构和性质) 基于各类快速变换, 如 FFT, DCT, DST 等 代数多重网格法 (Algebraic multigrid) 快速多极子算法 (Fast multipole) Hierarchical Matrices
秦 注记 有些方法可能只是对某类方程有效，比如快速算法. 在实际应用中，这些方法经常结合使用，如混合算法，预处理算法等。 本讲主要介绍经典（定常，不动点）迭代方法 更多送代方法可参见：Templates for the Solution of Linear Systems:Building Blocks for Iterative Methods,SIAM,1994. http://math.ecnu.edu.cn/~jypan 3/86
有些方法可能只是对某类方程有效, 比如快速算法. 在实际应用中, 这些方法经常结合使用, 如混合算法, 预处理算法等. 注 记 本讲主要介绍经典 (定常, 不动点) 迭代方法 ✍ 更多迭代方法可参见: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, 1994. http://math.ecnu.edu.cn/~jypan 3/86
秦 1 常用定常迭代方法 1.1矩阵分裂迭代方法 1.2 Jacobi迭代 l.3 Gauss-Seidel迭代 1.4SOR迭代 1.5SSOR迭代方法 l.6 Richardson算法 1.7分块迭代方法 http://math.ecnu.edu.cn/~jypan 4/86
1 常用定常迭代方法 1.1 矩阵分裂迭代方法 1.2 Jacobi 迭代 1.3 GaussSeidel 迭代 1.4 SOR 迭代 1.5 SSOR 迭代方法 1.6 Richardson 算法 1.7 分块迭代方法 http://math.ecnu.edu.cn/~jypan 4/86
秦 为什么迭代法 当直接求解方程组Ax二b较困难时，我们可以求解一个近似方程组 Mx=b 其中M是A的某个近似，且该方程组较容易求解。 设其解为x1).易知它与真解之间的误差满足 A(z-x)=b-Ax四 如果x)已经满足精度要求，则停止计算，否则需要修正 http://math.ecnu.edu.cn/~jypan 5/86
为什么迭代法 当直接求解方程组 Ax = b 较困难时, 我们可以求解一个近似方程组 Mx = b 其中 M 是 A 的某个近似, 且该方程组较容易求解. 设其解为 x (1) . 易知它与真解之间的误差满足 A(x∗ − x (1)) = b − Ax(1) 如果 x (1) 已经满足精度要求, 则停止计算, 否则需要修正. http://math.ecnu.edu.cn/~jypan 5/86
秦 设修正量为△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