第六讲 线性方程组的定常迭代解法 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