ヤコビ法 (固有値問題)

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

数値線形代数においてヤコビ法（ヤコビほう、古典ヤコビ法）は実対称行列の固有値と固有ベクトルをすべて同時に求める手法である。ドイツの数学者カール・グスタフ・ヤコブ・ヤコビの名前にちなむ。

原理

対称行列$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.

外部リンク

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