跳至內容

共軛梯度法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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