連立1次方程式：Lanczos法

対称行列の正規直交基底を算出するLanczos法とその線形方程式への適用，そして，共役勾配法のアルゴリズムの導出について説明する．

---

---

Lanczos法†

Arnoldi法では非対称行列を扱ったが，Aが対称行列だった場合， アルゴリズムを簡素化できる． これがランチョス(Lanczos)法である．

まず，Arnoldi法でAが実対称行列だったとき， も対称行列になる． さらにはヘッセンベルグ行列であり，，ただし i > j+1 である． よって，が対称行列ならば，i < j-1 でもとなる． つまり，以下のような三重対角行列(対角成分とその左右のみに値がある行列)となる．

ここで，とした．

の代わりにを使って， Arnoldi法(修正グラム・シュミットを用いたもの)を書き換える．

今，i < j-1でが0となることから，i=j-1,jについてのみ考えればよい． i=j-1では，なので，と置き換えることができる． ただし，と置いておく． 次に，i=jでは，なので，と置き換えることができる． 最後にと置き換え，は次の反復においてとして用いられる． これらのことを適用するとアルゴリズムは以下のようになる．

任意のベクトルを設定(ただし)
を設定
for(j = 1,2,...,m){
　　
　　
　　
　　
　　if() 反復終了
　　
}

これがLanczos法である．

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

Lanczos法から共役勾配法を導くことができる． 共役勾配法は，そのため，FOMと同じくとしたProjection法となる． ここでは，Lanczos法，Direct版のLanczos法を説明し，そこから導き出せる関係式，そして， その関係式を使って共役勾配法のアルゴリズムを導出するまでを説明する．

Lanczos法を使った線形システムの解法†

線形システム(ただし，Aは対称行列)について，初期近似値が与えられたとき， mステップ目の近似値はFOMと同様に以下のようになる．

ここで，が三重対角行列(tridiagonal matrix)になるのでと置き換えている． また，である．

この式からLanczos法を使った線形システムの解法アルゴリズムは以下となる．

を計算
を設定
for(j = 1,2,...,m){
　　
　　
　　
　　
　　if() 反復終了
　　
}
で構成される三重対角行列を設定

Direct版のLanczos法†

FOMからDIOMを導き出したときと同様にDirect版のLanczos法を考える． Lanczos法によるは三重対角行列なので，DIOMにおけるk=2の場合(値がある部分の幅が3)と考えられる． m=5のとき，のLU分解は以下のようになる．

DIOMと同様に，とおくと，

となる．

• に関して
  DIOMのの最後の列に関する式，
  
  において，k=2なので，i=m-1のときだけ考えればよい．つまり，
  
• に関して
  
  となるので，
  
  とする．

最終的にDIOMと同様にからを求める．

この式によりを更新していくのがDirect版のLanczos法である．

Direct版でのはガウス消去法のステップから，

により求めることができる．

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

直交・共役関係†

DIOMで得られた残差ベクトルとについて考えてみる． FOMの収束判定で導いたように，

であり，はのスカラー倍になっている． は直交系であるので，

また，に関しては，以下の関係が成り立つ．

これはAに関する共役を意味しており，A-共役 (A-conjugate)と呼ばれる．Aが単位行列ならばrと同じく直交になる．

これに関する証明を以下に示す．

であるならば，は対角行列になるはずである． なので，

Aは対称行列なので，も対称行列になる． よって，も対称行列である．また，は下三角行列(上三角行列の逆行列もまた上三角行列なので)である． 対称な下三角行列とは要するに対角行列である．よって，は対角行列であり， のA-共役が成り立つ．

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

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

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

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

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

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

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

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

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

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

参考文献†

• Yousef Saad, Iterative methods for sparse linear systems 2nd ed., SIAM, 2003.