共轭梯度法
概述
共轭梯度法（Conjugate Gradient Method, CG）由赫斯坦尼斯（Hestenes）和施蒂费尔（Stiefel）于 1952 年提出，是求解对称正定（SPD）线性方程组 $Ax=b$ 的迭代方法。核心思想是构造一组关于矩阵 $A$ 共轭（A-conjugate）的搜索方向，在 Krylov 子空间中寻找 $A$-范数最优近似解。CG 每步只需一次矩阵-向量乘法，存储仅需 4 个向量，收敛率依赖条件数的平方根（远优于经典迭代法依赖条件数本身）。配合预处理（PCG）是现代大规模科学计算的核心算法。
关键内容
算法
输入：SPD 矩阵 $A$，向量 $b$，初始猜测 $x_0$
r_0 = b - Ax_0, p_0 = r_0
for k = 0, 1, 2, ...:
α_k = (r_kᵀr_k) / (p_kᵀAp_k) # 步长
x_{k+1} = x_k + α_k p_k # 更新解
r_{k+1} = r_k - α_k A p_k # 更新残差
if ‖r_{k+1}‖ < ε: break
β_k = (r_{k+1}ᵀr_{k+1}) / (r_kᵀr_k) # 共轭系数
p_{k+1} = r_{k+1} + β_k p_k # 更新搜索方向
每步成本：1 次矩阵-向量乘法，2 次内积，4 个向量的存储
三个核心性质
A-共轭性：搜索方向满足 $p_i^T A p_j = 0$（$i \neq j$）——沿一个方向的最优化不破坏其他方向的进展
残差正交性：$r_i^T r_j = 0$（$i \neq j$）——连续迭代步的残差互相正交
Krylov最优性：第 $k$ 步的 $x_k$ 是所有 $K_k(A,r_0) = \text{span}{r_0, Ar_0, \ldots, A^{k-1}r_0}$ 中元素的 $A$-范数最优近似
收敛性
有限终止性（精确算术）：至多 $n$ 步内给出精确解（$n$ 个 A-共轭方向构成 $\mathbb{R}^n$ 的基）
迭代收敛界： $$\frac{|x_k - x^|_A}{|x_0 - x^|A} \leq 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k, \quad \kappa = \kappa(A) = \lambda{\max}/\lambda_{\min}$$
| 方法 | 收敛速率 | 约束 |
|---|---|---|
| Jacobi / Gauss-Seidel | $\rho \approx 1 - O(h^2) \sim 1 - O(1/\kappa)$ | 对角占优 |
| SOR（最优松弛） | $\rho \approx 1 - O(h) \sim 1 - O(1/\sqrt{\kappa})$ | SPD，需知谱半径 |
| CG | $\approx 1 - 2/\sqrt{\kappa}$（无需任何参数） | SPD |
CG 比 SOR 在不需要提前知道谱信息的前提下，达到同等量级的收敛率。
特征值聚集加速：若矩阵特征值形成 $m \ll n$ 个聚集组，约 $m$ 步即可高精度收敛——远优于理论上限 $n$ 步。
历史曲折：从被忽视到复兴
1952 年发表后，CG 一度因有限精度下 A-共轭性会被舍入误差破坏（有限终止性失效）而被视为"有缺陷的直接方法"冷落约 20 年。
1970 年代复兴（三个关键认识转变）： 1. 问题规模急剧增长，直接方法不可行 2. CG 应被视为迭代方法（近似求解），而非直接方法（精确 $n$ 步求解） 3. 预处理技术发展大幅提升实际收敛速度
Reid（1971）综述和 Golub & O'Leary（1989）历史回顾是复兴的重要推动。
预处理共轭梯度法（PCG）
将方程 $Ax=b$ 变换为 $M^{-1}Ax = M^{-1}b$，使 $\kappa(M^{-1}A) \ll \kappa(A)$：
| 预处理器 | 适用场景 |
|---|---|
| 不完全 Cholesky（IC/ICC） | SPD 稀疏矩阵 |
| 代数多重网格（AMG） | PDE 离散化矩阵 |
| 不完全 LU（ILU） | 一般稀疏矩阵 |
| 域分解 | 并行计算 |
PCG 是现代大规模 FEM/FDM/FVM 计算的事实标准求解器。
后续发展
| 方法 | 年份 | 用途 |
|---|---|---|
| 非线性 CG（Fletcher-Reeves） | 1964 | 无约束优化 |
| MINRES | 1975 | 对称不定系统 |
| BiCG | 1976 | 非对称系统 |
| GMRES（Saad-Schultz） | 1986 | 非对称系统，最小残差 |
| BiCGSTAB（van der Vorst） | 1992 | 非对称，更稳定 |
局限性
来源
- raw/books/数值分析/15_conjugate_gradient.md