Arnoldi法

アーノルディ法(Arnoldi's Method)は非対称行列のKrylov部分空間における正規直交基底を求める方法である． ちなみに対称行列に限定したLanczos法もある．

Arnoldi法のアルゴリズムを以下に示す．

任意のベクトルを設定(ただし)
for(){
　　
　　
　　
　　もし，なら反復終了
　　
}

ここでAは対象となる非対称行列である．

wの計算手順をまとめて書くと，

となり，なので， はグラム・シュミットの直交化法でベクトルからに 直交するベクトルを求めていることになる． そのため， Arnoldi法でj=mまで計算された場合， はKrylov部分空間の正規直交基底

を構成する．

さて，アルゴリズムより，

であり，これを変形すると，

ここでである． この式がどのような形になっているのかを確かめるために， m=3の場合で，を列とする行列を使って書き下してみる．

上記の式はこのように書ける．これをm次元に一般化する． の行列を使うと，

は基本ベクトルである． はヘッセンベルグ標準形と呼ばれる形式になっており， 行列AをKrylov部分空間に射影した行列となっている． は直交行列なので，この式の両辺にを掛けると，

となる．

ちなみに，Aとの固有値は同じとなるので， この方法は固有値計算にも用いられる．

修正グラム・シュミット法を用いたArnoldi法†

修正グラムシュミット法(グラム・シュミットの直交化法参照)を使ったArnoldi法のアルゴリズムを以下に示す．

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

丸め誤差がなければ通常のArnoldi法と結果は同じとなる．