共役勾配法

共役勾配法（きょうやくこうばいほう、、CG法とも呼ばれる）は対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズムである。反復法として利用され、コレスキー分解のような直接法では大きすぎて取り扱えない、大規模な疎行列を解くために利用される。そのような問題は偏微分方程式などを数値的に解く際に常に現れる。
共役勾配法は、エネルギー最小化などの最適化問題を解くために用いることもできる。
は、共役勾配法の非対称問題への拡張である。また、非線形問題を解くために、さまざまな非線形共役勾配法が提案されている。
詳説.
対称正定値行列Aを係数とする"n"元連立一次方程式
の解をx*とする。
直接法としての共役勾配法.
非零ベクトルu、vが
を満たすとき、u、vはAに関して共役であるという。Aは対称正定値なので、左辺から内積
を定義することができる。この内積に関して2つのベクトルが直交するなら、それらのベクトルは互いに共役である。
この関係は対称で、uがvに対して共役なら、vもuに対して共役である（この場合の「共役」は複素共役と無関係であることに注意）。
と書ける。ただし係数は
 \mathbf{A}\mathbf{x}_* = \sum^{n}_{i=1} \alpha_i\mathbf{p}_k^{\mathrm{T}} \mathbf{A} \mathbf{p}_i= \mathbf{p}_k^{\mathrm{T}} \mathbf{b}.</math>
で与えられる。
この結果は、上で定義した内積を考えるのが最も分かりやすいと思われる。
以上から、Ax = bを解くための方法が得られる。すなわち、まず"n"個の共役な方向を見つけ、それから係数α"k"を計算すればよい。
反復法としての共役勾配法.
共役なベクトル列p"k"を注意深く選ぶことにより、一部のベクトルからx*の良い近似を得られる可能性がある。そこで、共役勾配法を反復法として利用することを考える。こうすることで、"n"が非常に大きく、直接法では解くのに時間がかかりすぎるような問題にも適用することができる。
x*の初期値をx0 = 0 とする。x*が二次形式
を最小化する一意な解であることに注意し、最初の基底ベクトルp1をx = x0での"f"の勾配Ax0−b=−bとなるように取る。このとき、基底の他のベクトルは勾配に共役である。そこで、この方法を共役勾配法と呼ぶ。
r"k"を"k"ステップ目での残差
とする。r"k"はx = x"k"での"f"の負の勾配であることに注意されたい。最急降下法はr"k"の方向に進む解法である。p"k"は互いに共役でなければならないので、r"k"に最も近い方向を共役性を満たすように取る。これは
のように表すことができる（記事冒頭の図を参照）。
アルゴリズム.
以上の方法を簡素化することにより、Aが実対称正定値である場合にAx = bを解くための以下のアルゴリズムを得る。初期ベクトルx0は近似解もしくは0とする。
 formula_2
 formula_3
 for (k = 0; ; k++) 
 formula_4
 formula_5
 formula_6
 if formula_7 が十分に小さい then
 break
 formula_8
 formula_9
 結果は formula_10
Octaveでの共役勾配法の記述例.
Gnu Octaveで書くと以下のようになる。
前処理.
前処理行列とは、Aと同値なP-1A (PT)-1の条件数がAより小さく、Ax=bよりP-1A (PT)-1 x′ =P-1b′の方が容易に解けるような正定値行列 P.PTを指す。前処理行列の生成には、ヤコビ法、ガウス・ザイデル法、対称SOR法などが用いられる。
最も単純な前処理行列は、Aの対角要素のみからなる対角行列である。これはヤコビ前処理または対角スケーリングとして知られている。対角行列は逆行列の計算が容易かつメモリも消費しない点で、入門用として優れた方法である。より洗練された方法では、κ(A)の減少による収束の高速化とP-1の計算に要する時間とのトレードオフを考えることになる。
正規方程式に対する共役勾配法.
ATAは任意の行列に対して対称（半）正定値となるので、係数行列をATA、右辺をATbとする正規方程式を解くことにより、共役勾配法を任意の"n"×"m"行列に対して適用することができる（CGNR法）。
反復法としては、ATAを明示的に保持する必要がなく、行列ベクトル積、転置行列ベクトル積を計算すればよいので、"A"が疎行列である場合にはCGNR法は特に有効である。ただし、条件数κ(ATA)がκ(A2)に等しいことから収束は遅くなる傾向があり、前処理行列を使用するCGLS (Conjugate Gradient Least Squares)、LSQRなどの解法が提案されている。LSQRはAが悪条件である場合に最も数値的に安定な解法である。