FOM

Projection法でとする．

ここで，である． この条件を用いる方法としてFOMについて説明する．

近似解を部分空間から探索する． 探索するときの条件はから，

いま，とし，Arnoldi法で得られるKrylov部分空間の正規直交ベクトルを 並べた行列により，

とすると，は以下のように表される．

のときの残差は，

が解ならばこの式は0となるので，

両辺にを掛ける．

Arnoldi法より実行列の場合，なので，

をこの式から計算し，に代入することで，近似解が得られる． とし，上式をさらに変形する．

まとめると，

この式に基づき近似解を求める方法がFOM(Full Orthogonalization Method)である．

FOMの手順†

FOMでの近似解を求めるアルゴリズムを以下に示す．

を計算
の行列の各要素を0で初期化
for(j = 1,2,...,m){
　　
　　for(i = 1,2,...,j)\{
　　　　
　　　　
　　}
　　
　　if() m=jとしてループを抜ける
　　
}

のループの中は修正グラム・シュミット法を用いたArnoldi法(Arnoldi法#pc5d0806参照)そのものである． ここではが0かどうかで反復を抜ける判断をしているが， 実際には近似解に対する残差の大きさで判断したい． かつなるべく残差を計算するのにコストは掛けたくない． そのため，以下の式を用いる．

この式の導出を以下に示す．

まず，残差ベクトルは，

と表される．いま，であり， また，Arnoldi法より，なので，

より，

よって，残差の大きさは以下となる．

この式を使って残差を求め，それを反復終了条件とすればよい．

FOMの拡張†

FOMの計算コストはである．計算コストを減らすためにいくつかの手法が提案されている． ここでは，FOMの拡張であるFOM(m)，IOM，について簡単に紹介する(概要だけ)．

FOM(m)†

FOMの拡張の一つでRestarted FOMである．FOM(m)のアルゴリズムは，

1. m=1と設定
2. からFOMでを計算
3. として，2に戻る．

mが設定した上限値に達するか，残差が十分小さくなるまで，2,3を繰り返す．

IOM†

グラム・シュミット法において，の反復を

と変更する．これをincomplete orthogonalizationといい，これを用いたFOMを IOM(Incomplete Orthogonalization Method)という．

DIOM†

IOMにおいて問題となるのは，の計算ですべてのが必要になることである． そこで，をからでなく，から計算するように修正したのがDIOM(Direct IOM)である．

IOMでi=j-k+1〜jとしたことで，は値を持つ部分の幅がk+1な行列になる．以下にm=5, k=3の場合の例を示す．

まずとLU分解する． ピボッティングがなければ，分解した行列は以下のようになる．

DIOMではからを求める形にする． FOMのに関する式は，

であり，をLU分解した行列で置き換える．

いま，

とおくと以下のように変形できる．

，それぞれの中身について考えてみる．

• について
  の式はとなり，の各列をとすると，が上三角行列であることから， はガウスの消去法の後退代入を使って以下のように計算される．
  
  よって，はm-1までのを使って算出される．ここでを以下のように書くことにする．
  
• について
  についてもであり，例えば，m=5の場合，
  
  よって，
  
  ただし，である． このようにもm-1以下のから計算される．こちらもの時と同様に以下のように書く．
  

これらのことを使って式を書き換えると，

ここで，はなので，