共轭梯度法
维基百科,自由的百科全书
数学上,共轭梯度法实求解特定线性系统的数值解的方法,其中那些矩阵为对称和正定。共轭梯度法是一个迭代方法,所以它适用于稀疏矩阵系统,因为这些系统对于象乔莱斯基分解这样的直接方法太大了。这种系统在数值求解偏微分方程时相当常见。
共轭梯度法也可以用于求解无约束优化问题。
双共轭梯度法提供了一种处理非对称矩阵情况的推广。
目录 |
[编辑] 方法的表述
设我们要求解下列线性系统
其中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
- end if
- xk := xk-1 + αk pk
- rk := rk-1 - αk A pk
- end repeat
- 结果为xk
[编辑] 外部连接
- 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.