共轭梯度法

维库，知识与思想的自由文库

跳转到: 导航, 搜索

2个分类: 数值线性代数 | 优化算法

数学上，共轭梯度法实求解特定线性系统的数值解的方法，其中那些矩阵为对称和正定。共轭梯度法是一个迭代方法，所以它适用于稀疏矩阵系统，因为这些系统对于象乔莱斯基分解这样的直接方法太大了。这种系统在数值求解偏微分方程时相当常见。

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

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

[编辑] 方法的表述

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

$Ax = b,\,$

其中n-×-n矩阵A 是对称的(也即，A^T = A)，正定的(也即，x^TAx > 0 对于所有非0向量x属于Rⁿ)，并且是实系数的。

将系统的唯一解记作x_*。

[编辑] 最后算法

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

x₀ := 0

k := 0

r₀ := b

repeat until r_k is "sufficiently small":

k := k + 1

if k = 1

p₁ := r₀

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}$

x_k := x_k-1 + α_k p_k

r_k := r_k-1 - α_k A p_k

end repeat

结果为x_k

[编辑] 外部连接

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.

来自“http://www.wikilib.com/wiki/%E5%85%B1%E8%BD%AD%E6%A2%AF%E5%BA%A6%E6%B3%95”

个人工具