数値解析（塩田）2023年度

数値解析第15回　付録　古典的ヤコビ法の収束性

戻る

直交行列

　実対称行列の対角化に必要な直交行列に関する基礎知識をまとめておきます。

Def.1　

$({}^tP)P=E$ (

$E$ は単位行列 ) を満たす実数成分の正方行列を 直交行列 と呼ぶ。

Th.2　次はいずれも

$P$ が直交行列であることと同値である：

$({}^tP)P=E.$
$P({}^tP)=E.$
$P^{-1} = {}^tP.$
$P$ の列ベクトルたちは正規直交基底をなす。
$P$ の行ベクトルたちも正規直交基底をなす。

正規直交基底とは、次元と同じ個数の、互いに直交する長さ 1 のベクトルたちのことです。

証明を見る

証明を折りたたむ　(1)

$\Leftrightarrow$ (3)

$\Leftrightarrow$ (2) はすぐわかります。

$({}^tP)P$ の

$(i,j)$ -成分は

$P$ の第

$i$ 列と第

$j$ 列の内積ですから (1)

$\Leftrightarrow$ (4). 同様に

$P({}^tP)$ の

$(i,j)$ -成分は

$P$ の第

$i$ 行と第

$j$ 行の内積ですから (2)

$\Leftrightarrow$ (5) が言えます。 (証明終)

Prop.3　(1)　直交行列の積も直交行列である。
(2)　直交行列の逆行列も直交行列である。
(3)　直交行列の行列式は

$\pm 1$ である。

証明を見る

証明を折りたたむ　(1)　

$({}^tP)P=({}^tQ)Q=E$ であれば

${}^t(PQ)PQ=({}^tQ)({}^tP)PQ=({}^tQ)EQ=({}^tQ)Q=E$ . (2)　Prop.4, Th.10 (2) より

$({}^t({}^tP))({}^tP)=P({}^tP)=E$ . (3)　

$1=\det(E)=\det(({}^tP)P)=\det({}^tP)\det(P)=\det(P)^2$ ゆえ。(証明終)

Def.4　次の形の行列

$R(p,q;\theta)$ は、

$n$ 次元座標

$(x_1,x_2,\cdots,x_n)$ のうち、

$x_p$ と

$x_q$ に関する角

$\theta$ の回転を表す。

$R(p,q;\theta)= \mat{ccccc}{ & \vdots && \vdots & \\ \cdots & \cos\theta & \cdots & -\sin\theta & \cdots \\ & \vdots && \vdots & \\ \cdots & \sin\theta & \cdots & \cos\theta & \cdots \\ & \vdots && \vdots & \\}$ ただし、

$\cos\theta$ は

$(p,p)$ -成分と

$(q,q)$ -成分、

$-\sin\theta$ は

$(p,q)$ -成分、

$\sin\theta$ は

$(q,p)$ -成分で、これ以外の成分は単位行列に同じとする。

Prop.5　

$R(p,q;\theta)$ は直交行列である。

古典的ヤコビ法

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

Alg.6 ( 古典的ヤコビ法 )
入力：

$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 7　任意の

$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 8　任意の

$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 9　任意の

$n$ 次行列

$A=(a_{ij})$ と

$n$ 次の直交行列

$R$ に対し、

$B = R^{-1} \, A \, R = {}^tR \, A \, R$ とおくと (

$B$ の成分の2乗和 )

$=$ (

$A$ の成分の2乗和 ) が成り立つ。

証明　L'a 8 より

$\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\ 7\ )\\ &= \mbox{tr}({}^tA EAE) = \mbox{tr}({}^tA A). \end{align}$

古典的ヤコビ法の収束性

　絶対値最大の非対角要素

$a_{pq}$ , 角

$\theta$ ,

$R=R(p,q;\theta)$ を Alg.6 のとおりとし、

$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 9 の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 9 より。

　さて、古典的ヤコビ法では

$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.6 のループを

$m$ 繰り返せば ( 非対角成分の2乗和 )

$\leqq$ ( 最初の非対角成分の2乗和 )

$\times \dps{\left(1 - \frac{2}{n^2-n}\right)^m }$

$\rightarrow 0$ (

$m\rightarrow\infty$ ) となって、非対角成分は全て

$0$ に収束することがわかります。

戻る