5 Jacobi 法

誰だったか忘れたが (戸川先生?)、 Jacobi 法をモグラ叩きに例えた人がいる。 これはなかなかイメージが湧いてきて良いと思う。

証明.

$${\rm tr} (A^T A) = \sum_{i=1}^n \mbox{$A^T A$ の $(i,i)$ 要素}$$

$$= \sum_{i=1}^n \sum_{j=1}^n \mbox{$A^T$ の $(i,j)$ 要素} \mbox{$A^T$ の $(j,i)$ 要素}$$

$$= \sum_{i=1}^n\sum_{j=1}^n a_{ji}a_{ij}$$

$$= \sum_{i,j=1}^n {a_{ji}}^2. \qed$$

$\qedsymbol$

実行列 $A$ を実直交行列 $U$ で相似変換した $B=U^T A U$ について、

$${\rm tr}(B^T B)={\rm tr}(U^T A^T U\cdot U^T A U)={\rm }(U^T A^T A U)$$

となるが、 良く知られた公式 ${\rm tr}(AB)={\rm tr}(BA)$ より⁴、

$${\rm tr}(B^T B)={\rm }(A^T A U U^T)={\rm tr}(A^T A)$$

であるから、

   $$\mbox{$B$ の要素の平方和}$$$$=$$$$\mbox{$A$ の要素の平方和}$$$$,$$

つまり

実直交行列による相似変換で要素の平方和は不変である。

証明. 単純な計算なので略する。 $\qedsymbol$ $\qedsymbol$

この定理に基づき、$A_k$ が十分対角行列に近づいたときに計算を打ち切り、 $A$ の近似固有値として ${a_{11}}^{(k)}$ , $\cdots$ , ${a_{nn}}^{(k)}$ , それらに属する近似固有ベクトルとして $V_k$ の各列を採用する。これを古典 Jacobi 法と呼ぶ。

有限ステップで停止したときの誤差評価として、次の定理がある。

証明. (1) は摂動定理を使うだけ。(2) は、まず $(p,q)$ の選び方より

$$(a_{pq}^{(k)})^2\ge \frac{F^{(k)}}{n(n-1)}$$

であり、

$$F^{(k)}-F^{(k+1)}=2(a_{pq}^{(k)})^2\ge \frac{2}{n(n-1)}F^{(k)} =\frac{1}{N}F^{(k)}.$$

(3) については省略。 $\qedsymbol$ $\qedsymbol$

絶対値最大の要素の探索はかなり手間がかかる (計算量が大きくなる) ので、 色々な変種が考えられている。 ある「しきい閾値」 $\eps_1\ge \eps_2\ge\cdots$ と選び、 $\vert a_{pq}^{(k)}\vert>\eps_k$ なる $a_{pq}^{(k)}$ に対して回転を施す 閾値 Jacobi 法や、

for p:=1 to n-1 do

    for q:=p+1 to n

        $a_{pq}$ を叩く

を繰り返す特別巡回 Jacobi 法などがある。