共轭梯度法

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

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

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

方法的表述
设我们要求解下列线性系统
: 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{align}
& \mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_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{A p}_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{A p}_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{align}

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

外部链接

• [http://www.math-linux.com/article.php3?id_article=5 Méthode du gradient conjugé] （共轭梯度法，法语）作者N. Soualem.
• [http://www.math-linux.com/article.php3?id_article=12 Méthode du gradient conjugé préconditionné] （预处理共轭梯度法，法语）作者N. Soualem.
• [http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf 共轭梯度法通俗介绍] 作者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.