线性方程组。迭代方法与预处理 第五讲 预处理方法 目录 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