
_START_ARTICLE_
共役勾配法
_START_SECTION_
詳説
_START_PARAGRAPH_
対称正定値行列Aを係数とするn元連立一次方程式_NEWLINE_Ax = b_NEWLINE_の解をx*とする。
_START_SECTION_
直接法としての共役勾配法
_START_PARAGRAPH_
非零ベクトルu、vが_NEWLINE_を満たすとき、u、vはAに関して共役であるという。Aは対称正定値なので、左辺から内積_NEWLINE_を定義することができる。この内積に関して2つのベクトルが直交するなら、それらのベクトルは互いに共役である。_NEWLINE_この関係は対称で、uがvに対して共役なら、vもuに対して共役である（この場合の「共役」は複素共役と無関係であることに注意）。_NEWLINE_{pₖ}をn個の互いに共役なベクトル列とする。pₖは基底Rⁿを構成するので、Ax = bの解x*をこの基底で展開すると、_NEWLINE_と書ける。ただし係数は_NEWLINE_で与えられる。_NEWLINE_この結果は、上で定義した内積を考えるのが最も分かりやすいと思われる。_NEWLINE_以上から、Ax = bを解くための方法が得られる。すなわち、まずn個の共役な方向を見つけ、それから係数αₖを計算すればよい。
_START_SECTION_
反復法としての共役勾配法
_START_PARAGRAPH_
共役なベクトル列pₖを注意深く選ぶことにより、一部のベクトルからx*の良い近似を得られる可能性がある。そこで、共役勾配法を反復法として利用することを考える。こうすることで、nが非常に大きく、直接法では解くのに時間がかかりすぎるような問題にも適用することができる。_NEWLINE_x*の初期値をx₀ = 0 とする。x*が二次形式_NEWLINE_を最小化する一意な解であることに注意し、最初の基底ベクトルp₁をx = x₀でのfの勾配Ax₀−b=−bとなるように取る。このとき、基底の他のベクトルは勾配に共役である。そこで、この方法を共役勾配法と呼ぶ。_NEWLINE_rₖをkステップ目での残差_NEWLINE_とする。rₖはx = xₖでのfの負の勾配であることに注意されたい。最急降下法はrₖの方向に進む解法である。pₖは互いに共役でなければならないので、rₖに最も近い方向を共役性を満たすように取る。これは_NEWLINE_のように表すことができる（記事冒頭の図を参照）。
_START_SECTION_
アルゴリズム
_START_PARAGRAPH_
以上の方法を簡素化することにより、Aが実対称正定値である場合にAx = bを解くための以下のアルゴリズムを得る。初期ベクトルx₀は近似解もしくは0とする。_NEWLINE_for (k = 0; ; k++) _NEWLINE_    _NEWLINE_    _NEWLINE_    _NEWLINE__NEWLINE_    if  が十分に小さい then_NEWLINE_        break_NEWLINE__NEWLINE_    _NEWLINE_    _NEWLINE_結果は
_START_SECTION_
Octaveでの共役勾配法の記述例
_START_PARAGRAPH_
Gnu Octaveで書くと以下のようになる。_NEWLINE_ function [x] = conjgrad(A,b,x0)_NEWLINE__NEWLINE_    r = b - A*x0;_NEWLINE_    w = -r;_NEWLINE_    z = A*w;_NEWLINE_    a = (r'*w)/(w'*z);_NEWLINE_    x = x0 + a*w;_NEWLINE_    B = 0;_NEWLINE__NEWLINE_    for i = 1:size(A)(1);_NEWLINE_       r = r - a*z;_NEWLINE_       if( norm(r) < 1e-10 )_NEWLINE_            break;_NEWLINE_       endif_NEWLINE_       B = (r'*z)/(w'*z);_NEWLINE_       w = -r + B*w;_NEWLINE_       z = A*w;_NEWLINE_       a = (r'*w)/(w'*z);_NEWLINE_       x = x + a*w;_NEWLINE_    end_NEWLINE_ end
_START_SECTION_
前処理
_START_PARAGRAPH_
前処理行列とは、Aと同値なP⁻¹A (Pᵀ)⁻¹の条件数がAより小さく、Ax=bよりP⁻¹A  (Pᵀ)⁻¹ x′ =P⁻¹b′の方が容易に解けるような正定値行列 P.Pᵀを指す。前処理行列の生成には、ヤコビ法、ガウス・ザイデル法、対称SOR法などが用いられる。_NEWLINE_最も単純な前処理行列は、Aの対角要素のみからなる対角行列である。これはヤコビ前処理または対角スケーリングとして知られている。対角行列は逆行列の計算が容易かつメモリも消費しない点で、入門用として優れた方法である。より洗練された方法では、κ(A)の減少による収束の高速化とP⁻¹の計算に要する時間とのトレードオフを考えることになる。
_START_SECTION_
正規方程式に対する共役勾配法
_START_PARAGRAPH_
AᵀAは任意の行列に対して対称（半）正定値となるので、係数行列をAᵀA、右辺をAᵀbとする正規方程式を解くことにより、共役勾配法を任意のn×m行列に対して適用することができる（CGNR法）。_NEWLINE_AᵀAx =  Aᵀb_NEWLINE_反復法としては、AᵀAを明示的に保持する必要がなく、行列ベクトル積、転置行列ベクトル積を計算すればよいので、Aが疎行列である場合にはCGNR法は特に有効である。ただし、条件数κ(AᵀA)がκ(A²)に等しいことから収束は遅くなる傾向があり、前処理行列を使用するCGLS、LSQRなどの解法が提案されている。LSQRはAが悪条件である場合に最も数値的に安定な解法である。