预条件

形式陈述 ​

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

左预条件把系统改写为

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

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

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

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

右预条件先解

$$A{M}_R^{-1}y=b,x=M_R^{-1}y.$$

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

$$b-A{M}_R^{-1}y$$

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

更一般的分裂预条件为

$$M_L^{-1}A{M}_R^{-1}y=M_L^{-1}b,x=M_R^{-1}y.$$

对 Hermitian 正定系统，若 $M=C{C}^{\ast }$ 也正定，可用对称变换

$$C^{-1}A{C}^{-\ast }y=C^{-1}b,x=C^{-\ast }y,C^{-\ast }=(C^{\ast }{)}^{-1},$$

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

预条件的目标不是只让一个裸条件数变小。对正定系统，共轭梯度的能量误差界直接受预条件算子的谱区间和聚集影响；对非正规系统，特征值聚集或较小 $\kappa$ 仍可能遗漏场值、伪谱和瞬时放大，GMRES 收敛不能由特征值图单独预测。

工程成本应写成

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

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

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

直觉 ​

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

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

例子与边界 ​

考虑尺度失配的正定矩阵

$$A=\left(\begin{array}{cc}{10}^6& 1\\ 1& 2\end{array}\right).$$

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

$$C^{-1}A{C}^{-\mathsf{T}}=\left(\begin{array}{cc}1& 1/\sqrt{2\times {10}^6}\\ 1/\sqrt{2\times {10}^6}& 1\end{array}\right),$$

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

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

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

推论与应用 ​

稀疏矩阵公理库稀疏矩阵表示与运算Sparse matrix · CSR matrix · CSC matrix只存非零项及其位置，以稀疏模式组织矩阵运算、图结构、重排序与填充成本。的存储模式和填充决定预条件器是否能廉价应用，Krylov 子空间公理库Krylov 子空间Krylov subspace · Arnoldi iteration · Lanczos iteration从初始向量反复施加矩阵，生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。则描述变换后的算子被如何探索。定常迭代可复用已有矩阵分裂；不完全因子分解以限制填充换取近似三角求解；层级方法借粗尺度校正低频误差。每条路线都要单独说明保持的结构与失败条件。

GMRES公理库GMRES 方法GMRES · Generalized minimal residual method在 Krylov 仿射空间中逐步最小化线性系统的二范数残差，并权衡 Arnoldi 正交化、存储和重启代价。使用左右预条件时应分别报告原残差和算法内部残差。对多右端、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.