[[連立1次方程式:双共役勾配法]]
Lanczos法は対称行列に限定した,Krylov部分空間における正規直交基底を求める方法であったが,
これを非対称行列に対応させた拡張をLanczos双直交化(Lanczos Biorthogonalization or Two-sided Lanczos method),
非対応行列の正規直交基底を求めるのならばArnoldi法になるのではないかと思うが,
そうではなく,双直交系(biorthogonal system)に基づく方法で,Arnoldiとは異なる.
ちなみに 双直交系とは,2つのベクトル空間のそれぞれの直交基底&ref(ls_bicg1_bi-lanczos.eq1.gif,nolink,70%);が
&ref(ls_bicg1_bi-lanczos.eq2.gif,nolink,70%);となるような系である(&ref(ls_bicg1_bi-lanczos.eq3.gif,nolink,70%);はクロネッカーのデルタでi=jで1,それ以外で0となる).

Lanczos双直交化では,以下の2つのKrylov部分空間の正規直交基底を求めていく.
#ref(ls_bicg1_bi-lanczos.eq4.gif,nolink,70%)

#ref(ls_bicg1_bi-lanczos.eq5.gif,nolink,70%)

双直交な&ref(ls_bicg1_bi-lanczos.eq6.gif,nolink,70%);と&ref(ls_bicg1_bi-lanczos.eq7.gif,nolink,70%);のKrylov部分空間の基底ならば,&ref(ls_bicg1_bi-lanczos.eq8.gif,nolink,70%);を満たす.

Lanzcos法のアルゴリズムより,以下の3項漸化式(three-term recurrence formula)が成り立つ.
#ref(ls_bicg1_bi-lanczos.eq9.gif,nolink,70%)

&ref(ls_bicg1_bi-lanczos.eq10.gif,nolink,70%);についても同様に,
#ref(ls_bicg1_bi-lanczos.eq11.gif,nolink,70%)

ここで,&ref(ls_bicg1_bi-lanczos.eq12.gif,nolink,70%);であり,
&ref(ls_bicg1_bi-lanczos.eq13.gif,nolink,70%);は&ref(ls_bicg1_bi-lanczos.eq14.gif,nolink,70%);を正規化するためのパラメータである.
#ref(ls_bicg1_bi-lanczos.eq15.gif,nolink,70%)

双直交化するために,&ref(ls_bicg1_bi-lanczos.eq16.gif,nolink,70%);となるように&ref(ls_bicg1_bi-lanczos.eq13.gif,nolink,70%);を定める.
つまり,
#ref(ls_bicg1_bi-lanczos.eq17.gif,nolink,70%)

となる.この条件を満たす限り,&ref(ls_bicg1_bi-lanczos.eq13.gif,nolink,70%);はどのように定めてもよい.
ここでは,
#ref(ls_bicg1_bi-lanczos.eq18.gif,nolink,70%)

とする.また,この定義から以下も成り立つ.
#ref(ls_bicg1_bi-lanczos.eq19.gif,nolink,70%)


これらの式を用いたLanczos双直交化のアルゴリズムは以下となる.

>
任意のベクトル&ref(ls_bicg1_bi-lanczos.eq20.gif,nolink,70%);を設定(ただし&ref(ls_bicg1_bi-lanczos.eq21.gif,nolink,70%);)~
&ref(ls_bicg1_bi-lanczos.eq22.gif,nolink,70%);を設定~
for(j = 1,2,...,m){~
  &ref(ls_bicg1_bi-lanczos.eq23.gif,nolink,70%);~
  &ref(ls_bicg1_bi-lanczos.eq24.gif,nolink,70%);~
  &ref(ls_bicg1_bi-lanczos.eq25.gif,nolink,70%);~
  &ref(ls_bicg1_bi-lanczos.eq26.gif,nolink,70%);~
  if(&ref(ls_bicg1_bi-lanczos.eq27.gif,nolink,70%);) 反復終了~
  &ref(ls_bicg1_bi-lanczos.eq28.gif,nolink,70%);~
  &ref(ls_bicg1_bi-lanczos.eq29.gif,nolink,70%);~
  &ref(ls_bicg1_bi-lanczos.eq30.gif,nolink,70%);~
}


得られた&ref(ls_bicg1_bi-lanczos.eq31.gif,nolink,70%);からなる行列
#ref(ls_bicg1_bi-lanczos.eq32.gif,nolink,70%)

を考える.双直交系なので,&ref(ls_bicg1_bi-lanczos.eq33.gif,nolink,70%);である.
今,アルゴリズム中の&ref(ls_bicg1_bi-lanczos.eq34.gif,nolink,70%);を使って以下の三重対角行列を定義する.
#ref(ls_bicg1_bi-lanczos.eq35.gif,nolink,70%)

3項漸化式より,
#ref(ls_bicg1_bi-lanczos.eq36.gif,nolink,70%)

&ref(ls_bicg1_bi-lanczos.eq37.gif,nolink,70%);を使って,&ref(ls_bicg1_bi-lanczos.eq38.gif,nolink,70%);にまとめると以下となる.
#ref(ls_bicg1_bi-lanczos.eq39.gif,nolink,70%)

この式から,
#ref(ls_bicg1_bi-lanczos.eq40.gif,nolink,70%)

双直交性から&ref(ls_bicg1_bi-lanczos.eq41.gif,nolink,70%);なので,
#ref(ls_bicg1_bi-lanczos.eq42.gif,nolink,70%)



トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS