共轭梯度法 (conjugate gradient method) 最早由德国的 Hestenes 和 Stiefel 于 1952 年提出, 适用于系数矩阵对称正定的情形, 收敛速度较上一节的三种迭代法更快. 它的思想基于数学物理中的变分原理.
熟知二次函数 `1/2 ax^2 - bx` 在 `x = b/a` 处取得极小值. 将这一结果推广至 `n` 元函数, 有:
设 `bm A` 为对称正定矩阵. 则方程组 `bm (Ax) = bm b` 的求解等价于求 二次泛函 (二次型) `varphi(bm x) = 1/2 (bm (Ax), bm x) - (bm b, bm x)` 在 `RR^n` 上的极小值.
设 `bm x_0` 是方程组 `bm (Ax) = bm b` 的解, 则有 ` varphi(bm x_0) = 1/2 (bm (Ax_0), bm x_0) - (bm b, bm x_0) = -1/2 (bm (Ax_0), bm x_0)`. 对 `AA bm x in RR^n`, ` varphi(bm x) - varphi(bm x_0) = 1/2 (bm (Ax), bm x) - (bm b, bm x) + 1/2 (bm (Ax_0), bm x_0)` `= 1/2 [(bm (Ax, bm x))-2(bm (Ax_0, bm x)) + (bm (Ax_0), bm x_0)]` `= 1/2 (bm (A(x - x_0)), bm (x-x_0)) = 1/2 ||bm x - bm x_0||_(bm A)^2 ge 0`. 由 `bm A` 的正定性知, `bm x_0` 为 `varphi(bm x)` 的唯一极小值点.