数値解析 第15回 (7) 付録 古典的ヤコビ法の収束性
補題
古典的ヤコビ法が必ず収束することを証明しましょう。
はじめに補題を３つ用意します。
Lemma 23 任意の $n$ 次行列 $A=(a_{ij})$, $B=(b_{ij})$ に対し、
$\mbox{tr}(AB)=\mbox{tr}(BA)$ が成り立つ。
ただし $\mbox{tr}$ は
第14回 に述べたとおり対角成分の和を表します。
証明
$\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 24 任意の $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 25 任意の $n$ 次行列 $A=(a_{ij})$ と $n$ 次の直交行列 $R$ に対し、
$B = R^{-1} \, A \, R = {}^tR \, A \, R$
とおくと
( $B$ の成分の2乗和 ) $=$ ( $A$ の成分の2乗和 )
が成り立つ。
証明 L'a 24 より $\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) & (\ \because\ Prop.5\ )\\
&= \mbox{tr}(({}^tP)({}^tA) P({}^tP)AP) \\
&= \mbox{tr}(({}^tA) P({}^tP)AP({}^tP)) & (\ \because\ L'a\ 23\ )\\
&= \mbox{tr}({}^tA EAE) = \mbox{tr}({}^tA A).
\end{align}
古典的ヤコビ法の収束性
絶対値最大の非対角要素 $a_{pq}$, 角 $\theta$, $R=R(p,q;\theta)$ を
Alg.21 のとおりとし、
$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 25 の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'a25 より。
さて、古典的ヤコビ法では $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.21 のループを $m$ 繰り返せば
( 非対角成分の2乗和 ) $\leqq$ ( 最初の非対角成分の2乗和 ) $\times \dps{\left(1 - \frac{2}{n^2-n}\right)^m }$ $\rightarrow 0$ ( $m\rightarrow\infty$ )
となって、非対角成分は全て $0$ に収束することがわかります。