Biconjugate Gradient (BiCG)

双共役勾配法

Last Update:2009年05月15日

概要

Biconjugate Gradient法(BiCG法)は非対称行列に対してCG法のようなアルゴリズムを適応した連立一次方程式の反復解法の一つである。

このアルゴリズムは始めLanczosによって1952年に今と違った形(CG法に似た形）で提案された後、Fletcherによって1974年に、この方法が $\b{A}\b{x}=\b{b}$ を解くだけでなく、双対連立一次方程式 $\b{A}^T\b{x}^*_0=\b{b}^*$ についても陰的に解いていることが示された。*1

クリロフ部分空間 $\cal{K}_k=span\{\b{r}_0,\b{A}\b{r}_0,\ldots,\b{A}^{k-1}\b{r}_0\}$ とする。

CG法では、回目の反復において残差 $\b{r}_k$ が部分空間 $\b{x}_0+\cal{K}_k$ に直交するように解 $\b{x}_k$ を $\b{x}_0+\cal{K}_k$ の中から選んだ。つまり、

$\b{r}_k\quad\bot\quad\cal{K}_k \qquad \qquad \b{x}_k\in\b{x}_0+\cal{K}_k$

BiCG法では $\cal{K}_k$ とは別に次のような部分空間 $\ca{L}_k=span\{\b{r}^*_0,{\b{A}}^T\b{r}^*_0,\ldots,({\b{A}}^T)^{k-1}\b{r}^*_0\}$ を考える。BiCG法では残差 $\b{r}_k$ が部分空間 $\cal{L}_k$ と直交するように解 $\b{x}_k$ を部分空間 $\b{x}_0+\cal{K}_k$ からみつける方法である。つまり、

$find \quad \b{x}_k\in\b{x}_0+\cal{K}_k \qquad so \quad that \qquad \qquad \b{r}_k\quad\bot\quad\cal{L}_k$

CG法と違って上のように解 $\b{x}_k$ を選ぶことは何らかのノルムを最小化するものではなく収束については容易に予測できない。しかしながら、部分空間 $\cal{L}$ が十分大きければそれに直交するために残差が小さくなり、 $\b{x}_k$ は解 $\b{x}$ に収束していくものと考えられる。

BiCGはクリロフ部分空間の正規直交基底に双直交な基底を作る方法であるTwo-Sided Lanczos法と深い関係にある。これはCG法におけるLanczos法の関係と同じである。

基本的な手続き

回目の反復において残差 $\b{r}_{k+1}$ が次の関係を満たすようにパラメータ $\alpha_k$ を用いて解の更新ベクトルをスケーリングする。

$(\b{r}^*_k,\b{r}_{k+1})=0$

また、 $(\b{p}^*_k,\b{A}\b{p}_{k+1})=0$ を満たすように $\beta_k$ を決定する。

アルゴリズム(BiCG)

1.   Compute $\b{r}_0=\b{b}-\b{A}\b{x}_0$ , Choose $\b{r}^*_0$ $\quad such \quad that$ $(\b{r}_0,\b{r}^*_0)\ne0$
2.   Set , $\b{p}_0=\b{r}_0$ , $\b{p}^*_0=\b{r}^*_0$
3.   For $k=0,1,\ldots,m\quad$ Do:
4.      $\alpha_k=\frac{(\b{r}_k,\b{r}^*_k)}{(\b{A}\b{p}_k,\b{p}^*_k)}$
5.      $\b{x}_{k+1}=\b{x}_k+\alpha_k\b{p}_k$
6.      $\b{r}_{k+1}=\b{r}_k-\alpha_k\b{A}\b{p}_k$
7.      $\b{r}^*_{k+1}=\b{r}^*_k-\alpha_k\b{A}^T\b{p}^*_k$
8.      $\beta_k=\frac{(\b{r}_{k+1},\b{r}^*_{k+1})}{(\b{r}_k,\b{r}^*_k)}$
9.      $\b{p}_{k+1}=\b{r}_{k+1}+\beta_k\b{p}_k$
10.     $\b{p}^*_{k+1}=\b{r}^*_{k+1}+\beta_k\b{p}^*_k$
11. $End \quad Do$