共役勾配法
詳説
対称正定値行列Aを係数とするn元連立一次方程式
Ax = b
の解をx*とする。
直接法としての共役勾配法
非零ベクトルu、vが
を満たすとき、u、vはAに関して共役であるという。Aは対称正定値なので、左辺から内積
を定義することができる。この内積に関して2つのベクトルが直交するなら、それらのベクトルは互いに共役である。
この関係は対称で、uがvに対して共役なら、vもuに対して共役である（この場合の「共役」は複素共役と無関係であることに注意）。
{pₖ}をn個の互いに共役なベクトル列とする。pₖは基底Rⁿを構成するので、Ax = bの解x*をこの基底で展開すると、
と書ける。ただし係数は
で与えられる。
この結果は、上で定義した内積を考えるのが最も分かりやすいと思われる。
以上から、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とする。
for (k = 0; ; k++) 
    
    
    

    if  が十分に小さい then
        break

    
    
結果は
Octaveでの共役勾配法の記述例
Gnu Octaveで書くと以下のようになる。
 function [x] = conjgrad(A,b,x0)

    r = b - A*x0;
    w = -r;
    z = A*w;
    a = (r'*w)/(w'*z);
    x = x0 + a*w;
    B = 0;

    for i = 1:size(A)(1);
       r = r - a*z;
       if( norm(r) < 1e-10 )
            break;
       endif
       B = (r'*z)/(w'*z);
       w = -r + B*w;
       z = A*w;
       a = (r'*w)/(w'*z);
       x = x + a*w;
    end
 end
前処理
前処理行列とは、Aと同値なP⁻¹A (Pᵀ)⁻¹の条件数がAより小さく、Ax=bよりP⁻¹A  (Pᵀ)⁻¹ x′ =P⁻¹b′の方が容易に解けるような正定値行列 P.Pᵀを指す。前処理行列の生成には、ヤコビ法、ガウス・ザイデル法、対称SOR法などが用いられる。
最も単純な前処理行列は、Aの対角要素のみからなる対角行列である。これはヤコビ前処理または対角スケーリングとして知られている。対角行列は逆行列の計算が容易かつメモリも消費しない点で、入門用として優れた方法である。より洗練された方法では、κ(A)の減少による収束の高速化とP⁻¹の計算に要する時間とのトレードオフを考えることになる。
正規方程式に対する共役勾配法
AᵀAは任意の行列に対して対称（半）正定値となるので、係数行列をAᵀA、右辺をAᵀbとする正規方程式を解くことにより、共役勾配法を任意のn×m行列に対して適用することができる（CGNR法）。
AᵀAx =  Aᵀb
反復法としては、AᵀAを明示的に保持する必要がなく、行列ベクトル積、転置行列ベクトル積を計算すればよいので、Aが疎行列である場合にはCGNR法は特に有効である。ただし、条件数κ(AᵀA)がκ(A²)に等しいことから収束は遅くなる傾向があり、前処理行列を使用するCGLS、LSQRなどの解法が提案されている。LSQRはAが悪条件である場合に最も数値的に安定な解法である。