数値解析 第14回 (3) デフレーション

デフレーション ( deflation )

 Alg.6 では最大固有値とそれに対する固有ベクトルしか求められませんが、 「デフレーション ( deflation )」という処理により、 2番目、3番目 $\cdots$ に絶対値の大きい固有値についても固有値・固有ベクトルを求めることができるようになります。
Lemma 7 Th.5 の状況下、 次のアルゴリズムによって行列 $B$ を 作ると、
$\dps{ \left\{ \begin{array}{l} B\,\vvv_1=\ooo =0\,\vvv_1\\ B\,\vvv_j=\lambda_j\vvv_j \quad (\ \forall\,j \geqq 2\ ) \\ \end{array} \right. }$
が成り立つ。すなわち $B$ の固有値・固有ベクトルは
$(\require{color}\textcolor{red}{0},\vvv_1)$,  $(\lambda_2,\vvv_2)$,  $\cdots$,  $(\lambda_n,\vvv_n)$
となる。
Algorithm 8 ( デフレーション )
  1. $A$ の最大固有値とそれに対する固有ベクトルを $(\lambda_1,\vvv_1)$ とする
  2. ${}^tA$ にも Alg.6 を適用して、${}^tA$ の $\lambda_1$ に対する固有ベクトル $\www$ を求める
  3. $\dps{\uuu=\frac{1}{{}^t\www\,\vvv_1}\www}$ とおく
  4. $B=A-\lambda_1\vvv_1{}^t\uuu$ とおく
 ただし ${}^t\vvv$ や ${}^tA$ は転置を表す記号です。たとえば
$\dps{{}^t\mat{c}{1 \\ 2} = (1\ \ 2)}$,  $\dps{{}^t\mat{cc}{1 & 2 \\ 3 & 4} = \mat{cc}{1 & 3 \\ 2 & 4}}$
であり、「積の転置は、転置を逆に掛けたもの」という性質があります:
${}^t(AB)=({}^tB)({}^tA)$,  ${}^t(A\vvv)=({}^t\vvv)({}^tA)$  etc.
( 「$t$ 乗」と間違わないように左肩に書く人が多いです。)

 また Alg.8 では次のことに注意してください。
  1. ${}^tA$ と $A$ は同じ固有値を持ちます。
    ( $\det(xE-A)=\det{}^t(xE-A)=\det(xE-{}^tA)$ ゆえ。)
  2. ${}^t\www\,\vvv_1$ はスカラーです。
  3. $\vvv_1{}^t\uuu$ は $n$ 次行列です。
Th.9 $n$ 次行列 $A$ の $n$ 個の固有値が
$|\,\lambda_1\,| \gt |\,\lambda_2\,| \gt \cdots \gt |\,\lambda_n\,| \gt 0$  $\cdots\cdots$ $(\sharp)$
を満たせば、デフレーションを繰り返すことにより $A$ の全ての固有値・固有ベクトルを求めることができる。
 $(\sharp)$ を満たすとき、$A$ にデフレーションを施した行列 $B$ の固有値・固有ベクトルは
$(\textcolor{red}{0},\vvv_1)$,  $(\lambda_2,\vvv_2)$,  $(\lambda_3,\vvv_3)$,  $\cdots$,  $(\lambda_n,\vvv_n)$
になります。すると $\lambda_2$ が $B$ の最大固有値になり、$B$ に累乗法を適用することで $(\lambda_2,\vvv_2)$ が求まります。
 さらに $B$ にデフレーションを施した行列 $C$ の固有値・固有ベクトルは
$(\textcolor{red}{0},\vvv_1)$,  $(\textcolor{red}{0},\vvv_2)$,  $(\lambda_3,\vvv_3)$,  $\cdots$,  $(\lambda_n,\vvv_n)$
となり、$\lambda_3$ が $C$ の最大固有値となって ... という仕組みです。

実行例

Ex.10 前回ネズミの絵で説明した $\dps{A=\mat{rr}{3 & 1 \\ 1 & 3}}$ の場合