共軛梯度法

共軛梯度法（英語：Conjugate gradient method），是求解系數矩陣為對稱正定矩陣的線性方程組的數值解的方法。共軛梯度法是一個疊代方法，它適用於系數矩陣為稀疏矩陣的線性方程組，因為使用像Cholesky分解這樣的直接方法求解這些系統所需的計算量太大了。這種方程組在數值求解偏微分方程時很常見。

共軛梯度法也可以用於求解無約束的最優化問題。

雙共軛梯度法（英語：BiConjugate gradient method）提供了一種處理非對稱矩陣情況的推廣。

方法的表述

設我們要求解下列線性系統

$Ax=b,$

其中 $n\times n$ 矩陣 $A$ 是對稱的（即 $A^{T}=A$），正定的（即 $\forall {\vec {x}}\neq 0,{\vec {x}}^{T}A{\vec {x}}>0$），並且是實系數的。 將系統的唯一解記作 $x_{*}$。

最後算法

經過一些簡化，可以得到下列求解 $Ax=b$ 的算法，其中 $A$ 是實對稱正定矩陣。

${\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{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 {Ap} _{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 {Ap} _{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{aligned}}$

結果為 ${x}_{k+1}$.

外部連結

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