前処理付き共役勾配法

ウィキペディア

共役勾配法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/10 14:23 UTC 版)

線型方程式の二次形式を最小化するための、最適なステップサイズによる最急降下法（緑）の収束と共役勾配法（赤）の収束の比較。共役勾配法は、厳密にはn次の係数行列に対して高々nステップで収束する（ここではn=2）。

共役勾配法（きょうやくこうばいほう、英: conjugate gradient method、CG法とも呼ばれる）は対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズムである。反復法として利用され、コレスキー分解のような直接法では大きすぎて取り扱えない、大規模な疎行列を解くために利用される。そのような問題は偏微分方程式などを数値的に解く際に常に現れる。

共役勾配法は、エネルギー最小化などの最適化問題を解くために用いることもできる。

双共役勾配法は、共役勾配法の非対称問題への拡張である。

また、非線形問題を解くために、さまざまな非線形共役勾配法が提案されている。

詳説

対称正定値行列Aを係数とするn元連立一次方程式

Ax = b

の解をx_*とする。

直接法としての共役勾配法

非零ベクトルu、vが

$\mathbf {u} ^{\mathrm {T} }\mathbf {A} \mathbf {v} =\mathbf {0}$ カテゴリ