連立1次方程式：双共役勾配法

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

---

---

Lanczos双直交化†

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

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

双直交なとのKrylov部分空間の基底ならば，を満たす．

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

についても同様に，

ここで，であり， はを正規化するためのパラメータである．

双直交化するために，となるようにを定める． つまり，

となる．この条件を満たす限り，はどのように定めてもよい． ここでは，

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

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

任意のベクトルを設定(ただし)
を設定
for(j = 1,2,...,m){
　　
　　
　　
　　
　　if() 反復終了
　　
　　
　　
}

得られたからなる行列

を考える．双直交系なので，である． 今，アルゴリズム中のを使って以下の三重対角行列を定義する．

3項漸化式より，

を使って，にまとめると以下となる．

この式から，

双直交性からなので，

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

Lanczos双直交化法で線形システムを解く．ここで，Aはの非対称行列である． 基本的な手順はLanczos法を同じである．

を計算
ベクトルととなるようなを設定
を設定
for(j = 1,2,...,m){
　　
　　
　　
　　
　　if() 反復終了
　　
　　
　　
}

双共役勾配法†

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

双共役勾配法は，

としたProjection法となる． ここで，である．

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

よって，近似解は，

ここから，からを求める． とその共役をそれぞれのスカラー倍とすると，

また，とすると，

であるので，との列ベクトルについて，A-共役が成り立つ． つまり，

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

初期近似解を適当に設定
残差ベクトルを計算し， である共役残差ベクトルを設定
を設定
for(j = 0,1,...){
　　
　　
　　
　　
　　if(収束判定) 反復終了
　　
　　
　　
}

参考文献†

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