共轭梯度法

维基百科,自由的百科全书
跳转至: 导航搜索

数学上,共轭梯度法是求解特定线性方程组数值解的方法,其中那些矩阵为对称正定。共轭梯度法是一个迭代方法,它适用于稀疏矩阵线性方程组,因为这些系统对于像Cholesky分解这样的直接方法太大了。这种方程组在数值求解偏微分方程时很常见。

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

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

方法的表述[编辑]

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

 Ax = b,

其中n-×-n矩阵A是对称的(也即,AT = A),正定的(也即,xTAx > 0对于所有非0向量x属于Rn),并且是实系数的。

将系统的唯一解记作x*

最后算法[编辑]

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

x0 := 0
k := 0
r0 := b
repeat until rk is "sufficiently small":
k := k + 1
if k = 1
p1 := r0
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}
xk := xk-1 + αk pk
rk := rk-1 - αk A pk
end repeat
结果为xk

外部连接[编辑]

参考[编辑]

共轭梯度法最初出现于

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