数値解析 第15回 付録B 古典的ヤコビ法の収束性
古典的ヤコビ法のアルゴリズム
絶対値最大の非対角要素をターゲットにする方法を古典的ヤコビ法と呼びます。
Alg. ( 古典的ヤコビ法 )
入力： $n$ 次実対称行列 $A$
出力： $A$ の固有値・固有ベクトル $(\lambda_i, \vvv_i)$ ( $i =1,2,\cdots,n$ )
$P=E$
while (継続条件)
絶対値最大の非対角要素を $a_{pq}$ ( $p \lt q$ ) とする
$\theta=\left\{
\begin{array}{lll}
\dps{\frac{1}{2}\arctan\left(\frac{2a_{pq}}{a_{pp}-a_{qq}}\right)} & \mbox{ if} & a_{pp} \neq a_{qq} \\
\dps{\frac{\pi}{4}} & \mbox{ if} & a_{pp} = a_{qq}
\end{array}
\right.$
$R=R(p,q;\theta)$
(新 $A)={}^tR\,A\,R$
(新 $P)=P\,R$
$\lambda_i = a_{ii}$, $\vvv_i=(P$ の第 $i$ 列ベクトル) ( $i =1,2,\cdots,n$ ) を出力
古典的ヤコビ法の収束性
古典的ヤコビ法が必ず収束することを証明しましょう。
はじめに補題を３つ用意します。
Lemma B1 任意の $n$ 次行列 $A=(a_{ij})$, $B=(b_{ij})$ に対し、
$\mbox{tr}(AB)=\mbox{tr}(BA)$ が成り立つ。
ただし $\mbox{tr}$ は対角成分の和を表します。
証明
$\dps{
\mbox{tr}(AB) = \sum_i (AB)_{ii}
= \sum_i \sum_k a_{ik} b_{ki}
= \sum_k \sum_i b_{ki} a_{ik} = \sum_k (BA)_{kk}= \mbox{tr}(BA).
}$
Lemma B2 任意の $n$ 次行列 $A=(a_{ij})$ に対し、
$\dps{\mbox{tr}({}^tAA)=\sum_{i,j} a_{ij}^2 =}$ ( $A$ の成分の2乗和 )
が成り立つ。
証明
$\dps{
\mbox{tr}({}^tAA) = \sum_i ({}^tAA)_{ii}
= \sum_i \sum_k ({}^tA)_{ik} a_{ki}
= \sum_i \sum_k a_{ki} a_{ki} = \sum_{i,k} a_{ki}^2.
}$
Lemma B3 任意の $n$ 次行列 $A=(a_{ij})$ と $n$ 次の直交行列 $R$ に対し、
$B = R^{-1} \, A \, R = {}^tR \, A \, R$
とおくと
( $B$ の成分の2乗和 ) $=$ ( $A$ の成分の2乗和 )
が成り立つ。
証明 L'a B2 より $\mbox{tr}({}^tBB)=\mbox{tr}({}^tAA)$ を示せばよく、
\begin{align}
\mbox{tr}({}^tBB)
&= \mbox{tr}({}^t(({}^tP)AP)({}^tP)AP) \\
&= \mbox{tr}(({}^tP)({}^tA)({}^t({}^tP))({}^tP)AP) \\
&= \mbox{tr}(({}^tP)({}^tA) P({}^tP)AP) \\
&= \mbox{tr}(({}^tA) P({}^tP)AP({}^tP)) & (\ \because\ L'a\ B1\ )\\
&= \mbox{tr}({}^tA EAE) = \mbox{tr}({}^tA A).
\end{align}
古典的ヤコビ法の収束性
絶対値最大の非対角要素 $a_{pq}$, 角 $\theta$, $R=R(p,q;\theta)$ を
Alg. のとおりとし、
$B = R^{-1} \, A \, R = {}^tR \, A \, R,$, $A=(a_{ij})$, $B=(b_{ij})$
とおきます。
主張1 $a_{pp}^2 + 2 a_{pq}^2 + a_{qq}^2 = b_{pp}^2 + b_{qq}^2$.
証明 $A$, $B$ の $(p,p)$, $(p,q)$, $(q,p)$, $(q,q)$-成分だけを書き出すと、
2次元の回転の行列 $R(\theta)$ を用いて
$$
\mat{cc}{b_{pp} & b_{pq} \\ b_{qp} & b_{qq}}
=
{}^tR(\theta)
\mat{cc}{a_{pp} & a_{pq} \\ a_{qp} & a_{qq}}
R(\theta)
$$
となっていて、
L'a B3 の2次元の場合から
$a_{pp}^2 + a_{pq}^2 + a_{qp}^2 + a_{qq}^2 = b_{pp}^2 + b_{pq}^2 + b_{qp}^2 + b_{qq}^2$
が成り立ちます。$A$ は対称行列ゆえ $a_{pq}=a_{qp}$. また $\theta$ の取り方から $b_{pq}=b_{qp}=0$ なので主張が成り立ちます。
主張2 $i \neq p,q$ ならば $a_{ii} = b_{ii}$.
証明 $R$, ${}^tR$ は $p$, $q$ に無関係な行・列には作用しないので。
主張3 ( $B$ の対角成分の2乗和 ) = ( $A$ の対角成分の2乗和 )$+ 2a_{pq}^2$.
証明 主張1,2 より。
主張4 ( $B$ の非対角成分の2乗和 ) = ( $A$ の非対角成分の2乗和 )$- 2a_{pq}^2$.
証明 主張3 と
L'a B3 より。
さて、古典的ヤコビ法では $a_{pq}$ は絶対値が最大の非対角要素でした。
従って
( $A$ の非対角成分の2乗和 ) $\leqq (n^2 - n)a_{pq}^2$
$\therefore$ ( $B$ の非対角成分の2乗和 ) $\leqq$ ( $A$ の非対角成分の2乗和 ) $\times \dps{\left(1 - \frac{2}{n^2-n}\right)}$
となります。
Alg. のループを $m$ 繰り返せば
( 非対角成分の2乗和 ) $\leqq$ ( 最初の非対角成分の2乗和 ) $\times \dps{\left(1 - \frac{2}{n^2-n}\right)^m }$ $\rightarrow 0$ ( $m\rightarrow\infty$ )
となって、非対角成分は全て $0$ に収束することがわかります。