预条件 | Codeboy's Blog

形式陈述

考虑 $Ax=b$ ，选取非奇异算子 $M$ ，使线性方程 $Mz=v$ 比原系统容易求解，并使 $M$ 在相关方向上近似 $A$ 。预条件算法不显式形成 $M^{-1}$ ；每次出现 $M^{-1}v$ 都表示调用一次求解或近似求解过程。

左预条件把系统改写为

M_L^{-1}Ax=M_L^{-1}b.

解变量仍是 $x$ ，但 Krylov 方法直接看到的残差是

\widetilde r=M_L^{-1}(b-Ax).

例如左预条件 GMRES 最小化 $\|\widetilde r\|_2$ ，它未必与原残差 $\|b-Ax\|_2$ 同步。停止时应显式重算并检查用户真正关心的原残差或后向误差，不能把预条件残差的阈值直接改名为原系统精度。

右预条件先解

AM_R^{-1}y=b, \qquad x=M_R^{-1}y.

此时迭代变量是 $y$ ，而 Krylov 残差

b-AM_R^{-1}y

恰是原系统在映回 $x$ 后的残差。实现必须保存变量映射，并在输出、更新量和停止准则中使用一致的 $x$ ；忘记最后一次 $M_R^{-1}$ 应用会返回错误变量，而不只是少一次优化。

更一般的分裂预条件为

M_L^{-1}AM_R^{-1}y=M_L^{-1}b, \qquad x=M_R^{-1}y.

对 Hermitian 正定系统，若 $M=CC^*$ 也正定，可用对称变换

C^{-1}AC^{-*}y=C^{-1}b, \qquad x=C^{-*}y, \qquad C^{-*}=(C^*)^{-1},

保留 Hermitian 正定结构。任意左乘 $M^{-1}A$ 一般不会在 Euclidean 内积下保持对称，不能直接套用共轭梯度的标准推导。

预条件的目标不是只让一个裸条件数变小。线性系统条件数描述解对输入扰动的最坏敏感性，却不能独自预测每个迭代法的轨迹。对正定系统，共轭梯度法的能量误差界直接受预条件算子的谱区间和聚集影响；对非正规系统，特征值聚集或较小 $\kappa$ 仍可能遗漏场值、伪谱和瞬时放大，GMRES 收敛不能由特征值图单独预测。

工程成本应写成

C_{\mathrm{setup}} +k\bigl(C_A+C_M+C_{\mathrm{orth}}\bigr),

其中 $C_{\mathrm{setup}}$ 是构造成本， $C_M$ 是每次应用预条件器的求解成本， $k$ 是迭代步数。还要计入因子填充、层级结构或辅助向量的存储。昂贵设置若能在多个右端或相邻时间步复用，可能值得；只解一次且迭代数下降很少时，设置成本可能超过节省。

输入接口至少应给出 $A$ 的矩阵—向量乘、 $M$ 的应用、左右位置、容差和预算；输出应记录设置时间、每步应用次数、原残差、预条件残差与失败状态。若 $M$ 奇异、应用产生非有限值或内层求解未达到约定精度，外层算法必须报告预条件失败。

直觉

预条件不是改变答案，而是换一套更适合迭代观察的坐标和尺度。原系统若把某些方向压得很扁、另一些方向拉得很长，Krylov 多项式要同时处理这些尺度便会前进缓慢；近似逆把它们拉回相近范围，让少数方向组合就能显著削减残差。

“近似 $A$ ”与“容易求解”构成真实权衡。取 $M=A$ 会把预条件算子变成单位阵，却要求每一步先精确解原问题；取 $M=I$ 没有设置成本，也没有改善。实用设计位于两端之间，并由总时间和存储而不是迭代次数单独评价。

例子与边界

考虑尺度失配的正定矩阵

A= \begin{pmatrix} 10^6&1\\ 1&2 \end{pmatrix}.

其 $2$ -范数条件数约为 $5.00\times10^5$ 。取对角预条件器 $M=\operatorname{diag}(10^6,2)=CC^{\mathsf T}$ ，对称分裂后

C^{-1}AC^{-\mathsf T} = \begin{pmatrix} 1&1/\sqrt{2\times10^6}\\ 1/\sqrt{2\times10^6}&1 \end{pmatrix},

特征值为 $1\pm1/\sqrt{2\times10^6}$ ，条件数约 $1.0014$ 。这个例子展示对角缩放怎样去掉单位与量级失配；它不证明对角预条件能处理所有由网格、耦合或非正规性造成的困难。

不完全因子分解可以保留稀疏近似三角结构，但丢弃填充会降低近似质量，某些矩阵上还可能出现零主元或不稳定增长。更强的层级预条件器可减少外层迭代，却增加设置、通信和内存。二者都应按总成本比较，而不是把“迭代数更少”当作充分结论。

若预条件器随迭代步改变，例如内层求解每次采用不同容差，标准固定算子的 GMRES 关系不再成立。此时需要 flexible GMRES 一类保留每个预条件后向量的方法；静默地把可变 $M_k$ 塞进普通 GMRES 会破坏其搜索空间解释。

推论与应用

稀疏矩阵的存储模式和填充决定预条件器是否能廉价应用，Krylov 子空间则描述变换后的算子被如何探索。定常迭代可复用已有矩阵分裂；不完全因子分解以限制填充换取近似三角求解；层级方法借粗尺度校正低频误差。每条路线都要单独说明保持的结构与失败条件。

GMRES使用左右预条件时应分别报告原残差和算法内部残差。对多右端、Newton 线性化或时间步进序列，还应说明预条件器何时重建；复用过久可能让设置摊销更好，也可能因矩阵变化而失效。

参考资料

Richard Barrett et al., Templates for the Solution of Linear Systems, 2nd ed., SIAM, 1994, Ch. 3.
Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, Chs. 9–10.
Michele Benzi, “Preconditioning Techniques for Large Linear Systems: A Survey,” Journal of Computational Physics 182(2), 2002, pp. 418–477.

形式陈述 ​

反向链接

形式陈述