共轭梯度法

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

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

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

双共轭梯度法英语:BiConjugate 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.