前へ / 戻る

古典的ヤコビ法のアルゴリズム

　絶対値最大の非対角要素をターゲットにする方法を古典的ヤコビ法と呼びます。

古典的ヤコビ法の収束性

　古典的ヤコビ法が必ず収束することを証明しましょう。 はじめに補題を３つ用意します。 ただし $\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). }$ 証明　 $\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. }$ 証明　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})$ とおきます。 証明　$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$ なので主張が成り立ちます。 証明　$R$, ${}^tR$ は $p$, $q$ に無関係な行・列には作用しないので。 証明　主張1,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$ に収束することがわかります。

前へ / 戻る