Remove ads

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

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

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

方法的表述

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

其中 矩陣 對稱的(即 ),正定的(即 ),並且是實系數的。 將系統的唯一解記作

Remove ads

最後算法

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

結果為 .

Remove ads

外部連結

相關

參考

共軛梯度法最初出現於

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

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads