预条件共轭梯度法

预条件公理库预条件Preconditioning · Preconditioner用易应用的近似逆改变等价线性系统的尺度与 Krylov 几何，并计入构造、存储和每步应用成本。改变 CG 观察问题的坐标。取分解 $M=C{C}^{\ast }$，令

$C$ 非奇异，且对非零 $u$ 有

所以 $B$ 仍是 Hermitian 正定矩阵，可以对 $By=c$ 应用普通 CG。以下推导使用普通 CG 已有的正交性与最小化定理，证明它如何成为上述 PCG；并不另行重证普通 CG 定理。

记变换坐标中的残差和搜索方向为 $s_k,q_k$，映回原变量时定义

普通 CG 的初始方向 $q_0=s_0$ 因而给出

它的步长分子和分母分别变成

因此 ${\alpha }_k=(s_k^{\ast }{s}_k)/(q_k^{\ast }B{q}_k)$ 正好给出 PCG 的步长。对普通更新 $y_{k+1}=y_k+{\alpha }_k{q}_k$ 左乘 $C^{-\ast }$，便得到原变量的 $x$ 更新；对 $s_{k+1}=s_k-{\alpha }_{k}B{q}_k$ 左乘 $C$，便得到 $r_{k+1}=r_k-{\alpha }_{k}A{p}_k$。剩下两条普通 CG 递推为

第二式左乘 $C^{-\ast }$ 后成为 $p_{k+1}=M^{-1}{r}_{k+1}+{\beta }_k{p}_k$，完整解释了 apply 和方向更新的来源。$C$ 只用于证明，执行算法不必构造或调用它。

同一映射也确定了正确的内积几何公理库内积空间Inner product space带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。。普通 CG 的 $s_i^{\ast }{s}_j=0$ 与 $q_i^{\ast }B{q}_j=0$ 分别给出

原残差在 $M^{-1}$ 内积中正交，搜索方向仍在原来的 $A$ 内积中共轭。通常并没有 $r_i^{\ast }{r}_j=0$；把普通 CG 的 Euclidean 残差正交性直接搬到原变量，会遗漏整个坐标变化。

令 $T=M^{-1}A$。它通常不是 Euclidean Hermitian 矩阵，因为 $T^{\ast }=A{M}^{-1}$；但它在 $M$ 内积中满足

此外 $C^{\ast }T{C}^{-\ast }=B$，故 $T$ 与正定矩阵 $B$ 相似，具有相同的正特征值。PCG 的几何来自这种带权自伴性，不能由“左乘以后看起来更好解”替代。

取一个只需二阶块求解和一次缩放的预条件器：

令

$B$ 的特征值为 $2-\sqrt{2},2,2+\sqrt{2}$，所以 $A,M$ 均正定。这里 $M\ne A$，且 $(AM{)}_{12}=22$、$(MA{)}_{12}=18$，两者并不交换；因而此例保留了左预条件算子不对称的真实情形。对向量 $r=(r^{(1)},r^{(2)},r^{(3)}{)}^{\mathsf{T}}$，apply 明确为

以下均为精确分数，表中三元组表示列向量。先列出每个时刻的解、残差和预条件残差：

产生这些状态的三个搜索方向及其矩阵乘积为

标量更新与误差检查单独列出。最后一行的 ${\rho }_3=0$ 是由零残差得出的值，不需要再执行 apply。

例如第二步的分母为 $p_1^{\mathsf{T}}A{p}_1=3/8$，所以 ${\alpha }_1=(1/4)/(3/8)=2/3$；它把 $(0,-1,0{)}^{\mathsf{T}}$ 更新为 $(0,0,4/3{)}^{\mathsf{T}}$。第三步的分母为 $4/27$，所以 ${\alpha }_2=(1/9)/(4/27)=3/4$，直接得到 $A{x}_3=b$。这完整执行了三步递推，而非仅展示初始与最终状态。

这个历史同时区分了三种量。首先 $r_0^{\mathsf{T}}{r}_1=-1$，但 $r_0^{\mathsf{T}}{M}^{-1}{r}_1=0$，正交性确实依赖权重。其次，第二步的原残差范数由 $1$ 增到 $4/3$，能量误差平方却由 $1/4$ 降到 $1/12$。最后，${\rho }_k$ 与能量误差平方的数值也不相同；本例中二者恰好都下降，不能据此把预条件残差当作能量误差。

谱改善也可以精确检查：

原矩阵的坐标 Rayleigh 商给出 ${\lambda }_{max}(A)\ge 32$、${\lambda }_{min}(A)\le 2$，从而 ${\kappa }_2(A)\ge 16$。廉价块预条件确实缩小了谱跨度；它没有把 $B$ 变成单位阵，也没有消除所有耦合。

固定线性正定的 apply 是上述推导的边界。若每一步改变内层求解容差，或使用依赖输入的非线性近似过程，就不再有同一个 $C$ 和同一个 $B$；普通 ${\rho }_{k+1}/{\rho }_k$ 公式因而失去这里给出的依据。即使每次返回的向量都看似合理，也需要适用于该变化方式的算法分析。

令 $e_k=x_{\ast }-x_k$。坐标映射保持能量误差，因为

又因 $C^{-\ast }B=T{C}^{-\ast }$ 且 $C^{-\ast }{s}_0=z_0$，有

将普通 CG 的最小化定理沿这两个等式映回，就得到 PCG 在原变量中的精确结论：

因此能量误差随嵌套的Krylov 子空间公理库Krylov 子空间Krylov subspace · Arnoldi iteration · Lanczos iteration从初始向量反复施加矩阵，生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。单调不增。若 $s_0$ 关于 $B$ 的最小多项式次数为 $d$，精确算术中至多 $d\le n$ 步终止；浮点运算中不保证第 $n$ 步得到零残差。

普通 CG 的谱界同样映回为

这里使用对称正定 $B$ 的条件数公理库线性方程组的条件数与扰动Conditioning of linear systems · Matrix condition number把一般问题条件性具体化为可逆线性系统的右端、系数矩阵与联合扰动界。。虽然 $T=M^{-1}A$ 与 $B$ 的特征值相同，非酉相似一般不保持奇异值，因此不能把上式中的 $\kappa$ 换成 Euclidean 奇异值条件数 ${\kappa }_2(T)$。该界只使用谱端点；特征值聚集与初始误差的分量还会影响实际迭代数。

对大型稀疏 SPD 系统，标准 PCG 每个继续迭代的周期需要一次 $A$ 乘法、一次 apply、两个主要内积和 $O(n)$ 向量更新；除算子及预条件结构外，只需常数个长向量。若完成 $k\ge 1$ 次更新并在最后一次更新后直接停止，apply 的调用数是初始一次加中间 $k-1$ 次，共 $k$ 次。初始残差计算和另行重算真实残差所需的 $A$ 乘法也必须记录；已知 $x_0=0$ 时可省略初始的零向量乘法。

把设置、应用和检查分开，总成本可写为

其中 $N_A$ 包含初始及验证残差的矩阵乘法，$N_M$ 是实际 apply 次数，$C_{\mathrm{checks}}$ 计入额外范数与通信归约。预条件器的因子、填充或层级存储也属于成本。比较方法时，应同时报告设置时间与总求解时间；多个右端能摊销设置，而一次短求解未必能回本。

有限精度会使递推残差偏离 $b-A{x}_k$，并使精确正交性逐渐丢失。可以用递推残差筛选候选停止点，再以重算的真实残差决定成功；长迭代也可定期检查漂移。如果把重算残差替换进迭代并继续，应重新设置 $z=M^{-1}r$、$p=z$、$\rho =r^{\ast }z$，作为一次重启，而不是保留旧方向并继续声称完整共轭性。

非零残差下的 $\rho \le 0$、$p^{\ast }Ap\le 0$ 或非有限输出，与精确固定 SPD 合约不相容，实际实现应停止并报告数值故障或接口失败；达到预算上限则返回未收敛状态及真实残差。初始零残差是正常成功路径，须在任何 apply 或步长除法之前处理。这样，理论中的有限步终止、用户要求的原系统精度和机器上的实际退出原因才有各自明确的含义。