共轭梯度法

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

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

双共轭梯度法（英語：BiConjugate gradient method）提供了一种处理非对称矩阵情况的推广。

方法的表述

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

$Ax=b,$

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

最后算法

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

${\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{repeat}}\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad {\hbox{if }}r_{k+1}{\text{ is sufficiently small, then exit loop}}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad k:=k+1\\&{\text{end repeat}}\\\end{aligned}}$

结果为 ${x}_{k+1}$.

外部链接

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