×

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

|TOP Page|


Two-Sided Lanczos Method

双ランチョス法、ランチョス双直交化法




Last Update:2009年05月15日


概要

双ランチョス法(Two-Sided Lanczos Method)はランチョス双直交化(Lanczos Biorthogonalization)とも呼ばれる

\b{A}を非対称行列とすると、双ランチョス法は非対称行列のために双直交な\b{A}\b{A}^Tのクリロフ部分空間の基底を作成する方法である。

ここで、クリロフ部分空間span\{\b{v},\b{B}\b{v},\ldots,\b{B}^{k-1}\b{v}\}\cal{K}_k(\b{B},\b{v})と表すとする。\b{A}のクリロフ部分空間の基底を\b{v}_1,\ldots,\b{v}_k\in\cal{K}_k(\b{A},\b{v}_1)\b{A}^Tのクリロフ部分空間の基底を\b{w}_1,\ldots,\b{w}_k\in\cal{K}_k(\b{A}^T,\b{w}_1)とすると、双直交な\b{A}\b{A}^Tのクリロフ部分空間の基底とは、(\b{v}_i,\b{w}_j)=0 \quad for \quad i \ne j を満たすような2つの基底である。

対称行列はLanczos法を用いることで、3項間漸化式を作ることによって正規直交基底を作ることができた。同様に双ランチョス法では、\b{A}\b{A}^Tに対する2つの基底に対してそれぞれ3項間漸化式を作ることで逐次的に新しい基底を求める。

双ランチョス法はBiCG法などの方法に応用される。

基本的な手続き

双ランチョス法では次のようにして双直交なクリロフ部分空間の基底を求める。

アルゴリズム

  1.   Chose two vectors \b{v}_1,\b{w}_1 such that (\b{v}_1,\b{w}_1)=1
  2.   Set \beta_1=\delta_1\eq0, \b{\omega}_0=\b{v}_0\eq0
  3.   For j=1,2,\ldots,m\quadDo:
  4.      \alpha_i=(A\b{v}_j,\b{w}_j)
  5.      \tilde{\b{v}}_{j+1}=\b{A}\b{v}_j-\alpha_j\b{v}_j-\beta_j\b{v}_{j-1}
  6.      \tilde{\b{w}}_{j+1}=\b{A}^T\b{w}_j-\alpha_j\b{w}_j-\delta_j\b{w}_{j-1}
  7.      \delta_j=||\tilde{\b{v}}_{j+1}||\qquad If \delta_j=0 Stop
  8.      \b{v}_{j+1}=\tilde{\b{v}}_{j+1}/\delta_j
  9.      \beta_j=(\b{v}_{j+1},\tilde{\b{w}}_{j+1})\quad And \quad\b{w}_{j+1}=\tilde{\b{w}}_{j+1}/\beta_j
  10.  End Do

手順7,8,9では、三項間漸化式によって得られた新しい基底\tilde{\b{v}}_{j+1}\tilde{\b{w}}_{j+1}に対して、||\b{v}_{j+1}||=1(\b{v}_{j+1},\b{w}_{j+1})=1が成り立つようにスケーリングしてある。このスケーリングの仕方は\delta_j\beta_j=(\tilde{\b{v}}_{j+1},\tilde{\b{w}}_{j+1})の関係さえ満たせばどのように選んでも双直交な基底が得られるが、このように||\b{v}_{j+1}||=1(\b{v}_{j+1},\b{w}_{j+1})=1が成り立つようにスケーリングすると、後々の議論に大変便利である。これ以降ではこのスケーリングを用いるものとする。

行列による表示

\b{V}_kは行ベクトルが基底\b{v}_1,\ldots,\b{v}_kである行列であるとし、\b{W}_kは行ベクトルが基底\b{w}_1,\ldots,\b{w}_kである行列であるとする。

基底の双直交性は次のようにあらわされる。

\b{W}_k^T\b{V}_k=\b{I}

ここで、\b{T}_kは大きさが[k,k]の次のような3重対角行列であるとすると、

\b{T}_k=\(\begin{array}							\alpha_1 && \beta_1 && && \\ 							\gamma_1 && \ddots  && \ddots &&          \\					         && \ddots  && \ddots && \beta_{k-1} \\						 &&	    && \gamma_{k-1} && \alpha_k \end{array}\)

但し、ここでの係数\alpha,\beta,\gammaはアルゴリズムの中の3項間漸化式で導入したものと同一である。

三項漸化式の関係から明らかに以下が成り立つ。

\b{A}\b{V}_k=\b{V}_k\b{T}_k+\gamma_{k+1}\b{v}_{k+1}\b{e}^T_k

\b{A}^T\b{W}_k=\b{W}_k\b{T}^T_k+\beta_{k+1}\b{\omega}_{k+1}\b{e}^T_k

また上式から

\b{W}^T_k\b{A}\b{V}_k=\b{T}_k

が成り立つ。この関係式は固有値を求める時や連立一次方程式を解く時などに使う

双直交性の証明

ここで、この双ランチョス法の手続きによって得られる、2つの基底\b{v}_1,\ldots,\b{v}_k\b{w}_1,\ldots,\b{w}_kが双直交であることを証明する。

この2つの基底が双直交であるというのは、

(\b{v}_i,\b{w}_j)=0 \qquad for \quad i \ne j, \quad i,j\le k+1

ということである。

以下帰納法を使って証明する。

証明

****************

連立一次方程式の求解

ランチョス双直交化法で作られた2つのクリロフ部分空間の基底を使って連立一次方程式を解くことができる。連立一次方程式を解くやり方も双ランチョス法(Two-Sided Lanczos Method)と呼ばれているようである。双ランチョス法で連立一次方程式を解くやり方はBiCG法と深い関係がある。

k反復目の解を\b{x}_k、残差を\b{r}_kとすると、双ランチョス法で連立一次方程式を解くやり方は、残差がクリロフ部分空間\cal{K}_k(\b{A}^T,\b{r}_0)と直交するような解をクリロフ部分空間\cal{K}_k(\b{A},\b{r}_0)の中から探すという方法である。つまり、\b{r}_k \bot \cal{K}_k(\b{A}^T,\hat{\b{r}}_0) となるように、\b{e}_k=\b{x}_k-\b{x}_0\in\cal{K}_k(\b{A},\b{r}_0)を見つけるというものである。

ランチョス双直交化で得られた2つの基底を並べた行列を\b{V}_k\b{W}_kとすると、これらは次のように書き換えることができる。

\b{r}_k \bot \cal{K}_k(\b{A}^T,\b{r}_0) \quad \right \quad \b{W}^T_k\b{r}_k=0 \quad \right \quad \b{W}^T(\b{A}\b{x}_k-\b{b})=0 \quad \right \quad \b{W}^T_k\{\b{A}(\b{x}_k-\b{x}_0)+\b{A}\b{x}_0-\b{b}\}=0 \\ 				\qquad \qquad \qquad \qquad \right \quad \b{W}^T\b{A}\b{e}_k=\b{W}^T\b{r}_0= \quad \right \quad \b{W}^T\b{A}\b{e}_k=\beta\b{\xi}_1

ここで、\beta|\b{r}_0|である。また、

\b{e}_k=\b{x}_k-\b{x}_0\in\cal{K}_k(\b{A},\b{r}_0) \quad \right \quad \b{e}_k=\b{V}_k\b{y}_k \quad \right \quad \b{x}_k = \b{V}_k\b{y}_k+\b{x}_0

とかける、ここで、ベクトル\b{y}_kk次元のベクトルである。

これらを合わせると次のようになる。

\b{W}_k^T\b{A}\b{V}_k\b{y}_k=\b{T}_k\b{y}_k=\beta\b{\xi}_1

これを解くことで\b{y}_kを求め、\b{x}_k = \b{V}_k\b{y}_k+\b{x}_0によって解を求めることができる。

\b{T}_kは3重対角行列なので、\b{T}_kのLU分解は容易に計算できる。また、この性質を生かしてクリロフ部分空間の全ての基底\b{V}_kを保存しておかなくても、前回の反復における解の更新から、次の反復における解の更新を求めることができる。

BiCG法はこの方法の一種であるが\b{T}について解く必要がなく、簡単なので一般的によく使われている。

参考にしたもの

Books


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