ヤコビ法(固有値問題)

August 16, 2018, 6:07 pm

ヤコビ法(Jacobi Method)は対称な行列の固有値と固有ベクトルを求める(固有値問題を解く)方法。線形方程式の反復解法としてのヤコビ法もあるがここでのヤコビ法はそっちのヤコビ法じゃない。

行列\(A\)\(n\times n\)の正方行列で対称\(A^\mathrm{T}=A\)とする。このとき固有値方程式

\[ Ax=\lambda x\tag{1}\]

を満たす\(\lambda\)\(x\)の組を求めるのが固有値問題。ゼロでない\(x\)に対して(1)が成立するためには方程式

\[ (\lambda I-A)x=0\tag{2}\]

の係数行列の行列式が0でなければならない。さもなければ\((\lambda I-A)\)の逆行列が存在して(2)の解が\(x=0\)の一意に定まってしまう。よって\(\lambda\)

\[ |\lambda I -A|=0\tag{3}\]

を満たす。ヤコビ法では行列\(A\)に対して正則行列\(P\)による相似変換\(B=P^{-1}AP\)を繰り返し施して行列\(A\)を対角行列に近づける。

\[ |\lambda I -A|=|P(\lambda P^{-1}P-P^{-1}AP)P^{-1}|=\\ |P||\lambda I -B|/|P|=|\lambda I - B|\]

より相似変換は(3)を変えないから\(B\)の固有値と\(A\)の固有値は全く同じになる。ヤコビ法では行列\(P\)を次のように取る。

\[ P= \begin{pmatrix} \ddots&&&&\\ &\cos\phi&&\sin\phi&\\ &&\ddots&&\\ &-\sin\phi&&\cos\phi&\\ &&&&\ddots\\ \end{pmatrix}\tag{4}\]

行列\(P=(P_{ij})\)は成分が\(P_{pp}=P_{qq}=\cos\phi\),\(P_{pq}=\sin\phi\),\(P_{qp}=-\sin\phi\)でありそれ以外の要素は単位行列と等しいような行列である。ただし\(p\lt q\)とする。\(P^\mathrm{T}P=PP^\mathrm{T}=I\)より\(P\)は直行行列であり\(P^{-1}=P^\mathrm{T}\)。このとき\(B=P^\mathrm{T}AP\)\(B^\mathrm{T}=(P^\mathrm{T}AP)^\mathrm{T}=P^\mathrm{T}AP=B\)であり\(B\)も対称行列である。\(A=(a_{ij})\)\(B=(b_{ij})\)として成分を書き下す。簡単のため\(C=(c_{ij})\)\(C=AP\)としていったん行列\(C\)の成分を書き下すと

\[ c_{ip}=a_{ip}\cos\phi-a_{iq}\sin\phi\\ c_{iq}=a_{ip}\sin\phi+a_{iq}\cos\phi\tag{5}\]

\(i\neq p, q\)のとき\(c_{ij}=a_{ij}\)である。同様にして\(B=P^\mathrm{T}C\)の成分を書き下すと

\[ b_{pj}=c_{pj}\cos\phi-c_{qj}\sin\phi\\ b_{qj}=c_{pj}\sin\phi+c_{qj}\cos\phi\tag{6}\]

\(j\neq p, q\)のとき\(b_{ij}=c_{ij}\)である。(さらっと書いたけど実際考えると面倒だよね。)これより\(i,j\)が両方\(p,q\)のいずれでもない場合は\(b_{ij}=a_{ij}\)\(i,j\)の内どちらかが\(p\)\(q\)に等しい場合は上の式のどれかがそのまま使える。問題は\((i,j)=(p,p),(q,q),(p,q)\)のとき、\((q,p)\)の場合は\(B\)が対称行列で\((p,q)\)の時と同じ結果になるので考えなくていい。この3つの場合をそれぞれ書き下すと

\[ b_{pp}=(a_{pp}\cos\phi-a_{pq}\sin\phi)\cos\phi-(a_{qp}\cos\phi-a_{qq}\sin\phi)\sin\phi \\=a_{pp}\cos^2\phi-2a_{pq}\sin\phi\cos\phi+a_{qq}\sin^2\phi \\=a_{pp}\frac{1+\cos 2\phi}{2}-a_{pq}\sin 2\phi+a_{qq}\frac{1-\cos 2\phi}{2} \\=\frac{a_{pp}+a_{qq}}{2}+\frac{a_{pp}-a_{qq}}{2}\cos 2\phi-a_{pq}\sin 2\phi\tag{7}\]

\[ b_{qq}=(a_{pp}\sin\phi+a_{pq}\cos\phi)\sin\phi+(a_{qp}\sin\phi+a_{qq}\cos\phi)\cos\phi \\=a_{pp}\sin^2\phi+2a_{pq}\sin\phi\cos\phi+a_{qq}\cos^2\phi \\=a_{pp}\frac{1-\cos 2\phi}{2}+a_{pq}\sin 2\phi+a_{qq}\frac{1+\cos 2\phi}{2} \\=\frac{a_{pp}+a_{qq}}{2}-\frac{a_{pp}-a_{qq}}{2}\cos 2\phi+a_{pq}\sin 2\phi\tag{8}\]

\[ b_{pq}=(a_{pp}\sin\phi+a_{pq}\cos\phi)\cos\phi-(a_{qp}\sin\phi+a_{qq}\cos\phi)\sin\phi \\=a_{pp}\sin\phi\cos\phi+a_{pq}\cos^2\phi-a_{qp}\sin^2\phi \\-a_{qq}\cos\phi\sin\phi \\=\frac{a_{pp}-a_{qq}}{2}\sin 2\phi+a_{pq}\cos 2\phi\tag{9}\]

ヤコビ法では対角成分\(b_{pq}\)がゼロになるように\(\phi\)を選ぶ。よって\(\phi\)

\[ \tan 2\phi=\frac{-2a_{pq}}{a_{pp}-a_{qq}}\tag{10}\]

を満たすように選ぶ。\((p,q)\)として毎回\(|a_{pq}|\)が最大のものを選んで(10)を満たすような\(\phi\)によって\(P\)を作って相似変換を繰り返し施せば非対角成分はいずれ全てゼロに収束する。このときの対角成分が固有値、また相似変換に用いた行列の積の列ベクトルがそれぞれに対応する固有ベクトルになっている。これがヤコビ法の大まかな説明である。

次にヤコビ法が収束することを示す。まず\(P\)が直行行列であることから

\[ B^2=B^\mathrm{T}B=(P^\mathrm{T}AP)^\mathrm{T}(P^\mathrm{T}AP) \\=P^\mathrm{T}A^\mathrm{T}AP=P^\mathrm{T}A^2P\]

相似変換によって行列のトレースは変化しないから\(\mathrm{tr} A^2=\mathrm{tr} B^2\)。これを成分で書くと

\[ \mathrm{tr} A^2=\sum_{i}\sum_{j}a_{ij}a_{ji}=\sum_{i,j}a_{ij}^2\]

\(B^2\)も同様(\(A\)\(B\)が対称行列である性質を使っていることに注意)。これは行列の各成分の2乗和が相似変換によって変わらないことを意味している。また、本当に面倒くさい計算をすると(7),(8),(9)から次の関係が導かれる。(本当に面倒くさいけど(7),(8),(9)の途中式を使えば比較的簡単に出せる。まあ面倒。)

\[ b_{pp}^2+2b_{pq}^2+b_{qq}^2=a_{pp}^2+2a_{pq}^2+a_{qq}^2\tag{11}\]

\(b_{pq}=0\)となるように選んでいたので(11)は次のように書き換えられる。

\[ b_{pp}^2+b_{qq}^2=a_{pp}^2+2a_{pq}^2+a_{qq}^2\tag{12}\]

これは行列\(B\)の対角成分の2乗和が\(A\)の対角成分の2乗和より減っていることを意味しているが、成分全体の2乗和は変わらないので、これは行列\(B\)の非対角成分の2乗和が\(A\)のそれよりも減っていることがわかる。よってヤコビ法はいずれ収束する。

収束することは分かったがヤコビ法は大きな次元の行列に対しては適用できない。理由は記憶量、計算量ともに非効率だから。じゃあいつ使うんだよって話だけれどもはなから全ての固有値固有ベクトルが欲しい場合には意外と使えるらしい。もちろんいろいろな工夫をしたうえでの話。知らんけど。

Previous Post Next Post