华东师范大学：《迭代方法与预处理》课程教学课件（迭代方法与预处理）第三讲 定常迭代法（主讲：潘建瑜）

线性方程组。迭代方法与预处理 第三讲定常迭代法 目录 3.1 定常迭代法 3.2 收敛性分析 3.3 正则分裂 3.4交替方向迭代法 3.5迭代法的加速 https://math.ecnu.edu.cn/-jypan/Teaching/MatrixIter

线性方程组 • 迭代方法与预处理 第三讲 定常迭代法 3.1 定常迭代法 3.2 收敛性分析 3.3 正则分裂 3.4 交替方向迭代法 3.5 迭代法的加速 目录 https://math.ecnu.edu.cn/~jypan/Teaching/MatrixIter

线性方程组的数值求解 ⊙直接法 -LU分解，Cholesky分解， )选代法 -定常（经典，基本）迭代法：Jacobi,Gauss--Seidel,.SOR,SSOR, -现代(Krylov子空间)迭代法：CG,MINRES,GMRES,. ⊙快速算法（基于特殊结构和性质） -基于各类快速变换，如FFT,DCT,DST, -代数多重网格法(Algebraic multigrid) -快速多极子算法(Fast multipole) Hierarchical Matrices,... http://math.ecmu.edu.cn/-jypan 2/109

线性方程组的数值求解  直接法 - LU 分解, Cholesky 分解, ...  迭代法 - 定常 (经典, 基本) 迭代法: Jacobi, Gauss-Seidel, SOR, SSOR, ... - 现代 (Krylov 子空间) 迭代法: CG, MINRES, GMRES, ...  快速算法 (基于特殊结构和性质) - 基于各类快速变换, 如 FFT, DCT, DST, ... - 代数多重网格法 (Algebraic multigrid) - 快速多极子算法 (Fast multipole) - Hierarchical Matrices, ... http://math.ecnu.edu.cn/~jypan 2/109

有些方法可能只是对某类方程有效，比如快速算法 在实际应用中，这些方法经常结合使用，如混合算法，预处理算法等 本讲主要介绍定常（经典，基本）迭代法 更多迭代方法可参见： Templates for the Solution of Linear Systems:Building Blocks for Iterative Methods,1994. http://math.ecmu.edu.cn/-jypan 3/109

!  有些方法可能只是对某类方程有效, 比如快速算法.  在实际应用中, 这些方法经常结合使用, 如混合算法, 预处理算法等. 本讲主要介绍定常 (经典, 基本) 迭代法 更多迭代方法可参见: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 1994. http://math.ecnu.edu.cn/~jypan 3/109

3-11 定常迭代法 3.1定常迭代法 3.1.1矩阵分裂与选代法 3.1.2经典迭代法(Jacobi,G-S,SOR,SSOR,AOR) 3.1.3 Richardson迭代法 3.1.4分块迭代法 https://math.ecnu.edu.cn/-jypan/Teaching/MatrixIter

3­1 定常迭代法 3.1 定常迭代法 3.1.1 矩阵分裂与迭代法 3.1.2 经典迭代法 (Jacobi, G-S, SOR, SSOR, AOR) 3.1.3 Richardson 迭代法 3.1.4 分块迭代法 https://math.ecnu.edu.cn/~jypan/Teaching/MatrixIter

什么是迭代法 当直接求解方程组Ax=b较困难时，我们可以求解一个近似方程组 Mx=b 其中M是A的某个近似，且该方程组较容易求解. 设其解为x).易知它与真解之间的误差满足 A(-x四)=b-Ax四 如果x1)已经满足精度要求，则停止计算，否则需要通过修正来满足精度要求. http://math.ecma.edu.cn/-jypan 5/109:

什么是迭代法 当直接求解方程组 Ax = b 较困难时, 我们可以求解一个近似方程组 Mx = b 其中 M 是 A 的某个近似, 且该方程组较容易求解. 设其解为 x (1) . 易知它与真解之间的误差满足 A(x∗ − x (1)) = b − Ax(1) 如果 x (1) 已经满足精度要求, 则停止计算, 否则需要通过修正来满足精度要求. http://math.ecnu.edu.cn/~jypan 5/109

怎么修正近似解 设修正量为△x.显然最佳的修正量△x应该满足方程A△x=b-Ax) 但由于直接求解该方程比较困难，因此我们还是求解近似方程组 M△x=b-Ax1) 于是得到修正后的近似解 x2)=)+△x=x)+M1(b-Ax) 若②)已经满足精度要求，则停止计算，否则继续按以上的方式进行修正， http://math.ecnu.edu.cn/-jypan 6/109

怎么修正近似解 设修正量为 ∆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/109

定常迭代法 不断重复以上步骤，于是，我们就得到一个序列 x1,②，.，因， 满足以下递推关系 xk+1)=x因+M1(b-A) k=1,2, 由于每次迭代的格式是一样的，因此称为定常迭代法 http://math.ecmu.edu.cn/-jypan 7/109

定常迭代法 不断重复以上步骤, 于是, 我们就得到一个序列 x (1) , x (2) , . . . , , x (k) , . . . . 满足以下递推关系 x (k+1) = x (k) + M−1 (b − Ax(k) ) , k = 1, 2, . . . . 由于每次迭代的格式是一样的, 因此称为 定常迭代法 . http://math.ecnu.edu.cn/~jypan 7/109

构造定常迭代法的基本准则 构造一个好的定常迭代法通常需要考虑以下两点： (1)以M为系数矩阵的线性方程组必须比原线性方程组更容易求解： (2)M应该是A的一个很好的近似，或者迭代序列{}要收敛（越快越好）. http://math.ecnu.edu.cn/-jypan 8/109

构造定常迭代法的基本准则 构造一个好的定常迭代法通常需要考虑以下两点: (1) 以 M 为系数矩阵的线性方程组必须比原线性方程组更容易求解; (2) M 应该是 A 的一个很好的近似, 或者迭代序列 {x (k)} 要收敛 (越快越好). http://math.ecnu.edu.cn/~jypan 8/109

本讲主要介绍以下定常迭代法（基于矩阵分裂）： Jacobi,Gauss-Seidel,SOR(Successive Over-Relaxation) SSOR (Symmetric SOR),AOR (Accelerated over-relaxation),SAOR ⑦ Richardson算法 。分块迭代算法 ⊙交替方向算法 http://math.ecmu.edu.cn/-jypan 9/109

本讲主要介绍以下定常迭代法 (基于 矩阵分裂):  Jacobi, Gauss-Seidel, SOR (Successive Over-Relaxation) SSOR (Symmetric SOR), AOR (Accelerated over-relaxation), SAOR  Richardson 算法  分块迭代算法  交替方向算法 http://math.ecnu.edu.cn/~jypan 9/109

迭代法基本思想 给定一个迭代初始值O,通过一定的迭代格式生成一个迭代序列 x1),2),3),.,因， 使得 limx因=x*eA-lb http://math.ecmu.edu.cn/-jypan 10/109

迭代法基本思想 给定一个迭代初始值 x (0) , 通过一定的迭代格式生成一个迭代序列 x (1) , x (2) , x (3) , . . . , x (k) , . . . 使得 lim k→∞ x (k) = x∗ ≜ A −1 b http://math.ecnu.edu.cn/~jypan 10/109