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

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

任意のベクトルls_arnoldi.eq1.gifを設定(ただしls_arnoldi.eq2.gif)
for(ls_arnoldi.eq3.gif){
  ls_arnoldi.eq4.gif
  ls_arnoldi.eq5.gif
  ls_arnoldi.eq6.gif
  もし,ls_arnoldi.eq7.gifなら反復終了
  ls_arnoldi.eq8.gif
}

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

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

ls_arnoldi.eq9.gif

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

ls_arnoldi.eq15.gif

を構成する.

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

ls_arnoldi.eq16.gif

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

ls_arnoldi.eq17.gif

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

ls_arnoldi.eq20.gif

上記の式はこのように書ける.これをm次元に一般化する. ls_arnoldi.eq21.gifの行列ls_arnoldi.eq22.gifを使うと,

ls_arnoldi.eq23.gif

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

ls_arnoldi.eq28.gif

となる.

ちなみに,Aとls_arnoldi.eq25.gifの固有値は同じとなるので, この方法は固有値計算にも用いられる.

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

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

任意のベクトルls_arnoldi.eq1.gifを設定(ただしls_arnoldi.eq2.gif)
for(j = 1,2,...,m){
  ls_arnoldi.eq29.gif
  for(i = 1,2,...,j){
    ls_arnoldi.eq30.gif
    ls_arnoldi.eq31.gif
  }
  ls_arnoldi.eq32.gif
  if(ls_arnoldi.eq33.gif) 反復終了
  ls_arnoldi.eq8.gif
}

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


添付ファイル: filels_arnoldi.eq30.gif 757件 [詳細] filels_arnoldi.eq11.gif 729件 [詳細] filels_arnoldi.eq28.gif 713件 [詳細] filels_arnoldi.eq5.gif 720件 [詳細] filels_arnoldi.eq2.gif 763件 [詳細] filels_arnoldi.eq12.gif 651件 [詳細] filels_arnoldi.eq27.gif 678件 [詳細] filels_arnoldi.eq16.gif 707件 [詳細] filels_arnoldi.eq23.gif 682件 [詳細] filels_arnoldi.eq8.gif 745件 [詳細] filels_arnoldi.eq3.gif 728件 [詳細] filels_arnoldi.eq31.gif 682件 [詳細] filels_arnoldi.eq18.gif 677件 [詳細] filels_arnoldi.eq4.gif 710件 [詳細] filels_arnoldi.eq9.gif 680件 [詳細] filels_arnoldi.eq15.gif 954件 [詳細] filels_arnoldi.eq32.gif 673件 [詳細] filels_arnoldi.eq25.gif 663件 [詳細] filels_arnoldi.eq33.gif 627件 [詳細] filels_arnoldi.eq6.gif 630件 [詳細] filels_arnoldi.eq13.gif 669件 [詳細] filels_arnoldi.eq17.gif 700件 [詳細] filels_arnoldi.eq19.gif 699件 [詳細] filels_arnoldi.eq14.gif 658件 [詳細] filels_arnoldi.eq1.gif 736件 [詳細] filels_arnoldi.eq29.gif 653件 [詳細] filels_arnoldi.eq26.gif 666件 [詳細] filels_arnoldi.eq20.gif 641件 [詳細] filels_arnoldi.eq10.gif 630件 [詳細] filels_arnoldi.eq22.gif 639件 [詳細] filels_arnoldi.eq7.gif 664件 [詳細] filels_arnoldi.eq21.gif 628件 [詳細] filels_arnoldi.eq24.gif 703件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-07-10 (火) 17:21:38 (3312d)