数値解析 第14回 (3) デフレーション
デフレーション
Alg.6 では最大固有値とそれに対する固有ベクトルしか求められませんが、
「デフレーション」という処理により、
2番目、3番目 $\cdots$ に絶対値の大きい固有値についても固有値・固有ベクトルを求めることができるようになります。
Lemma 7 Th.5 の状況下、
次のアルゴリズムによって行列 $B$ を
作ると、
$\dps{
\left\{
\begin{array}{l}
B\vvv_1=\ooo \\
B\vvv_j=\lambda_j\vvv_j \quad ( j \gt 1 ) \\
\end{array}
\right.
}$
が成り立つ。すなわち $B$ は
- $A$ と同じ固有ベクトルを持ち、
- $\vvv_1$ に対する固有値は $\lambda_1$ ではなく $0$ になる
- 他の固有ベクトル $\vvv_j$ に対する固有値は $\lambda_j$ のままである
証明は後述します。
Algorithm 8 ( デフレーション )
- $A$ の最大固有値とそれに対する固有ベクトルを $(\lambda_1,\vvv_1)$ とする
- ${}^tA$ にも Alg.6 を適用して、${}^tA$ の $\lambda_1$ に対する固有ベクトル $\www$ を求める
- $\dps{\uuu=\frac{1}{{}^t\www\,\vvv_1}\www}$ とおく
- $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 では次のことに注意してください。
- ${}^tA$ と $A$ は同じ固有値を持ちます。
( $\det(xE-A)=\det{}^t(xE-A)=\det(xE-{}^tA)$ ゆえ。)
- ${}^t\www\,\vvv_1$ はスカラーです。
- $\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$ では $\lambda_2$ が最大固有値になり、
$B$ に累乗法を適用することで $(\lambda_2,\vvv_2)$ が求まります。
以下、その処理を繰り返します。
Lemma 7 の証明
${}^tA\uuu=\lambda_1\uuu$
の転置を取ると
${}^t\uuu A=\lambda_1{}^t\uuu$
となりますので $j \geqq 2$ に対しては
$(\lambda_1{}^t\uuu)\, \vvv_j=({}^t\uuu A)\vvv_j={}^t\uuu (A\vvv_j)
={}^t\uuu (\lambda_j\,\vvv_j)=\lambda_j{}^t\uuu\,\vvv_j$
が成り立ち、
$(\lambda_1-\lambda_j){}^t\uuu\,\vvv_j=0$
となります。条件 $(\ast)$ から $\lambda_1\neq\lambda_j$ なので
${}^t\uuu\,\vvv_j=0$
が言えます。従って $j \geqq 2$ に対しては
$B\vvv_j =(A-\lambda_1\vvv_1{}^t\uuu)\vvv_j=A\vvv_j-\lambda_1\vvv_1({}^t\uuu\,\vvv_j)=\lambda_j\vvv_j-\lambda_1\vvv_1\,0=\lambda_j\vvv_j$.
また
${}^t\uuu)\vvv_1=\frac{1}{{}^t\www\,\vvv_1} {}^t\www\,\vvv_1=1$
ゆえ
$B\vvv_1 =(A-\lambda_1\vvv_1{}^t\uuu)\vvv_1=A\vvv_j-\lambda_1\vvv_1({}^t\uuu\,\vvv_1)=\lambda_1\vvv_1-\lambda_1\vvv_1=\ooo$.
実行例
Ex.10 前回ネズミの絵で説明した $\dps{A=\mat{rr}{3 & 1 \\ 1 & 3}}$ の場合
実行例を折りたたむ
- 最大固有値は $\lambda_1=4$ で、$\vvv_1=\mat{c}{1 \\ 1}$.
- $A$ は対称行列なので $\www=\vvv_1=\mat{c}{1 \\ 1}$.
- $\dps{{}^t\www\,\vvv_1=(1\ \ 1)\mat{c}{1 \\ 1}=1+1=2}$ ゆえ
$\dps{\uuu=\frac{1}{2}\mat{c}{1 \\ 1}=\mat{c}{1/2 \\ 1/2}}$.
- $\dps{B=A-\lambda_1\vvv_1{}^t\uuu
=\mat{rr}{3 & 1 \\ 1 & 3}-4\,\mat{c}{1 \\ 1}(1/2 \ \ 1/2)}$
$\dps{=\mat{rr}{3 & 1 \\ 1 & 3}-\mat{rr}{2 & 2 \\ 2 & 2}
=\mat{rr}{1 & -1 \\ -1 & 1}
}$.
すると $B$ の固有値・固有ベクトル $(\mu_j,\www_j)$ は
$\dps{
\mu_1=2,\ \www_1=\mat{r}{1 \\ -1};\quad
\mu_2=0,\ \www_2=\mat{c}{1 \\ 1}
}$
となっていて、$B$ に累乗法を適用することにより $(\mu_1,\www_1)=(\lambda_2,\vvv_2)$ が得られます。