共軛梯度法(英語: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.