1 共役勾配法

1.1 固有値問題

一般化固有値問題は、以下の形で与えられる。

$$\boldsymbol{A}\boldsymbol{x} = \lambda \boldsymbol{B}\boldsymbol{x}$$ (1)

共役勾配法ではこのような固有値問題の最小固有値を求められる。

$\lambda$は，Raylaigh商から求められる．

$$\lambda = \frac{(\boldsymbol{x},\boldsymbol{Ax})}{(\boldsymbol{x},\boldsymbol{Bx})}$$ (2)

1.2 計算法

最急勾配方向¹ $\boldsymbol{g}(\boldsymbol{x})$を以下に示す．

$$\boldsymbol{g}(\boldsymbol{x}) = \frac{2(\boldsymbol{Ax} - \lambda \boldsymbol{Bx})}{(\boldsymbol{x},\boldsymbol{Bx})}$$ (3)

固有ベクトルは以下のように反復法で求められる．

$$\boldsymbol{x}_{i+1} = \boldsymbol{x}_i + \alpha_i \boldsymbol{p}_i$$ (4)

$$\boldsymbol{p}_ {i+1}= -\boldsymbol{g}_{i+1} + \beta _{i} \boldsy... ...bol{g}_{i+1}, \boldsymbol{g}_{i+1})} {(\boldsymbol{g}_{i}, \boldsymbol{g}_{i})}$$ (5)

ただし， $\boldsymbol{x}_0$をランダム関数などを使って適当に決め， $\boldsymbol{p}_0 = -\boldsymbol{g}_0$ として， $\boldsymbol{x}_1$から計算し始める．

ここで，$\alpha_i$を求めなくてはいけないが，これは$\lambda$が最小になる ように選べばいいので，

$$\frac{\partial \lambda}{\partial \alpha} = 0$$ (6)

すなわち，

$$\frac{\partial }{\partial \alpha_i} \left( \frac{(\boldsymbol{x}_... ..._i, \boldsymbol{B}[\boldsymbol{x}_i + \alpha_i \boldsymbol{p}_i] )} \right) = 0$$ (7)

となるように$\alpha_i$を決める．ここで，これを計算すると，

$$\alpha = \frac{B_{pp}\,A_{xx} - A_{pp}\,B_{xx} \pm {\sqrt{{\left(... ...right) }}}{2\, \left( -\left( A_{px}\,B_{pp} \right) + A_{pp}\,B_{px} \right) }$$ (8)

ただし，

$$(\boldsymbol{x},\boldsymbol{Ax}) = A_{xx} (\boldsymbol{p},\boldsymbol{Ax}) = A_{px} (\boldsymbol{p},\boldsymbol{Ap}) (\boldsymbol{x},\boldsymbol{Bx}) = B_{xx} (\boldsymbol{p},\boldsymbol{Bx}) = B_{px} (\boldsymbol{p},\boldsymbol{Bp}) = B_{pp}$$

と置いた． ここで，$\alpha$は２つでてきたが，実際は$\pm$のところを$+$にする． つまり，

$$\alpha = \frac{B_{pp} A_{xx} - A_{pp} B_{xx} + {\sqrt{{\left( B... ...right) }}}{2 \left( -\left( A_{px} B_{pp} \right) + A_{pp} B_{px} \right) }$$ (9)

である．

ここで，手順をまとめると次のようになる．

1. $\boldsymbol{x}_0$をランダム関数などを使い，適当に決める．
2. $\boldsymbol{p}_0 = -\boldsymbol{g}_0$とする．
3. $i=0$
4. $\boldsymbol{x}_{i+1} = \boldsymbol{x}_i + \alpha_{i} \boldsymbol{p}_i$
5. $\boldsymbol{p}_ {i+1}= -\boldsymbol{g}_{i+1} + \beta _{i} \boldsymbol{p}_{i}$
6. 収束判定をして，収束が十分でなければ$i=i+1$として，４に戻る．

これで，最小の固有値と固有ベクトルが求められる．

ホームページ: Yamamoto's laboratory
著者: 夏井拓也