×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

|TOP Page|


Arnoldi's Method

Arnoldi法




Last Update:2009年05月15日


概要

Arnoldi法はKrylov部分空間の正規直交規定を求める方法である。

QR法により非対称行列の固有値を求める時やGMRes法による連立一次方程式の求解に使われる。

基本的な手続き

Arnoldi法はGram-Shumitの直交化に従ってKrylov部分空間\cal{K}_kの正規直交基底v_1,v_2,\cdots,v_kを求める。

アルゴリズム(Gram-Shumit)

  1.   Chose a vector \b{v}_1 of norm 1
  2.   For j=1,\cdots,k\quad Do:
  3.      \b{w} = \b{A}\b{v}_j
  4.      For i=1,\cdots,j\quadDo:
  5.         h_{ij}=(\b{v}_i,\b{w})
  6.         \b{w}=\b{w}-h_{ij}\b{v}_i
  7.      End Do
  8.      h_{j+1,j}=||\b{w}||_2
  9.      If h_{j+1,j}=0 then Stop
10.      \b{v}_{j+1}=\b{w}/h_{j+1,j}
11.   End Do

3行目でj番目の基底を求めた後、4,5,6,7行目でGram-Shumitの直交化を行い、j番目の基底を1〜j-1番目の正規直交基底と直交させる。8,9,10行目で直交化させた基底を正規化している。

基本的な性質

Arnodi法のアルゴリズムから以下の式が成立つ。

A\b{v}_j=\(\sum_{i=1}^j \b{v}_ih_{ij}\)+\b{v}_{j+1}h_{j+1,j}  =  \sum_{i=1}^{j+1}\b{v}_ih_{ij}  =  \sum_{i=1}^{k+1}\b{v}_ih_{ij}

ここでh_{ij}=0 \quad for \quad i>j+1を用いた

ここで、行列\b{V}_kを行ベクトルが\b{v}_1,\b{v}_2,\cdots,\b{v}_kであるn \times kの行列であるとする。また、行列\bar{\b{{H}_k}はij成分がArnodi法のアルゴリズムの際のh_{ij}である、k+1 \times kの行列であるとする。すると、以下の式が成立つ。

\b{A}\b{V}_k=\b{V}_{k+1}\bar{\b{H}}_k=\b{V}_k\b{H}+\b{v}_{k+1} h_{k+1,k}\b{e}^T_k

ここで\b{e}_iは次のような単位ベクトルである。

\b{e}^T_i=(\overbrace{\underbrace{0,\ldots,0,1}_{i},0,\ldots,0}^k)

左から\b{V}^T_kをかけると、\b{V}^T_k\b{V}_k=\b{I},\b{V}^T_k\b{v}_{k+1}=0より

\b{V}^T_k\b{A}\b{V}_k=\b{H}

が成立つ。

実用上の手続き

グラムシュミット(Gram-Shumit)の直交化の代わりに修正グラムシュミット(Modefied Gram-Shumit)の直交化を用いると、数学的には結果は変化しないが、丸め誤差の影響が小さくすることができ、精度の高い直交化ができる。修正グラムシュミットの直交化を用いたArnoldi法のアルゴリズムは以下のとおり

アルゴリズム(修正Gram-Shumit)

  1.   Chose a vector \b{v}_1 of norm 1
  2.   For j=1,\cdots,k\quad Do:
  3.      \b{w} = \b{A}\b{v}_j
  4.      For i=1,\cdots,j\quadDo:
  5.         h_{ij}=(\b{v}_i,\b{w})
  6.         \b{w}=\b{w}-h_{ij}\b{v}_i
  7.      End Do
  8.      h_{j+1,j}=||\b{w}||_2
  9.      If h_{j+1,j}=0 then Stop
10.      \b{v}_{j+1}=\b{w}/h_{j+1,j}
11.   End Do

5行目において修正グラムシュミットのアルゴリズムはグラムシュミットのアルゴリズムと違って1からi-1番目の正規直行基底を取り除いたベクトル\b{w}に対して内積を計算している。

参考にしたもの

Books


Made by Nobuyuki UMETANI  梅谷 信行
n.umetani@gmail.com