5-1 预处理Krylov子空间方法 5.1预处理Krylov子空间方法 5.1.1预处理CG方法 5.1.2预处理GMRES方法 5.1.3左、右预处理方式的最优性质 5.1.4 Flexible GMRES方法 5.1.5带预处理的BiCGSTAB方法 https://math.ecnu.edu.cn/-jypan/Teaching/MatrixIter
51 预处理 Krylov 子空间方法 5.1 预处理 Krylov 子空间方法 5.1.1 预处理 CG 方法 5.1.2 预处理 GMRES 方法 5.1.3 左、右预处理方式的最优性质 5.1.4 Flexible GMRES 方法 5.1.5 带预处理的 BiCGSTAB 方法 https://math.ecnu.edu.cn/~jypan/Teaching/MatrixIter
线性方程组的预处理 考虑线性方程组 Ax=b A∈Rnxn非奇异，b∈Rn 在方程组的两边同时左乘一个非奇异矩阵P∈Rx”的逆，则可得 P-1Az=P-1b (5.1) ·这个新方程组就是预处理后的方程组 ·P就称为预处理子(preconditioner)】 ·这个过程就是对原线性方程组做预处理 ·当Krylov子空间方法被用于求解（⑤.1）时，就称为预处理Krylov子空间方法 http://aath.ecnu.edu.cn/-jypan 12/72
线性方程组的预处理 考虑线性方程组 Ax = b , A ∈ R n×n 非奇异, b ∈ R n . 在方程组的两边同时左乘一个非奇异矩阵 P ∈ R n×n 的逆, 则可得 P −1Ax = P −1 b (5.1) ▶ 这个新方程组就是 预处理后的方程组 ▶ P 就称为 预处理子 (preconditioner ) ▶ 这个过程就是对原线性方程组 做预处理 ▶ 当 Krylov 子空间方法被用于求解 (5.1) 时, 就称为 预处理 Krylov 子空间方法 http://math.ecnu.edu.cn/~jypan 12/72
预处理子怎么选取 预处理子选取基本准则 一个好的预处理子P通常需满足下面两个要求： (1)P1A具有更小的条件数和（或）更好的特征值分布； (2)线性方程组Pz=r容易求解，即预处理子P的使用成本低廉， ·第一条是为了确保预处理后的线性方程组更容易求解，即预处理子有效 ·第二条是因为在用Krylov子空间方法求解预处理后的方程组时，每步迭代都 需要额外求解一个以P为系数矩阵的线性方程组，为了不增加太多额外的运算 成本，必须很容易求解 囊http:/aath.ecan.odu.c/jp 13/72
预处理子怎么选取 预处理子选取基本准则 一个好的预处理子 P 通常需满足下面两个要求: (1) P −1A 具有更小的条件数和 (或) 更好的特征值分布; (2) 线性方程组 Pz = r 容易求解, 即预处理子 P 的使用成本低廉. ▶ 第一条是为了确保预处理后的线性方程组更容易求解, 即预处理子有效 ▶ 第二条是因为在用 Krylov 子空间方法求解预处理后的方程组时, 每步迭代都 需要额外求解一个以 P 为系数矩阵的线性方程组, 为了不增加太多额外的运算 成本, 必须很容易求解. http://math.ecnu.edu.cn/~jypan 13/72
预处理方式 ⊙左预处理 P-1Ax=P-1b ⊙右预处理 AP-lu=b, t=P-lu 。两边预处理：同时进行左预处理和右预处理 L-1AR-1u=L-16, x=R-lu 对应的预处理子为P=LR http://aath.ecnu.edu.cn/-jypan 14/72
预处理方式 左预处理 P −1Ax = P −1 b 右预处理 AP−1 u = b, x = P −1 u 两边预处理: 同时进行左预处理和右预处理 L −1AR−1 u = L −1 b, x = R −1 u 对应的预处理子为 P = LR http://math.ecnu.edu.cn/~jypan 14/72
三种预处理方式的选择 三种预处理方式的迭代矩阵 P-1A,AP-1,L-1AR-1 图具有相同的特征值分布 ·若A和P都对称正定，则三种方式的PCG效果基本一样 ·若A非对称（非正规）情形，则预处理方式对Krylov子空间方法有不同影响 注记 在实际使用中，该选取哪种预处理方式，需要根据问题本身和所用的方法来确定 比如GMRES方法，建议右预处理（右预处理极小化的是原始残量的范数）： http://math.ecmu.edu.cn/-jypan 15/72
三种预处理方式的选择 三种预处理方式的迭代矩阵 P −1A, AP−1 , L −1AR−1 具有相同的特征值分布 ▶ 若 A 和 P 都对称正定, 则三种方式的 PCG 效果基本一样 ▶ 若 A 非对称 (非正规) 情形, 则预处理方式对 Krylov 子空间方法有不同影响 注记 在实际使用中, 该选取哪种预处理方式, 需要根据问题本身和所用的方法来确定. 比如 GMRES 方法, 建议右预处理 (右预处理极小化的是原始残量的范数). http://math.ecnu.edu.cn/~jypan 15/72