Lanczos法を非対称行列に対応させる方法とそれによる 双共役勾配法のアルゴリズムについて説明する.



Lanczos双直交化

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

Lanczos双直交化では,以下の2つのKrylov部分空間の正規直交基底を求めていく.

ls_bicg1_bi-lanczos.eq4.gif
ls_bicg1_bi-lanczos.eq5.gif

双直交なls_bicg1_bi-lanczos.eq6.gifls_bicg1_bi-lanczos.eq7.gifのKrylov部分空間の基底ならば,ls_bicg1_bi-lanczos.eq8.gifを満たす.

Lanzcos法のアルゴリズムより,以下の3項漸化式(three-term recurrence formula)が成り立つ.

ls_bicg1_bi-lanczos.eq9.gif

ls_bicg1_bi-lanczos.eq10.gifについても同様に,

ls_bicg1_bi-lanczos.eq11.gif

ここで,ls_bicg1_bi-lanczos.eq12.gifであり, ls_bicg1_bi-lanczos.eq13.gifls_bicg1_bi-lanczos.eq14.gifを正規化するためのパラメータである.

ls_bicg1_bi-lanczos.eq15.gif

双直交化するために,ls_bicg1_bi-lanczos.eq16.gifとなるようにls_bicg1_bi-lanczos.eq13.gifを定める. つまり,

ls_bicg1_bi-lanczos.eq17.gif

となる.この条件を満たす限り,ls_bicg1_bi-lanczos.eq13.gifはどのように定めてもよい. ここでは,

ls_bicg1_bi-lanczos.eq18.gif

とする.また,この定義から以下も成り立つ.

ls_bicg1_bi-lanczos.eq19.gif

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

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

得られたls_bicg1_bi-lanczos.eq31.gifからなる行列

ls_bicg1_bi-lanczos.eq32.gif

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

ls_bicg1_bi-lanczos.eq35.gif

3項漸化式より,

ls_bicg1_bi-lanczos.eq36.gif

ls_bicg1_bi-lanczos.eq37.gifを使って,ls_bicg1_bi-lanczos.eq38.gifにまとめると以下となる.

ls_bicg1_bi-lanczos.eq39.gif

この式から,

ls_bicg1_bi-lanczos.eq40.gif

双直交性からls_bicg1_bi-lanczos.eq41.gifなので,

ls_bicg1_bi-lanczos.eq42.gif

Lanczos双直交化による線形システムの解法

Lanczos双直交化法で線形システムls_bicg2_bi-lanczos_ls.eq1.gifを解く.ここで,Aはls_bicg2_bi-lanczos_ls.eq2.gifの非対称行列である. 基本的な手順はLanczos法を同じである.

ls_bicg2_bi-lanczos_ls.eq3.gifを計算
ベクトルls_bicg2_bi-lanczos_ls.eq4.gifls_bicg2_bi-lanczos_ls.eq5.gifとなるようなls_bicg2_bi-lanczos_ls.eq6.gifを設定
ls_bicg2_bi-lanczos_ls.eq7.gifを設定
for(j = 1,2,...,m){
  ls_bicg2_bi-lanczos_ls.eq8.gif
  ls_bicg2_bi-lanczos_ls.eq9.gif
  ls_bicg2_bi-lanczos_ls.eq10.gif
  ls_bicg2_bi-lanczos_ls.eq11.gif
  if(ls_bicg2_bi-lanczos_ls.eq12.gif) 反復終了
  ls_bicg2_bi-lanczos_ls.eq13.gif
  ls_bicg2_bi-lanczos_ls.eq14.gif
  ls_bicg2_bi-lanczos_ls.eq15.gif
}
ls_bicg2_bi-lanczos_ls.eq16.gif
ls_bicg2_bi-lanczos_ls.eq17.gif
ls_bicg2_bi-lanczos_ls.eq18.gif

双共役勾配法

Lanzcos法から共役勾配法のアルゴリズムを導出したのと同じような方法で, 双直交版のLanzcos法から双共役勾配法(Bi-Conjugate Gradient method : BiCG法)が導かれる.

双共役勾配法は,

ls_bicg3.eq1.gif

としたProjection法となる. ここで,ls_bicg3.eq2.gifである.

Direct版のLanczos法を使ってCG法のアルゴリズムを導いたのと同じように, 双直交版のLanczos法のls_bicg3.eq3.gifをLU分解し(ls_bicg3.eq4.gif),以下のようにls_bicg3.eq5.gifを定義する.

ls_bicg3.eq6.gif

よって,近似解は,

ls_bicg3.eq7.gif

ここから,ls_bicg3.eq8.gifからls_bicg3.eq9.gifを求める. ls_bicg3.eq10.gifとその共役ls_bicg3.eq11.gifをそれぞれls_bicg3.eq12.gifのスカラー倍とすると,

ls_bicg3.eq13.gif

また,ls_bicg3.eq14.gifとすると,

ls_bicg3.eq15.gif

であるので,ls_bicg3.eq16.gifls_bicg3.eq17.gifの列ベクトルについて,A-共役が成り立つ. つまり,

ls_bicg3.eq18.gif

共役勾配法と同様にすると以下の双共役勾配法のアルゴリズムが得られる.

初期近似解ls_bicg3.eq19.gifを適当に設定
残差ベクトルls_bicg3.eq20.gifを計算し, ls_bicg3.eq21.gifである共役残差ベクトルls_bicg3.eq22.gifを設定
ls_bicg3.eq23.gifを設定
for(j = 0,1,...){
  ls_bicg3.eq24.gif
  ls_bicg3.eq25.gif
  ls_bicg3.eq26.gif
  ls_bicg3.eq27.gif
  if(収束判定) 反復終了
  ls_bicg3.eq28.gif
  ls_bicg3.eq29.gif
  ls_bicg3.eq30.gif
}

参考文献

  • Yousef Saad, Iterative methods for sparse linear systems 2nd ed., SIAM, 2003.

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-07-13 (金) 15:33:15 (3196d)