华东师范大学:《迭代方法与预处理》课程教学课件(迭代方法与预处理)第五讲 预处理方法

线性方程组。迭代方法与预处理 第五讲 预处理方法 目录 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 differential 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
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 华东师范大学:《迭代方法与预处理》课程教学课件(迭代方法与预处理)第四讲 Krylov子空间方法.pdf
- 华东师范大学:《迭代方法与预处理》课程教学课件(迭代方法与预处理)第三讲 定常迭代法(主讲:潘建瑜).pdf
- 华东师范大学:《迭代方法与预处理》课程教学课件(迭代方法与预处理)第二讲 非负矩阵与M-矩阵.pdf
- 华东师范大学:《迭代方法与预处理》课程教学课件(迭代方法与预处理)第一讲 线性代数基础(矩阵基础).pdf
- 大连大学:数学与应用数学(金融数学)专业课程教学大纲汇编(2010).doc
- 大连大学:数学与应用数学(师范类)专业课程教学大纲汇编(2010).doc
- 《数值分析》课程教学资源(课外阅读)数值计算指南, Sun Microsystems, Inc., 2005.pdf
- 《数值分析》课程教学资源(课外阅读)Lloyd N. Trefethen, Predictions for scientific computing 50 years from now, Mathematics Today, 2000.pdf
- 《数值分析》课程教学资源(课外阅读)Lloyd N. Trefethen, The Definition of Numerical Analysis, SIAM News, Nov 1992.pdf
- 《数值分析》课程教学资源(课外阅读)G. H. Golub, History of Numerical Linear Algebra, a Personal View, 2007.pdf
- 《数值分析》课程教学资源(课外阅读)Professor SVD(Moler, 2006).pdf
- 《数值分析》课程教学资源(参考资料)Singular Values and Singular Value Inequalities(Mathias, Handbook of LA, 2014).pdf
- 华东师范大学:《数值分析》课程教学资源(课件讲义)第三讲 线性最小二乘问题——线性最小二乘问题的求解方法.pdf
- 华东师范大学:《数值分析》课程教学资源(课件讲义)第三讲 线性最小二乘问题——奇异值分解(SVD).pdf
- 华东师范大学:《数值分析》课程教学资源(课件讲义)第三讲 线性最小二乘问题——QR分解.pdf
- 华东师范大学:《数值分析》课程教学资源(课件讲义)第三讲 线性最小二乘问题——问题介绍与 Householder、Givens变换.pdf
- 华东师范大学:《数值分析》课程教学资源(课件讲义)第二讲 线性方程组直接解法——扰动分析与解的改进.pdf
- 《数值分析》课程教学资源(参考资料)Matrix factorizations and direct solution of linear systems(Beattie, Handbook of LA, 2014).pdf
- 《数值分析》课程教学资源(参考资料)Gaussian Elimination(Higham, 2011).pdf
- 华东师范大学:《数值分析》课程教学资源(课件讲义)第二讲 线性方程组直接解法——Gauss消去法与矩阵分解法.pdf
- 华东师范大学:《矩阵计算》课程教学资源(讲义)矩阵计算课堂讲义 Matrix Computations(主讲:潘建瑜).pdf
- 《矩阵计算》课程教学资源(文献资料)The decompositional approach to matrix computation(Stewart, 2000).pdf
- 《矩阵计算》课程教学资源(文献资料)G. H. Golub, History of Numerical Linear Algebra, a Personal View, 2007.pdf
- 《矩阵计算》课程教学资源(文献资料)Lloyd N. Trefethen, The Definition of Numerical Analysis, SIAM News, Nov 1992.pdf
- 《矩阵计算》课程教学资源(文献资料)Lloyd N. Trefethen, Predictions for scientific computing 50 years from now, Mathematics Today, 2000.pdf
- 上海交通大学:数学科学学院公共基础课《大学医科数学》课程教学大纲(A类,1).pdf
- 上海交通大学:数学科学学院公共基础课《大学医科数学》课程教学大纲(A类,2).pdf
- 上海交通大学:数学科学学院公共基础课《微积分基础》课程教学大纲.pdf
- 上海交通大学:数学科学学院公共基础课《数理方法》课程教学大纲.pdf
- 上海交通大学:数学科学学院公共基础课《概率统计》课程教学大纲.pdf
- 上海交通大学:数学科学学院公共基础课《线性代数》课程教学大纲.pdf
- 上海交通大学:数学科学学院公共基础课《计算方法》课程教学大纲.pdf
- 上海交通大学:数学科学学院公共基础课《高等数学I》课程教学大纲.pdf
- 上海交通大学:数学科学学院公共基础课《高等数学II》课程教学大纲.pdf
- 上海交通大学:数学科学学院专业基础课《数值分析与程序设计》课程教学大纲.pdf
- 上海交通大学:数学科学学院专业基础课《高等代数》课程教学大纲(I).pdf
- 上海交通大学:数学科学学院专业基础课《高等代数》课程教学大纲(II).pdf
- 上海交通大学:数学科学学院专业基础课《高等代数》课程教学大纲(荣誉)I.pdf
- 上海交通大学:数学科学学院专业基础课《数学分析》课程教学大纲(I).pdf
- 上海交通大学:数学科学学院专业基础课《数学分析》课程教学大纲(II).pdf