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

出典:wikipedia