ヤコビ法 (固有値問題)

数学 > 数値解析 > 数値線形代数 > 固有値問題の数値解法 > ヤコビ法 (固有値問題)

数値線形代数においてヤコビ法（ヤコビほう、古典ヤコビ法）は実対称行列の固有値と固有ベクトルをすべて同時に求める手法である。ドイツの数学者カール・グスタフ・ヤコブ・ヤコビの名前にちなむ。（電子計算機が発明開発された初期において，固有値問題を解く方法としてフォン・ノイマンがこの方法を提唱したので一時期フォン・ノイマンの方法と呼ばれていたようである。しかしその後に数学者・天文学者ヤコビが既にこの方法も含めた計算手法について公表していたことが判明したので，今日ではヤコビの対角化法と呼ばれる。）

原理

対称行列$A=[a_{ij}]\in \mathbb {R} ^{n\times n}$が与えられたとき、ヤコビの回転行列$U_{1}=[u_{ij}]$を次のように定める。

$U_{1}:={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &\cos(\theta )&\cdots &\sin(\theta )&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &-\sin(\theta )&\cdots &\cos(\theta )&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}},\quad u_{pp}=u_{qq}=\cos(\theta ),\quad u_{pq}=\sin(\theta ),\quad u_{qp}=-\sin(\theta ).$

$\tan(2\theta )={\frac {-2a_{pq}}{a_{pp}-a_{qq}}},\quad -\pi /4\leq \theta \leq \pi /4.$

このとき、非対角要素のうちで絶対値最大な要素$a_{pq}$に対して

$A_{1}:=U_{1}^{t}AU_{1}$

とおく。以下、

$A_{\nu -1}=U_{\nu -1}^{t}A_{\nu -2}U_{\nu -1}=U_{\nu -1}^{t}\cdots U_{1}^{t}AU_{1}\cdots U_{\nu -1}$

の非対角要素のうち、絶対値最大な要素に対して順次同じ操作を行って回転行列$U_{\nu }$を定める。このとき、

$\lim _{\nu \to \infty }A_{\nu }=D$

が成り立つ ($D$は対角行列)。$D$の対角要素が$A$の固有値で$\prod _{i=1}^{\infty }U_{i}$の各列が固有ベクトルを与える。

変種

上記で述べられている絶対値が最大の非対角要素を毎回直交回転で消去し続ける（ヤコビが本来提案したのと同じ）方法を古典ヤコビ法と称する。 電子計算機上での能率の面などから古典法から消去の方針を変更して得られた変種がある。

• しきい値ヤコビ法 ($\epsilon _{1}\geq \epsilon _{2}\geq \cdots$となるようにしきい値$\epsilon _{\nu }>0$を選び、$|a_{pq}^{(\nu )}|>\epsilon _{\nu }$なる$a_{pq}^{(\nu )}$に対して回転を施す)
• 特別巡回ヤコビ法 (2次収束する)

そのほかにも算法の並列性を引き出して使う並列化ヤコビ法や、電子計算機上での記憶参照の局所性を高めるブロック化算法としてのブロック化ヤコビ法もある。

意義

現代ではQR法や可積分アルゴリズムなど、ヤコビ法（古典ヤコビ法）より計算が早くて精度の良い方法が多く存在する。しかしそれらのほとんどは固有ベクトルを併せて求めることはできないので、逆べき乗法を使う必要がある。そのため現代においても，すべての固有値および固有ベクトルが同時に求められてしかも終盤で2次収束をするヤコビ法（古典ヤコビ法）は重宝されている。なお，ヤコビ法は行列が密で実対称の場合ばかりが特に有名であるが，同様の手法で複素エルミート密行列の全固有値全固有ベクトルを求めることができる。なおかつては（一般的には要素が複素数の）非対称な密行列に対する固有値問題に対するヤコビ法も研究されていた。

参考文献

• Golub, G.H.; van der Vorst, H.A. (2000). "Eigenvalue computation in the 20th century". en:Journal of Computational and Applied Mathematics. 123 (1–2): 35–65.
• Sameh, A.H. (1971). "On Jacobi and Jacobi-like algorithms for a parallel computer". en:Mathematics of Computation. 25 (115): 579–590.
• Veselić, K. (1979). "On a class of Jacobi-like procedures for diagonalising arbitrary real matrices". en:Numerische Mathematik. 33 (2): 157–172.
• Veselić, K.; Wenzel, H. J. (1979). "A quadratically convergent Jacobi-like method for real matrices with complex eigenvalues". en:Numerische Mathematik. 33 (4): 425–435.
• Gene H. Golub, Charles F. van Loan: "Matrix Computations" (3rd Ed.), 第8.4節 "Jacobi Methods", Johns Hopkins University Press (1996).

外部リンク

• 行列の固有値問題
• 固有値解析 (PDF)