预条件子

预条件子（preconditioner）是与原线性系统配合使用的辅助算子，用较便宜的求解变换原问题，使迭代方法更容易收敛。它追求的不是单纯减小矩阵元素，而是在每次额外工作可承受的前提下改善有效谱、尺度或其他影响迭代的结构。构造成本与每次应用成本都应计入总求解时间。

对角缩放改变的是方程的几何形状

考虑 $$A=\left(\begin{array}{cc}4& 1\\ 1& 1\end{array}\right),b=\left(\begin{array}{c}1\\ 2\end{array}\right),x_{\ast }=\left(\begin{array}{c}-1/3\\ 7/3\end{array}\right).$$ 矩阵对称正定，特征值为 $(5\pm \sqrt{13})/2$。取 Jacobi 预条件矩阵 $M=\mathrm{diag}(4,1)$。对称缩放后的矩阵为 $$C=M^{-1/2}A{M}^{-1/2}=\left(\begin{array}{cc}1& 1/2\\ 1/2& 1\end{array}\right).$$ 它的特征值为 $1/2,3/2$，二范数条件数为三，比原矩阵的 $(5+\sqrt{13})/(5-\sqrt{13})\approx 6.1713$ 小。这里比较的是对称缩放后的矩阵，不能把非对称矩阵 $M^{-1}A$ 的普通二范数条件数直接当成同一个数。

原矩阵的误差二次型等值线 eᵀAe=1。两个坐标轴使用相同比例，椭圆形状由矩阵的特征值与特征向量决定。

缩放后的二次型等值线，坐标范围与前图相同。特征值比降为三，坐标变换后椭圆形状改善，原问题的解没有改变。

左、右与对称预条件

左预条件将 $Ax=b$ 改为 $M^{-1}Ax=M^{-1}b$；右预条件令 $x=M^{-1}y$，解 $A{M}^{-1}y=b$。两者均以 $M$ 可逆为前提，实际应用 $M^{-1}v$ 时通常是解 $Mz=v$，不是显式形成逆矩阵。

对于对称正定的 $A,M$，可写成对称系统 $Cy=M^{-1/2}b$、$x=M^{-1/2}y$。实际共轭梯度法一般通过解 $Mz=r$ 完成预条件，无须计算平方根。左预条件残差为 $M^{-1}r$，它小并不自动说明原始残差 $r=b-Ax$ 小；停止准则应说明使用哪一种范数。Netlib 的预条件章节和 SciPy 的 CG 接口分别说明了算子选择与正定条件。

一个可以完整证明的收敛改进

预条件 Richardson 迭代是 $x^{k+1}=x^k+\omega M^{-1}(b-A{x}^k)$。令误差 $e^k=x^k-x_{\ast }$，并定义缩放误差 $y^k=M^{1/2}{e}^k$。代入得 $$y^{k+1}=(I-\omega C)y^k.$$ 因为 $C$ 对称正定，可选正交特征向量，逐个模式的因子为 $1-\omega {\lambda }_j$。取 $$\omega =\frac{2}{{\lambda }_{min}+{\lambda }_{max}},q=\frac{{\lambda }_{max}-{\lambda }_{min}}{{\lambda }_{max}+{\lambda }_{min}}=\frac{\kappa (C)-1}{\kappa (C)+1},$$ 两端特征值的因子模相等，中间特征值的模不大于它们；由正交展开得到 $\Vert e^{k+1}{\Vert }_M\le q\Vert e^k{\Vert }_M$，其中 $\Vert e{\Vert }_M=\sqrt{e^{T}Me}$。这是一条明确的收敛定理，条件包括两个矩阵对称正定及合适的松弛参数。

本例缩放后 $\omega =1,q=1/2$。从零开始，首步为 $x^1=M^{-1}b=(1/4,2{)}^T$；残差为 $(-2,-1/4{)}^T$，第二步为 $x^2=(-1/4,7/4{)}^T$。误差应在 $M$ 范数下比较，而不是只挑一个分量观察。

有解变式把 $A$ 改成 $\mathrm{diag}(1000,1)$，并取同一对角矩阵为 $M$。此时 $C=I$，$\omega =1$ 一步到达解。相反，若 $A$ 的对角线本来全相同但有强耦合，对角缩放可能只改变一个整体常数，不能改善谱的分布。

成本与方法匹配

Jacobi 预条件应用便宜，但只处理分量尺度；不完全LU分解保留部分局部消去信息；区域分解法通过子域求解捕捉局部耦合；多重网格法还利用粗层处理长波误差。稀疏 Cholesky、块结构和物理约束也可提供预条件结构。

对非对称、非正规矩阵，特征值聚集并不单独保证 GMRES 快速收敛；还可能受特征向量与数值域影响。为 CG 使用的预条件子应保持所需正定结构。若预条件作用随迭代改变，则通常需要 flexible 类迭代方法，不能无条件沿用固定预条件的递推证明。

对角预条件的可运行例子

程序专门实现本例的预条件 Richardson 迭代。输入迭代步数，返回全部状态及原始残差范数。每轮是常数成本；一般稀疏 Jacobi 预条件只需要 $O(n)$ 次除法和 $O(n)$ 额外存储，矩阵向量积另计。

Python 3

import math


def jacobi_preconditioned_example(steps):
    if not isinstance(steps, int) or steps < 0:
        raise ValueError("nonnegative integer steps required")
    x = [0.0, 0.0]
    history = []
    for k in range(steps+1):
        r = [1-4*x[0]-x[1], 2-x[0]-x[1]]
        history.append((x[:], math.hypot(*r)))
        if k < steps:
            x = [x[0]+r[0]/4, x[1]+r[1]]
            if not all(math.isfinite(v) for v in x):
                raise OverflowError("nonfinite iterate")
    return history


print(jacobi_preconditioned_example(2))
# states: [0,0], [0.25,2], [-0.25,1.75]
print(jacobi_preconditioned_example(30)[-1][1])  # original residual near zero