共轭梯度法

共轭梯度法，简称 CG，是面向对称正定系统 Ax = b 的 Krylov 求解器。它背后有一个优美的重新诠释：求解 Ax = b 等价于极小化二次能量 phi(x) = (1/2) x^T A x - b^T x，其唯一极小点就是解。CG 在这个碗状曲面上向下走，但走得很巧妙。

朴素的最速下降在被拉长的碗里来回曲折，效率很差。CG 通过选取 A-共轭的搜索方向来纠正这点：方向 p_i, p_j 满足当 i 不等于 j 时 p_i^T A p_j = 0。共轭方向之间从不互相抵消进展。结果是，在精确算术下，CG 至多 n 步就到达 n 阶系统的精确解——它技术上是一种直接法，尽管我们总是迭代地使用它。

使 CG 实用的是它惊人的节俭：每步只需一次矩阵-向量乘积、几个内积和少数几次向量更新，且无论 n 多大都只存几个向量。它构造的 Krylov 子空间与众人相同，但凭借对称性，用一个简短的三项递推就找到能量极小点，而无须存储整组基。

收敛与条件数 kappa = lambda_max / lambda_min 挂钩。经典界说，k 步后的 A-范数误差大致按 ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))^k 缩小。良态或特征值聚集的矩阵几步就收敛；病态的则爬行——这正是 CG 几乎总要配预处理子运行的原因。