固有値問題の数値解法

数値線形代数において高速・高精度で安定な固有値問題の数値解法（こゆうちのすうちかいほう、英: Eigenvalue Algorithms）の開発および厳密な誤差評価の確立は至上命題の一つであり、この目標を達するためにLAPACKをはじめ多くのライブラリが開発されてきた^[1][2]。

→「固有値」および「線型代数学ライブラリの比較」も参照

数学 > 数値解析 > 数値線形代数 > 固有値問題の数値解法

数値解法の必要性

5次以上の一般の（実数あるいは複素数の）行列において、有限回の代数的操作（四則及び冪根を開く）によって固有値を厳密に表わす計算手順は存在しない。そのため固有値問題の数値解法には必ず反復法を用いることになる。そのことは、もしも有限回の代数的操作で厳密な固有値を求める方法があったとすれば、係数が一般の${\displaystyle n}$次代数方程式:

${\displaystyle x^{n}+a_{1}x^{n-1}+\cdots +a_{n}=0}$

の解${\displaystyle \lambda _{1},\cdots ,\lambda _{n}}$がその方程式の多項式に対する同伴行列:

${\displaystyle {\begin{pmatrix}0&&&&-a_{n}\\1&0&\cdots &\cdots &-a_{n-1}\\&\ddots &\ddots &&\vdots \\&&\ddots &\ddots &-a_{2}\\&&&1&-a_{1}\\\end{pmatrix}}}$

の固有値として有限回の代数的操作で求められることになるが、これは代数方程式に関するガロア理論のよく知られた結論とは矛盾するので不可能であることを考えればただちにわかる^[1]。 （ただしこのことは有限回の代数的操作で固有値が厳密に表せるような行列もあることまでをも否定するものではない。たとえば対角行列や上三角行列の固有値は直ちにわかる。）

固有ベクトルの計算

固有値問題の数値的な解法にはさまざまものがあるが、固有値だけを求めるだけのものもある。固有値だけではなくて固有ベクトルも求める方法としてはたとえば以下のものがある^[1][2]。

• 逆べき乗法（一時には、一つ（あるいは少数）の固有ベクトルを求める方法である。）
• ヤコビ法 (固有値問題)（すべての固有値と固有ベクトルを同時に求めるもので，実対称行列の場合ばかりが有名であるが，複素エルミート行列の場合も同様に構成できるほか、複素数の一般の場合や実で非対称な場合についての方法なども一応存在する。）

代表的な手法

行列が実対称あるいは複素エルミートである場合には，代数的な演算（四則と開平）だけを用いて構成される直交変換あるいはユニタリ変換を有限回用いて三重対角行列の形に変換することができるので，それを中継としてその三重対角行列の固有値問題を解くことに元の問題を帰着させることが（元の行列が密行列あるいは比較的密な行列に対しては）よく行われてきた。 また行列が実あるいは複素で一般の場合にも、同様に代数的な演算だけで構成できる変換で，ヘッセンベルグ形の行列にまで変換を行うことができるので、それを中継として元の問題をヘッセンベルグ形の行列の固有値問題に帰着させることが（元の行列が密あるいは比較的密に近い行列に対しては）行われてきた。 三重対角形あるいはヘッセンベルグ形にするための方法としては，Givens回転を繰り返す方法やHouseholder変換を繰り返す方法が有名である。 Givens回転あるいはHouseholder変換による三重対角化やヘッセンベルグ形を経由する以前には，密行列に対してはJacobi回転を用いたJacobi対角化法が主に使われていたが，演算量や記憶参照の量が多いことや，行列の添字について行方向と列方向交互のアクセスがあるなど参照パターンが高速な計算機の機構と相性が悪いため1970年代には中間形を経由する方法に置き換えられた。ただし今日でもごく小規模な行列や固有ベクトルの直交精度が重要である場合には使われることがある。

行列が疎である場合には、その行列の種類に応じて，クリロフ部分空間法の系統による三重対角化あるいはヘッセンベルグ化を行う方法がよく行われている。

→「数値線形代数 § クリロフ部分空間法」、「数値線形代数 § 精度保証」、「数値線形代数 § 可積分系との関係」、「ゲルシュゴリンの定理」、および「可積分アルゴリズム」も参照

• べき乗法^[1][2]
• QR法 (可積分系との関係が明らかになっている^[3][4])
• QZ法^[5]
• 分割統治法^[6][7][8]
• Sakurai-Sugiura 法^[9]
• CIRR 法 (Rayleigh-Ritz type method with contour integral)^[10]
• フィルターを用いた固有値問題の解法^{[11][12][13][14]}