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$ を満たすような２つの基底である。

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

双ランチョス法は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\quad$ Do:
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]の次のような３重対角行列であるとすると、

$\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$ はアルゴリズムの中の３項間漸化式で導入したものと同一である。

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

$\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$

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

双直交性の証明

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

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

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

ということである。

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

証明

k=0のとき

$(\b{v}_1,\b{w}_1)=1$

k>0のとき

i=k+1,j=kのとき

$(\tilde{\b{v}}_{k+1},\b{w}_k)=(\b{A}\b{v}_k,\b{w}_k)-\alpha_k(\b{v}_k,\b{w}_k)-\beta_{k-1}(\b{v}_{k-1},\b{w}_k)=(\b{A}\b{v}_k,\b{w}_k)-\alpha_k=0$

i=k,j=k+1のとき

$(\tilde{\b{w}}_{k+1},\b{v}_k)=(\b{A}^T\b{w}_k,\b{v}_k)-\alpha_k(\b{w}_k,\b{v}_k)-\gamma_{k-1}(\b{w}_{k-1},\b{v}_k)=(\b{A}\b{w}_k,\b{v}_k)-\alpha_k=0$

i=k+1,j=k-1の時

$(\tilde{\b{v}}_{k+1},\b{w}_{k-1})=(\b{A}\b{v}_k,\b{w}_{k-1})-\alpha_k(\b{v}_k,\b{w}_{k-1})-\beta_{k-1}(\b{v}_{k-1},\b{w}_{k-1})=(\b{v}_k,\b{A}^T\b{w}_{k-1})-\beta_{k-1}=(\b{v}_k,\tilde{\b{w}}_{k-1})-\beta_{k-1}=0$

i=k-1,j=k+1の時

$(\tilde{\b{w}}_{k+1},\b{v}_{k-1})=0$

i=k+1,j<k-1の時

$(\tilde{\b{v}}_{k+1},\b{w}_j)=(\b{A}\b{v}_k,\b{w}_j)=(\b{v}_k,\b{A}^T\b{w}_j)=(\b{v}_k,\tilde{\b{w}}_{j+1})=0$

i<k-1,j=k+1の時

$(\tilde{\b{w}}_{k+1},\b{v}_j)=0$

よってk-1で成り立てば、kで成り立つことがわかった。以上より数学的帰納法から $k\ge0$ で成り立つことがわかる。

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

連立一次方程式の求解

ランチョス双直交化法で作られた２つのクリロフ部分空間の基底を使って連立一次方程式を解くことができる。連立一次方程式を解くやり方も双ランチョス法(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)$ を見つけるというものである。

ランチョス双直交化で得られた２つの基底を並べた行列を $\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$