|TOP|

共役勾配法 (Conjugate gradient method)

概要
反復法による解の更新
実際の計算手順
修正方向ベクトルのAに関する共役性と残差ベクトルの直交性
最急降下法との比較

概要

共役勾配法は正値対称な連立一次方程式の反復解法として利用することができる。

連立一次方程式を以下のように表す。

$\displaystyle \displaystyle \bm{Ax}=\bm{b}$

(1)

ここで $\bm {A}$ はn×nの係数行列、 $\bm{x}$ は

次の変数ベクトル、 $\bm{b}$ は

次の定数ベクトルとする。共役勾配法では $\bm {A}$ が正値対称行列であることが必要である。

正値とは $\bm{0}$ 以外の任意のベクトル $\bm{v}$ に対して $\bm{v^{\rm {t}}Av}>0$ が成り立つことをいう。

対称行列は転置しても元の行列と等しい行列で、 $\bm{A}^{\rm {t}}=\bm{A}$ が成り立つ。

また式(1)は式(2)の $\bm{x}$ を変数とする凡関数 $F(\bm{x})$ の最小値問題として表現することができる。

$\displaystyle \displaystyle F(\bm{x})=\frac{1}{2}\bm{x^{\rm {t}}Ax}-\bm{x^{\rm {t}}b}$

(2)

式(2)の最小値は $\bm{x}$ で偏微分することで得られ、これは式(1)と一致する。

$\displaystyle \displaystyle \frac{\partial{F(\bm{x})}}{\partial{\bm{x}}} = \bm{Ax}-\bm{b}=0$

(3)

反復法による解の更新

式(1)の厳密解を $\bm{x}_{\rm {ans}}$ 、

回目の解の更新により得られた近似解を $\bm{x}_k$ とする。 $\bm{x}_k$ を式(1)に代入して得られる残差を $\bm{r}_k$ とすると、 $\bm{r}_k$ は以下のように表される。

$\displaystyle \displaystyle \bm{r}_k = \bm{Ax}_k - \bm{b}$

(4)

$\bm{x}_k$ からより厳密解に近い $\bm{x}_{k+1}$ を得ることを考える。 $\bm{x}_{k+1}$ を $\bm{x}_k$ を用いて、以下のように表す。

$\displaystyle \displaystyle \bm{x}_{k+1} = \bm{x}_k + {\Delta} \bm{x}$

(5)

式(2)から

$\displaystyle \displaystyle F({\bm{x}}_{k+1})= F(\bm{x_k+\Delta x})= F(\bm{x... ...bm{\Delta x^{\rm {t}}r_k} + \frac{1}{2}\bm{\Delta x_{k}^{\rm {t}}A \Delta x_k}$

(6)

次に $\Delta x$ を修正量 $\alpha_k$ と修正方向ベクトル $\bm{p}_k$ の積で表す。

$\displaystyle \displaystyle \bm{x}_{k+1} = \bm{x}_k + \alpha_k \bm{p}_k$

(7)

式(6)、式(7)から

$\displaystyle \displaystyle F({\bm{x}}_{k+1}) = F(\bm{x_k}) - \alpha_k\bm{p}_k^{\rm {t}} \bm{r}_k + \frac{1}{2} \alpha_k^2 \bm{p}_k^{\rm {t}}\bm{Ap}_k$

(8)

式(8)を $\alpha_k$ で偏微分し最小値をとる $\alpha_k$ を得る。

$\displaystyle \displaystyle - \bm{p}_k^{\rm {t}} \bm{r}_k + \alpha_k \bm{p}_k^{\rm {t}}\bm{Ap}_k = 0$

(9)

$\displaystyle \displaystyle \alpha_k = \frac{\bm{p}_k^{\rm {t}} \bm{r}_k}{\bm{p}_k^{\rm {t}} \bm{Ap}_k}$

(10)

次に $\bm{p}_{k+1}$ を求める必要がある。これには修正方向ベクトルの $\bm {A}$ に対する共役性が利用される。また修正方向ベクトルの $\bm {A}$ に対する共役性から残差ベクトルは直交性を持つ。これについては後で詳しく触れる。この二つの条件は以下のように表される。

$\displaystyle \displaystyle \bm{p}_i^{\rm {t}} \bm{Ap}_j = 0 \;(i\neq j)$

(11)

$\displaystyle \displaystyle \bm{r}_i^{\rm {t}} \bm{r}_j = 0 \;(i\neq j)$

(12)

$\bm{p}_{k+1}$ を $\bm{r}_{k+1}$ と $\bm{p}_{k}$ 、および $\beta_{k}$ を用いて表す。

$\displaystyle \displaystyle \bm{p}_{k+1} = \bm{r}_{k+1} + \beta_{k} \bm{p}_{k}$

(13)

式(13)に左側から $\bm{p}_{k}^{\rm {t}} \bm{A}$ をかけると次式が得られる。

$\displaystyle \displaystyle \bm{p}_{k}^{\rm {t}} \bm{A} \bm{p}_{k+1} = \bm{p}... ...m {t}} \bm{A} \bm{r}_{k+1} + \beta_{k} \bm{p}_{k}^{\rm {t}} \bm{A} \bm{p}_{k}$

(14)

$\bm{p}_{k}$ と $\bm{p}_{k+1}$ の $\bm {A}$ に関する共役性から $\beta_{k}$ が得られる。

$\displaystyle \displaystyle \beta_{k} = - \frac{\bm{p}_{k}^{\rm {t}} \bm{A} \bm{r}_{k+1}} {\bm{p}_{k}^{\rm {t}} \bm{A} \bm{p}_{k}}$

(15)

$\alpha_{k}$ と $\beta_{k}$ はさらに変形でき、以下のように表せる。

$\displaystyle \displaystyle \alpha_{k} = \frac{\bm{r}_k^{\rm {t}} \bm{r}_k} {\bm{p}_k^{\rm {t}} \bm{Ap}_k}$

(16)

$\displaystyle \displaystyle \beta_{k} = \frac{\bm{r}_{k+1}^{\rm {t}} \bm{r}_{k+1}} {\bm{r}_{k}^{\rm {t}} \bm{r}_{k}}$

(17)

実際の計算手順

実際の具体的な計算手順を示す。これは以下のようになる。

初期条件
- $\bm{x}_0=\bm{0}$
- $\bm{r}_0=\bm{b}$
- $\bm{p}_0=\bm{r}_0$
繰り返し計算
- $\alpha_{k} = \frac{\bm{r}_k^{\rm {t}} \bm{r}_k} {\bm{p}_k^{\rm {t}} \bm{Ap}_k}$
- $\bm{x}_{k+1} = \bm{x}_k + \alpha_k \bm{p}_k$
- $\bm{r}_{k+1} = \bm{r}_k - \alpha_k \bm{Ap}_k$
- もし残差が十分に小さければ繰り返し計算を終わる
- $\beta_k = \frac{\bm{r}_{k+1}^{\rm {t}} \bm{r}_{k+1}} {\bm{r}_k^{\rm {t}} \bm{r}_k}$
- $\bm{p}_{k+1} = \bm{r}_{k+1} + \beta_k \bm{p}_k$
繰り返し計算終わり

修正方向ベクトルのAに関する共役性と残差ベクトルの直交性

2では $\bm{p}_{k+1}$ を決定する際に $\bm{p}_{k}$ と $\bm {A}$ に関する共役性を持つように選んだ。これによって、残差ベクトルが直交性を持つことを示す。

式(4)、式(7)、式(10)から

$\displaystyle \displaystyle \bm{r}_{k+1} = \bm{r}_{k} - \frac {\bm{p}_{k}^{\rm {t}} \bm{r}_{k}} {\bm{p}_{k}^{\rm {t}} \bm{Ap}_{k}} \bm{Ap}_{k}$

(18)

これに左側から $\bm{p}_{k}^{\rm {t}}$ をかけると

$\displaystyle \displaystyle \bm{p}_{k}^{\rm {t}} \bm{r}_{k+1} = 0$

(19)

の関係が得られる。

また式(13)の関係から修正方向ベクトルは残差ベクトルの線形和であり、以下のように表現できる。

$\displaystyle \displaystyle \bm{p}_{k} = \bm{r}_{k} + \beta_{k-1} \bm{r}_{k-1... ..._{k-2} \bm{r}_{k-2} + \beta_{k-1} \beta_{k-2} \beta_{k-3} \bm{r}_{k-3} \cdots$

(20)

これに左側から $\bm{r}_{k+1}^{\rm {t}}$ をかけると式(19)が成り立つため式(12)の残差ベクトルの直交性が示される。また

$\displaystyle \displaystyle \bm{p}_{k}^{\rm {t}} \bm{r}_{k} = \bm{r}_{k}^{\rm {t}} \bm{r}_{k}$

(21)

$\displaystyle \displaystyle \bm{p}_{i}^{\rm {t}} \bm{r}_{j} = 0 \; (i < j)$

(22)

の関係が得られる。

次に式(11)が成り立つことを示す。式(18)に左側から $\bm{p}_{i}^{\rm {t}}\;(i<k-1)$ をかける。

$\displaystyle \displaystyle \bm{p}_{i}^{\rm {t}} \bm{r}_k = \bm{p}_{i}^{\rm {... ...-1}^{\rm {t}} \bm{Ap}_{k-1}} \bm{p}_{i}^{\rm {t}} \bm{Ap}_{k-1} \; (i < k-1)$

(23)

式(22)、式(23)から

$\displaystyle \displaystyle \bm{p}_{i}^{\rm {t}} \bm{Ap}_{j} = 0 \; (i < j)$

(24)

であり、また $\bm {A}$ が対称行列であることから式(11)も成り立つ。

最急降下法との比較

共役勾配法は最急降下法よりも効率がよい方法であることを示す。

最急降下法では修正方向ベクトルとして残差ベクトルが選ばれる。この関係を式(8)に代入すると以下の関係が得られる。

$\displaystyle \displaystyle F'(\bm{x}_{k+1}) = F(\bm{x}_k) - \frac{1}{2} \frac{(\bm{r}_k^{\rm {t}}\bm{r}_k)^2} {\bm{r}_k^{\rm {t}} \bm{Ar}_k}$

(25)

$\bm {A}$ が正値であることから

$\displaystyle \displaystyle \frac{1}{2} \frac{(\bm{r}_k^{\rm {t}}\bm{r}_k)^2} {\bm{r}_k^{\rm {t}} \bm{Ar}_k} > 0$

(26)

が成り立ち、 $F({\bm{x}}_{k+1}) < F(\bm{x_k})$ も成り立つため、最急降下法による解の更新によって厳密解に近づいたことが示される。

次にこれを共役勾配法と比較する。共役勾配法では修正方向ベクトルは式(13)によって計算される。式(8)から

$\displaystyle \displaystyle F({\bm{x}}_{k+1}) = F(\bm{x_k}) - \frac{1}{2} \frac{(\bm{r}_k^{\rm {t}}\bm{r}_k)^2} {\bm{p}_k^{\rm {t}} \bm{Ap}_k}$

(27)

である。式(25)と式(26)から ${\bm{r}_k^{\rm {t}} \bm{Ar}_k} > {\bm{p}_k^{\rm {t}} \bm{Ap}_k}$ が示されれば共役勾配法が最急降下法よりも効率がよい方法だといえる。

式(13)から

$\displaystyle \displaystyle \bm{p}_k^{\rm {t}} \bm{Ap}_k = \bm{r}_k^{\rm {t}}... ...{k-1}^{\rm {t}} \bm{Ar}_k + \beta_{k-1}^2 \bm{p}_{k-1}^{\rm {t}} \bm{Ap}_{k-1}$

(28)

これは式(15)から

$\displaystyle \displaystyle \bm{p}_k^{\rm {t}} \bm{Ap}_k = \bm{r}_k^{\rm {t}}... ... {(\bm{p}_{k-1}^{\rm {t}} \bm{Ar}_k)^2} {\bm{p}_{k-1}^{\rm {t}} \bm{Ap}_{k-1}}$

(29)

これと、が正値であることから

$\displaystyle \displaystyle \bm{r}_k^{\rm {t}} \bm{Ar}_k > \bm{p}_k^{\rm {t}} \bm{Ap}_k$

(30)

が成り立ち、共役勾配法の解の更新によって、最急降下法よりも厳密解に近い解が得られ、効率がよい方法だといえる。