Appendix¶

共役勾配法（Conjugate Gradient method）¶

著者: 簑島敬（JAMSTEC）

共役勾配法（Conjugate Gradient method, CG法）とは、 $n\times n$ 対称正定値行列 $A$ を係数とする $n$ 元連立一次方程式

(1)¶ $A {\bf x} = {\bf b}$

を解くためのアルゴリズムです。

式 (1) の解を、 $A$ に関して互いに共役 1 なベクトル ${\bf p_k}$ を用いて

(2)¶ ${\bf x} = \sum_{k=1}^{n}\alpha_{k} {\bf p_k}$

と展開し、 $\bf p_k$ と係数 $\alpha_k$ を逐次求めていくことで、解を探索します。

ある関数 $f({\bf x})$ を2次までのテイラー展開で近似します。

(3)¶ $f({\bf x}) &\sim f(0)+\sum_{i}\frac{\partial f}{\partial x_i}x_i+\frac{1}{2}\sum_{i,j}\frac{\partial^2 f}{\partial x_i \partial x_j}x_i x_j \\ &= f(0) - {\bf b} \cdot {\bf x} + \frac{1}{2} {\bf x} \cdot A {\bf x}$

式 (3) の近似では、 $f$ の勾配は

(4)¶ $\nabla f = A {\bf x} - {\bf b}$

となり、式 (1) の解を求めることは、 $f$ の極値(最小値)を求めることに相当します。

ある方向 $\bf p_k$ に沿って $f$ を最小化し、次に新しい方向 $\bf p_{k+1}$ に沿って $f$ を最小化する際に、 $\bf p_{k+1}$ を過去全ての $\bf p_k$ と $A$ に関して共役に選ぶと、新しい最小化の方向と過去の最小化による勾配の変化の方向との関係は

(5)¶ ${\bf p}_{k+1} \cdot \delta \left(\nabla f\right) = {\bf p_{k+1}} \cdot A {\bf p_k} = 0$

と垂直になるので、新しい最小化は過去の最小化に干渉しません。こうすることで、 $n$ 次の行列に対して高々 $n$ 回の計算で解を探索することが出来ます。

具体的なアルゴリズムは以下のようになります。

初期化。 $k=0$ , ${\bf x}_0 = 0$ , 残差 ${\bf r}_0 = {\bf b} - A{\bf x}_0$ , ${\bf p}_0 = {\bf r}_0$
$\alpha_k = \left({\bf r}_k \cdot {\bf r}_k\right) / \left({\bf p}_k \cdot A {\bf p}_k\right)$
${\bf x}_{k+1} = {\bf x}_{k} + \alpha_k {\bf p}_k$
${\bf r}_{k+1} = {\bf r}_{k} - \alpha_k A {\bf p}_k$
$|{\bf r}_{k+1}|$ が十分小さければ、 ${\bf x}_{k+1}$ は真の解に収束したとみなして、計算終了。
$\beta_k = \left({\bf r}_{k+1} \cdot {\bf r}_{k+1}\right) / \left({\bf r}_{k} \cdot {\bf r}_{k}\right)$
${\bf p}_{k+1} = {\bf r}_{k+1} + \beta_k {\bf p}_{k}$
$k=k+1$
1に戻る。