查看“︁共轭梯度法”︁的源代码

{{NoteTA
|1=zh-hans:迭代;zh-hant:疊代;
|G1 = Math
}}

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

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

[[双共轭梯度法]]（{{lang-en|BiConjugate gradient method}}）提供了一种处理非对称矩阵情况的推广。

==方法的表述==

设我们要求解下列线性系统
:<math> Ax = b,</math>
其中 <math> n \times n </math> 矩阵 <math>A</math> 是[[对称矩阵|对称]]的（即 <math>A^T = A</math>），[[正定矩阵|正定]]的（即 <math>\forall \vec{x} \neq 0, \vec{x}^T A \vec{x} > 0</math>），并且是实系数的。 将系统的唯一解记作 <math>x_{*}</math>。

===最后算法===

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

:<math>\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}</math>

结果为 <math> {x}_{k+1} </math>.

==外部链接==
* [http://www.math-linux.com/article.php3?id_article=5 Méthode du gradient conjugé] {{Wayback|url=http://www.math-linux.com/article.php3?id_article=5 |date=20070927194624 }}（共轭梯度法，法语）作者N. Soualem.
* [http://www.math-linux.com/article.php3?id_article=12 Méthode du gradient conjugé préconditionné] {{Wayback|url=http://www.math-linux.com/article.php3?id_article=12 |date=20070927194617 }}（预处理共轭梯度法，法语）作者N. Soualem.
* [http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf 共轭梯度法通俗介绍] {{Wayback|url=http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf |date=20201109014320 }}作者Jonathan Richard Shewchuk.

== 相關 ==
*[[共轭梯度法的推导]]
*{{tsl|en|Nonlinear conjugate gradient method|非線性共軛梯度法}}

==参考==

共轭梯度法最初出现于
* 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.
{{authority control}}
[[Category:数值线性代数|G]]
[[Category:最优化算法|G]]