共役勾配アルゴリズムの導出

とに関する関係式を使って共役勾配法のアルゴリズムを導き出してみる． まず，基本的なProjection法のステップを思いだそう．

ここで，である． これをDirect版Lanczosアルゴリズムに当てはめる．とすると，

これまで，から始まっていたが，ここではより一般的なからのスタートにしてあるので注意． また，と書き換えている． 次にの更新式を考える． Direct版のLanczosではであり， はのスカラー倍になっているので，残差ベクトルと前ステップのを使って，

と書ける． なお，式中のはの要素として使っていたとは別物なので注意．

前節で述べた，の直交，共役関係を使ってを算出することで，共役勾配法のアルゴリズムが得られる．

• の導出
  に関する関係式よりなので，
  
  これをについて解くと以下となる．
  
  分母について，の性質を用いると，
  
  となる．よって，
  

• の導出
  の関係を用いる．まず，
  
  であり，よって以下のようにに関する式が求められる．
  
  これをさらに変形する． いま，から， なので，
  
  より，最終的に，
  

これらの式から，以下の共役勾配法のアルゴリズムが得られる．

を計算
for(j = 0,1,...){
　　
　　
　　
　　if(収束判定) 反復終了
　　
　　
}