线性方程组求解——预处理Preconditioning介绍

为什么需要预处理？

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

什么是预处理

通俗地说, 预处理就是将难以求解的问题转化成等价的容易求解的新问题
对于线性方程组而言, 预处理就是对(病态) 系数矩阵进行适当的线性变换,转换为一个(良态) 新矩阵, 从而达到改善迭代法收敛性的目的.

预处理子选取基本准则：

一个好的预处理子P 通常需满足下面两个要求:
(1) $P^{-1} A$ 具有更小的条件数和(或) 更好的特征值分布; P是A的一个很好的近似。
(2) 线性方程组Pz = r 容易求解, 即预处理子P 的使用成本低廉.
▶ 第一条是为了确保预处理后的线性方程组更容易求解, 即预处理子有效
▶ 第二条是因为在用Krylov 子空间方法求解预处理后的方程组时, 每步迭代都需要额外求解一个以P 为系数矩阵的线性方程组, 为了不增加太多额外的运算成本, 必须很容易求解.

Note：一个比较有意思的事情是, 对病态矩阵A 做预处理, 要使得其条件数大大降低,预处理子P 也通常是病态的.

预处理子的种类

预处理子的分类(按构造方式)

(a) 代数预处理子(Algebraic Preconditioner), 即仅仅根据所给方程组的系数矩阵来构造预处理子, 这类预处理子具有一定的通用性, 便于做成黑盒子.
(b) 专属预处理子(Problem-Specific Preconditioner), 即根据问题的机理或物理背景所构造的专属预处理子, 这类预处理子往往具有很好的数值表现.

这里我们只介绍代数预处理子

1. 基于矩阵分裂的预处理子

理论上讲，任何一个矩阵分裂都可以定义一个预处理子. 但为了使得预处理子能有很好的预处理效果, 往往需要其在一定意义下与A 充分接近.

设

A=D-L-U，

其中D, −L, −U 分别是A 的对角部分, 严格下三角部分和严格上三角部分, 并假定D 非奇异. 则由我们之前讨论的定常迭代法, 可以立即得到下面的预处理子:

 Jacobi 预处理子(或对角预处理子): P = D;
 Gauss-Seidel 预处理子(或三角预处理子): P = D − L 或P = D − U;
 SOR 预处理子: P = D − ωL 或P = D − ωU;
 SSOR 预处理子: P = (D − ωL) $D^{-1}$ (D − ωU);
 SGS 预处理子: P = (D − L) $D^{-1}$ (D − U).
 HSS 预处理子: P = (αI + H)(αI + S)
 ADI 预处理子: P = (αI + A1)(αI + A2)