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$ を求める。

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\quad$ Do:
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の直交化を行い、ｊ番目の基底を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$ の行列であるとする。すると、以下の式が成立つ。