アーノルディ法(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 562件 [詳細] filels_arnoldi.eq11.gif 576件 [詳細] filels_arnoldi.eq28.gif 564件 [詳細] filels_arnoldi.eq5.gif 572件 [詳細] filels_arnoldi.eq2.gif 616件 [詳細] filels_arnoldi.eq12.gif 539件 [詳細] filels_arnoldi.eq27.gif 573件 [詳細] filels_arnoldi.eq16.gif 606件 [詳細] filels_arnoldi.eq23.gif 578件 [詳細] filels_arnoldi.eq8.gif 638件 [詳細] filels_arnoldi.eq3.gif 619件 [詳細] filels_arnoldi.eq31.gif 574件 [詳細] filels_arnoldi.eq18.gif 574件 [詳細] filels_arnoldi.eq4.gif 560件 [詳細] filels_arnoldi.eq9.gif 572件 [詳細] filels_arnoldi.eq15.gif 806件 [詳細] filels_arnoldi.eq32.gif 567件 [詳細] filels_arnoldi.eq25.gif 566件 [詳細] filels_arnoldi.eq33.gif 523件 [詳細] filels_arnoldi.eq6.gif 530件 [詳細] filels_arnoldi.eq13.gif 570件 [詳細] filels_arnoldi.eq17.gif 615件 [詳細] filels_arnoldi.eq19.gif 618件 [詳細] filels_arnoldi.eq14.gif 573件 [詳細] filels_arnoldi.eq1.gif 606件 [詳細] filels_arnoldi.eq29.gif 566件 [詳細] filels_arnoldi.eq26.gif 587件 [詳細] filels_arnoldi.eq20.gif 531件 [詳細] filels_arnoldi.eq10.gif 551件 [詳細] filels_arnoldi.eq22.gif 551件 [詳細] filels_arnoldi.eq7.gif 543件 [詳細] filels_arnoldi.eq21.gif 544件 [詳細] filels_arnoldi.eq24.gif 611件 [詳細]

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