《线性代数方程组中的预处理共轭梯度法ppt课件.pptx》由会员分享，可在线阅读，更多相关《线性代数方程组中的预处理共轭梯度法ppt课件.pptx（12页珍藏版）》请在三一办公上搜索。
1、线性代数方程组迭代法预处理共轭梯度法,孟庆彬,November 13, 2022,1 引入,线性代数方程组的解法直接法：高斯消去法，分解法迭代法：古典迭代法：Jacobi，Gauss-Seidel，SOR，SSOR现代迭代法：（投影方法，子空间法）正交化的误差投影型Krylov：FOM，IOM，DIOM对称情形误差投影型Krylov：Lanczos，CG，PCG正交化的残量投影型Krylov：GMRES，GCR双正交化投影型Krylov方法：BiCG，CGS.,1 引入,共轭梯度法（1950S）对于固定的k，在 R n 空间中取k个线性无关的量 p 1 ,p 2 ,. ,p 使 满足：( )=
2、 min( ( 1 , 2 ,., 当k=n时， 一定是方程Ax=b的精确解，CG的出发点数值稳定性不好舍入误差必然存在条件数较大时收敛慢预处理共轭梯度法（1970S）预处理系数矩阵,cond()=| 1 |,2 知识回顾,CG算法 残差向量 搜索步长 搜索方向,3 算法原理,PCG算法矩阵A的对称正定的矩阵M相似于A原始残差 = 预处理残差 = 1 特殊情况，M为单位矩阵问题是预处理矩阵M应该如何选取呢？M是对称正定M与A具有相似性方程 Mz = 的特征值比较集中，即cond( ) 1或尽可能小,3 算法原理,PCG算法取M的LU分解 M=LL T L 1 AL u=L 1 x=L 1 u
3、= = = = 1 = 1 , )=( , 1 )=( 1 , 1 )=( , , )=( , )=( 1 , )=( , ,4 预处理方法,预处理方法取预优矩阵（预处理矩阵）为A的一个小带宽部分（如三对角或对角线部分） 矩阵分裂，尤其是线性稳定迭代中的矩阵A的分裂构造预处理矩阵通过A的各种近似分解得到预处理矩阵（如不完全分解）通过矩阵A的多项式构造预处理矩阵子结构，区域分裂，EBE预处理途径等等,4 预处理方法,预处理方法对角预处理法：若A是严格对角占优的矩阵，则可以选择 =( 11 , 22 ,., 为预处理矩阵；若A是分块对角阵，则可以选择 =( 11 , 22 ,., 为预处理矩阵但是
4、这样简单的选择，往往不能带来很好的加速收敛效果。,4 预处理方法,预处理方法分裂方法：将A分裂为：APQ；通过矩阵P，Q来构造预处理矩阵M，一般取线性稳定迭代法中相应分裂如：Jacobi分裂（Pdiag(A)）Gauss-Seidel分裂（ Pdiag(A) L，L是A的严格下三角）SSOR分裂：= ， 为严格下三角,4 预处理方法,预处理方法不完全分解预处理方法：主要有不完全LU分解、不完全Cholesky分解以及相应的块不完全分解等设 是A的一个近似分解 = +，L是下三角矩阵，R称为剩余矩阵，M= 为预处理矩阵。此方法与CG迭代方法相结合，就形成了不完全Cholesky分解预处理共轭梯度法(ICCG)，由于参数可以调整，以达到最好的收敛效果，所以它是目前人们使用最多的方法之一，而且从这个方法上改进出的方法也很多。,5 高效实现,PCG计算量主要工作量是 1 和向量的乘法，以及一次矩阵A和向量的乘法A和M是相似的第一种高效实现不完全分解M=A-R 1 = 1 (+)=+ 1 R中的非零元素远远少于A。R需要显式存储第二种高效实现分裂A是对称的= 0 E ，-E严格下三角，D0是对角线矩阵 M=() 1 ( E ，D不完全等于D0SSOR-PCG,谢 谢！,
