共轭梯度法

共轭梯度法（Template:Lang-en），是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法，它适用于系数矩阵为稀疏矩阵的线性方程组，因为使用像Cholesky分解这样的直接方法求解这些系统所需的计算量太大了。这种方程组在数值求解偏微分方程时很常见。

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

双共轭梯度法（Template:Lang-en）提供了一种处理非对称矩阵情况的推广。

方法的表述

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

$Ax=b,$

其中 $n\times n$ 矩阵 $A$ 是对称的（即 $A^T=A$），正定的（即 $\mathrm{\forall }\overrightarrow{x}\ne 0,{\overrightarrow{x}}^{T}A\overrightarrow{x}>0$），并且是实系数的。 将系统的唯一解记作 $x_{*}$。

最后算法

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

$\begin{array}{cc}& {𝐫}_0:=𝐛-{𝐀𝐱}_0\\ & {𝐩}_0:={𝐫}_0\\ & k:=0\\ & \text{repeat}\\ & {\alpha }_k:=\frac{{𝐫}_k^{𝖳}{𝐫}_k}{{𝐩}_k^{𝖳}{𝐀𝐩}_k}\\ & {𝐱}_{k+1}:={𝐱}_k+{\alpha }_k{𝐩}_k\\ & {𝐫}_{k+1}:={𝐫}_k-{\alpha }_k{𝐀𝐩}_k\\ & \text{if }{r}_{k+1}\text{ is sufficiently small, then exit loop}\\ & {\beta }_k:=\frac{{𝐫}_{k+1}^{𝖳}{𝐫}_{k+1}}{{𝐫}_k^{𝖳}{𝐫}_k}\\ & {𝐩}_{k+1}:={𝐫}_{k+1}+{\beta }_k{𝐩}_k\\ & k:=k+1\\ & \text{end repeat}\\ \end{array}$

结果为 $x_{k+1}$.

外部链接

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

相關

• 共轭梯度法的推导
• Template:Tsl

参考

共轭梯度法最初出现于

• 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.