共轭梯度法

共轭梯度法

共轭梯度法

共轭梯度法（Conjugate Gradient, CG）是[[Krylov子空间方法]]家族中最著名的成员，专门用于求解对称正定矩阵的线性方程组。由[[马格努斯·赫斯提尼斯]]和[[爱德华·施蒂费尔]]于1950年共同发明，被认为是20世纪最伟大的十大算法之一。

核心思想

共轭梯度法引入了**“A-共轭”（A-Conjugate）**的概念：两个向量 $p_i$ 和 $p_j$ 关于矩阵A正交，即 $p_i^T A p_j = 0$（$i \neq j$）。这保证了每次搜索方向在矩阵A的"视角"下完全独立，避免了[[最速下降法]]的"之"字形震荡。

算法伪代码

1
2
3
4
5
6
7
8
初始化：r₀ = b - Ax₀, p₀ = r₀

对于 k = 0, 1, 2, ... 直到收敛：
    αₖ = (rₖᵀrₖ) / (pₖᵀApₖ)      // 步长计算
    xₖ₊₁ = xₖ + αₖpₖ              // 更新解
    rₖ₊₁ = rₖ - αₖApₖ             // 更新残差
    βₖ = (rₖ₊₁ᵀrₖ₊₁) / (rₖᵀrₖ)   // 共轭参数
    pₖ₊₁ = rₖ₊₁ + βₖpₖ            // 新搜索方向

关键性质

  • 每次迭代只需一次矩阵-向量乘法（$Ap_k$）
  • 残差向量自动正交：$r_i^T r_j = 0$（$i \neq j$）
  • 搜索方向A-共轭：$p_i^T A p_j = 0$（$i \neq j$）
  • 理论上最多n步收敛到精确解，实际中只需远少于n步即可获得工程可接受的近似解

应用

共轭梯度法是现代科学计算的基石，广泛应用于[[有限元分析]]、[[计算流体力学]]、医疗影像重建等领域。

分享到