数値解析 第15回 (4) ヤコビ法の発想
ヤコビ法の発想
Th.15,
Rem.16 より、実対称行列 $A$ は、
$P = R_1 \, R_2 \, \cdots \, R_t$
( ただし $R_i$ は $R(p,q;\theta)$ の形の回転の行列 )
と書ける直交行列 $P$ を用いて
$P^{-1} \, A \, P = {}^tP \, A \, P = \dps{\mat{ccc}{\lambda_1 && \\ & \ddots & \\ && \lambda_n}}$
のように対角化できます。
\begin{align}
{}^tP \, A \, P
&= {}^t(R_1 \, R_2 \, \cdots \, R_t)\, A \, (R_1 \, R_2 \, \cdots \, R_t) \\
&= ({}^tR_t \, \cdots \, {}^tR_2\, {}^tR_1)\, A \, (R_1 \, R_2 \, \cdots \, R_t) \\
&= {}^tR_t \, (\cdots \, ({}^tR_2\, ({}^tR_1\, A \, R_1) \, R_2) \, \cdots )\, R_t \tag{$\sharp$} \\
\end{align}
ですから
$(\sharp)$ が対角行列になるように、上手に回転の行列 $R_1$, $R_2$, $\cdots$ を選べばよいのではないか
という発想ができます。
さらに、
2次元の場合 には $R(\theta)=R(1,2;\theta)$ の形の行列で $(1,2)$-成分を $0$ にできたことから
作戦 17 Th.7 のように角 $\theta$, $\theta'$, $\cdots$ を適切に選んで、順番に
- $R(1,2;\theta)$ で $(1,2)$-成分を $0$ に
- $R(1,3;\theta')$ で $(1,3)$-成分を $0$ に
$\vdots$
- $R(2,3;\theta'')$ で $(2,3)$-成分を $0$ に
- $R(2,4;\theta''')$ で $(2,4)$-成分を $0$ に
$\vdots$
すればいいんじゃないの？
と、最初は思いますね。やってみましょう。
Rem.18 $A$ が対称行列なので、Prop.5 より ${}^tP\,A\,P$ の形の行列も対称行列になることに注意しておいてください。
作戦 17 の実行例
Ex.19
$\dps{A = \mat{ccc}{
1 & 2 & 3 \\
2 & 5 & 6 \\
3 & 6 & 7}}$
に対して 作戦 17 を実行してみる。
まず $(1,2)$-成分をターゲットにして
\begin{align}
\theta
&=\frac{1}{2}\arctan\left(\frac{2 a_{12}}{a_{11} - a_{22}}\right) \\
&=\frac{1}{2}\arctan\left(\frac{2 \times 2}{1 - 5}\right)
= -0.3926990817, \\
R_1
&= R(1, 2; \theta)
=\mat{rrr}{
0.9238795325 & 0.3826834324 & 0 \\
-0.3826834324 & 0.9238795325 & 0 \\
0\phantom{xxxx} & 0\phantom{xxxx} & 1 }
\end{align}
とおきます。$A_1={}^tR_1 \, A \, R_1$ を計算すれば
$\require{color}$
\begin{align}
A_1
&= {}^tR_1 \, A \, R_1 \\
&=\mat{rrr}{
0.1715728753 & \textcolor{red}{-0.0000000000} & 0.4755380033 \\
\textcolor{red}{-0.0000000000} & 5.8284271247 & 6.6913274922 \\
0.4755380033 & 6.6913274922 & 7.0000000000 }
\end{align}
となって
$(1,2)$-成分が $0$ になりました。
次は $(1,3)$-成分をターゲットにして
\begin{align}
\theta'
&=\frac{1}{2}\arctan\left(\frac{2 a'_{12}}{a'_{11} - a'_{22}}\right) \\
&=\frac{1}{2}\arctan\left(\frac{2 \times 0.4755380033}{0.1715728753 - 7}\right) \\
&= -0.0691957668, \\
R_2
&= R(1, 3; \theta') \\
&=\mat{rrr}{
0.9976069280 & 0 & 0.0691405612 \\
0\phantom{xxxx} & 1 & 0\phantom{xxxx} \\
-0.0691405612 & 0 & 0.9976069280 }
\end{align}
とおき、$A_2={}^tR_2 \, A' \, R_2$ を計算します。
$\require{color}$
\begin{align}
A_2
&= {}^tR_2 \, A' \, R_2 \\
&=\mat{rrr}{
0.1386150404 & \textcolor{red}{-0.4626421379} & \textcolor{blue}{-0.0000000000} \\
\textcolor{red}{-0.4626421379} & 5.8284271247 & 6.6753146637 \\
\textcolor{blue}{-0.0000000000} & 6.6753146637 & 7.0329578349 }
\end{align}
おやおや、
$(1,3)$-成分は $0$ になりました が、
せっかく $0$ にした $(1,2)$-成分が $0$ でなくなってしまいました。
問題点 作戦 17 では一度 $0$ にした非対角成分が $0$ でなくなってしまう。
こちらを叩けばあちらが顔を出す、いわゆる
モグラ叩き状態 になってしまいます。
しかし、それでも上手くいくよ、というのが次のページです。