华东师范大学：《迭代方法与预处理》课程教学课件（迭代方法与预处理）第五讲 预处理方法

线性方程组。迭代方法与预处理 第五讲 预处理方法 目录 5.1 预处理Krylov子空间方法 5.2 基于矩阵分裂的预处理子 5.3 不完全分解预处理子 M 5.4 稀疏近似逆预处理子 米 其他预处理技术 https://math.ecnu.edu.cn/-jypan/Teaching/MatrixIter

线性方程组 • 迭代方法与预处理 第五讲 预处理方法 5.1 预处理 Krylov 子空间方法 5.2 基于矩阵分裂的预处理子 5.3 不完全分解预处理子 5.4 稀疏近似逆预处理子 * 其他预处理技术 目录 https://math.ecnu.edu.cn/~jypan/Teaching/MatrixIter

Nothing will be more central to computational science in the next century than the art of transforming a problem that appears intractable into another whose solution can be approximated rapidly.For Krylov subspace matrix iterations, this is preconditioning. -Trefethen Bau,1997. Lloyd N.Trefethen Professor of University of Oxford,Head of Oxford's Numerical Analysis Group First customer to buy MATLAB Royal Society(英国至家学会)，National Academy of Engineering(关国国家工程院)， Academia Europaea(欧洲人文与自然科乎院) Fellow of SIAM and AMS.President of SIAM IMA Gold Medal.LMS Naylor Prize.SIAM Polya Prize 包 SIAM John von Neumann Prize Invited speaker at ICIAM,ICM,and ECM congresses Author of SIAM's all-time bestseller Winner of teaching prizes at MIT.Cornell and Oxford Winner of the first Fox Prize in Numerical Analysis Inventor of Chebfun L.N.Trefethen and D.Bau,III,Numerical Linear Algebra,1997. http://aath.ecnu.edu.cn/-jypan 2/72

Nothing will be more central to computational science in the next century than the art of transforming a problem that appears intractable into another whose solution can be approximated rapidly. For Krylov subspace matrix iterations, this is preconditioning. — Trefethen & Bau, 1997. Lloyd N. Trefethen Professor of University of Oxford, Head of Oxford’s Numerical Analysis Group  First customer to buy MATLAB  Royal Society (英国皇家学会), National Academy of Engineering (美国国家工程院), Academia Europaea (欧洲人文与自然科学院)  Fellow of SIAM and AMS, President of SIAM  IMA Gold Medal, LMS Naylor Prize, SIAM Pólya Prize  SIAM John von Neumann Prize  Invited speaker at ICIAM, ICM, and ECM congresses  Author of SIAM’s all-time bestseller  Winner of teaching prizes at MIT, Cornell and Oxford  Winner of the first Fox Prize in Numerical Analysis  Inventor of Chebfun  L.N. Trefethen and D. Bau, III, Numerical Linear Algebra, 1997. http://math.ecnu.edu.cn/~jypan 2/72

为什么要预处理 工程中出现的大规模线性方程组往往是病态的，对数值求解带来很大的困难： ·使得迭代法（比如Krylov子空间迭代法）收敛变得非常缓慢 ·对数值解的精度产生很大的影响（在有限精度计算情形下） 对于第一个问题，当前的有效处理方法是预处理，预处理是当前公认的能有效 改善迭代法（特别是Krylov子空间迭代法）收敛性质的有效手段 http://math.ecnu.edu.cn/-jypan 3/72

为什么要预处理 工程中出现的大规模线性方程组往往是病态的, 对数值求解带来很大的困难: ▶ 使得迭代法 (比如 Krylov 子空间迭代法) 收敛变得非常缓慢 ▶ 对数值解的精度产生很大的影响 (在有限精度计算情形下) 对于第一个问题, 当前的有效处理方法是 预处理, 预处理是当前公认的能有效 改善迭代法 (特别是 Krylov 子空间迭代法) 收敛性质的有效手段. http://math.ecnu.edu.cn/~jypan 3/72

什么是预处理 通俗地说，预处理就是将难以求解的问题转化成等价的容易求解的新问题 ⊙对于线性方程组而言，预处理就是对（病态）系数矩阵进行适当的线性变换， 转换为一个（良态）新矩阵，从而达到改善迭代法收敛性的目的 0 预处理方法的研究是当前科学计算领域中的重要研究课题和热门课题， http://sath.ecnu.edu.cn/-jypan 4/72

什么是预处理 通俗地说, 预处理就是将难以求解的问题转化成等价的容易求解的新问题  对于线性方程组而言, 预处理就是对 (病态) 系数矩阵进行适当的线性变换, 转换为一个 (良态) 新矩阵, 从而达到改善迭代法收敛性的目的.  预处理方法的研究是当前科学计算领域中的重要研究课题和热门课题. http://math.ecnu.edu.cn/~jypan 4/72

预处理举例：二维Poisson方程 2u 82u -△u(x,)=- =x), 4(x,=0, (x,)∈02， 2≌0,1×[0,1： ⊙用五点差分离散，得代数方程组 10 (I8T+T⑧)u=h2f 30 其中T=tridiag(-1,2,-1) 40 50 60 10 20 3040 50 60 z=288 http://math.ecnu.edu.cn/-jypan 5/72

预处理举例: 二维 Poisson 方程 − ∆u(x, y) = − ( ∂ 2u ∂x 2 + ∂ 2u ∂y 2 ) = f(x, y), u(x, y) = 0, (x, y) ∈ ∂Ω, Ω ≜ [0, 1] × [0, 1].  用五点差分离散, 得代数方程组 (I ⊗ T + T ⊗ I)u = h 2 f , 其中 T = tridiag(−1, 2, −1). 0 10 20 30 40 50 60 nz = 288 0 10 20 30 40 50 60 http://math.ecnu.edu.cn/~jypan 5/72

)不同预处理效果 P=(D-L)D-1(D-L) P2=TriDiag(A) P3 ichol(A) P4 michol(A) n 82 162 322 642 (A) 32.2 166 441 1712 K(PA) 4.89 15.5 56.3 216 K(P2A) 16.6 58.7 221 856 K(P3A) 3.69 11.1 39.8 152 K(PA) 3.00 6.65 16.5 43.5 http://aath.ecnu.edu.cn/-jypan 6/72

 不同预处理效果 P1 = (D − L)D −1 (D − L ⊺ ) P2 = TriDiag(A) P3 = ichol(A) P4 = michol(A) n 8 2 162 322 642 κ(A) 32.2 166 441 1712 κ(P −1 1 A) 4.89 15.5 56.3 216 κ(P −1 2 A) 16.6 58.7 221 856 κ(P −1 3 A) 3.69 11.1 39.8 152 κ(P −1 4 A) 3.00 6.65 16.5 43.5 http://math.ecnu.edu.cn/~jypan 6/72

PCG convergence history 100 105 2装5393oc00909e0909903e0ee3030e0ne9e09e60406e为 10-10 CG SGS 1015 -TriDiag ichol -michol 10-20 10 20 30 40 50 60 70 80 90 100 Performance of different preconditioners for 2D Poisson with n=642 http:/aath.ecn.edu.cm/jp 7/72

10 20 30 40 50 60 70 80 90 100 10-20 10-15 10-10 10-5 100 PCG convergence history CG SGS TriDiag ichol michol Performance of different preconditioners for 2D Poisson with n = 642 http://math.ecnu.edu.cn/~jypan 7/72

预处理举例：分数阶扩散方程 「-D[(oD-8-(1-)D）国=国， x∈0,1，K(a=1+8x,3=0.5,0=0.5 Convergence history for N=4096 Condition number 10 一GMRES n cond(A) 28 5191 10 29 14813 210 42143 211 119653 102 212 339259 213 961081 10 0 200 400 00 80 1000 http://aath.ecnu.edu.cn/-jypan 8/72

预处理举例: 分数阶扩散方程    − D [ K(x) ( θ 0 D 1−β x −(1 − θ) x D 1−β 1 ) u(x) ] = f(x), x ∈ [0, 1], K(x) = 1 + 8x, β = 0.5, θ = 0.5. Condition number n cond(A) 2 8 5191 2 9 14813 2 10 42143 2 11 119653 2 12 339259 2 13 961081 Convergence history for N = 4096 http://math.ecnu.edu.cn/~jypan 8/72

简单循环预处理子 Convergence history after preconditioning Condition number 10° -Preconditioned GMRES cond(A) cond(P-1A) 102 28 10 5191 76 108 29 14813 112 210 109 42143 162 100 21 119653 235 102 212 339259 337 104 213 961081 482 106 0-00900 10 20 3040 506070 80 http://math.ecnu.edu.cn/-jypan 9/72

简单循环预处理子 Condition number n cond(A) cond(P −1A) 2 8 5191 76 2 9 14813 112 2 10 42143 162 2 11 119653 235 2 12 339259 337 2 13 961081 482 Convergence history after preconditioning http://math.ecnu.edu.cn/~jypan 9/72

关于预处理方法的相关参考资料 Saad,Iterative Methods for Sparse Linear Systems,2nd edition,2003. Chen,Matrir Preconditioning Techniques and Applications,2005. Malek and Z.Strakos,Preconditioning and the Conjugate Gradient Method in The Contert of Solving PDEs,2015. Bertaccini and Durastante,Iterative Methods and Preconditioning for Large and Sparse Linear Systems With Applications,2018. 0谷同祥等，迭代方法和预处理技术（下），科学出版社，2015. Benzi,Preconditioning techniques for large linear systems:A survey,JCP,2002, 418-477. Mardal and Winther,Preconditioning discretizations of systems of partial differ- ential equations,NLAA,2011,1-40. Wathen,Preconditioning,Acta Numerica,2015,329-376 DPearson and Pestana,Preconditioners for Krylov subspace methods:An overview, GAMM,2020. http://aath.ecnu.edu.cn/-jypan 10/72

关于预处理方法的相关参考资料  Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, 2003.  Chen, Matrix Preconditioning Techniques and Applications, 2005.  Málek and Z. Strakoˇs, Preconditioning and the Conjugate Gradient Method in The Context of Solving PDEs, 2015.  Bertaccini and Durastante, Iterative Methods and Preconditioning for Large and Sparse Linear Systems With Applications, 2018.  谷同祥等, 迭代方法和预处理技术 (下), 科学出版社, 2015. ▷ Benzi, Preconditioning techniques for large linear systems: A survey, JCP, 2002, 418–477. ▷ Mardal and Winther, Preconditioning discretizations of systems of partial differ￾ential equations, NLAA, 2011, 1–40. ▷ Wathen, Preconditioning, Acta Numerica, 2015, 329–376. ▷ Pearson and Pestana, Preconditioners for Krylov subspace methods: An overview, GAMM, 2020. http://math.ecnu.edu.cn/~jypan 10/72