共轭梯度法

数学上，共轭梯度法是求解特定线性系统的数值解的方法，其中那些矩阵为对称和正定。共轭梯度法是一个迭代方法，所以它适用于稀疏矩阵系统，因为这些系统对于象乔莱斯基分解这样的直接方法太大了。这种系统在数值求解偏微分方程时相当常见。

共轭梯度法也可以用于求解无约束的最優化问题。

双共轭梯度法提供了一种处理非对称矩阵情况的推广。

方法的表述

设我们要求解下列线性系统

$Ax = b,$，

其中n-×-n矩阵A是对称的（也即，A^T = A），正定的（也即，x^TAx > 0对于所有非0向量x属于Rⁿ），并且是实系数的。

将系统的唯一解记作x_*。

最后算法

经过一些简化，可以得到下列求解Ax = b的算法，其中A是实对称正定矩阵。

x₀ := 0

k := 0

r₀ := b

repeat until r_k is "sufficiently small":

k := k + 1

if k = 1

p₁ := r₀

else

$p_k := r_{k-1} + \frac{r_{k-1}^\top r_{k-1}}{r_{k-2}^\top r_{k-2}}~p_{k-1}$

end if

$\alpha_k := \frac{r_{k-1}^\top r_{k-1}}{p_k^\top A p_k}$

x_k := x_k-1 + α_k p_k

r_k := r_k-1 - α_k A p_k

end repeat

结果为x_k

外部连接

• Méthode du gradient conjugé（共轭梯度法，法语）作者N. Soualem.
• Méthode du gradient conjugé préconditionné（预处理共轭梯度法，法语）作者N. Soualem.
• 共轭梯度法通俗介绍作者Jonathan Richard Shewchuk.

参考

共轭梯度法最初出现于

• Magnus R. Hestenes and Eduard Stiefel（1952）,Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49, 409–436.

下列教科书中可以找到该方法的描述

• Kendell A. Atkinson（1988）,An introduction to numerical analysis（2nd ed.）,Section 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
• Gene H. Golub and Charles F. Van Loan, Matrix computations（3rd ed.）,Chapter 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.