固有値問題の数値解法

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

数値線形代数において高速・高精度で安定な固有値問題の数値解法（こゆうちのすうちかいほう、英: 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]

出典

1. ^ 山本哲朗『数値解析入門』サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月、増訂版。ISBN 4-7819-1038-6。
2. ^ 森正武. 数値解析 第2版. 共立出版.
3. 解析学百科II 可積分系の数理、朝倉書店、中村佳正 et al. (2018)
4. 可積分系の機能数理、共立出版、中村佳正。
5. Moler, C. B., & Stewart, G. W. (1973). An algorithm for generalized matrix eigenvalue problems. en:SIAM Journal on Numerical Analysis, 10(2), 241-256.
6. Paul N. Swarztrauber:A parallel algorithm for computing the eigenvalues of a symmetric tridiagonal matrix,Math. Comp., Vol.60, No.202, (Apr.,1993), pp.651-668.
7. 桑島豊, & 重原孝臣. (2005). 実対称三重対角固有値問題の分割統治法の拡張 (行列・固有値問題における線形計算アルゴリズムとその応用). 日本応用数理学会論文誌, 15(2), 89-115.
8. 桑島豊, & 重原孝臣. (2006). 実対称三重対角固有値問題に対する多分割の分割統治法の改良 (理論, 行列・固有値問題の解法とその応用, 平成 18 年研究部会連合発表会). 日本応用数理学会論文誌, 16(4), 453-480.
9. Sakurai, T., & Sugiura, H. (2003). A projection method for generalized eigenvalue problems using numerical integration. en:Journal of computational and applied mathematics, 159(1), 119-128.
10. Sakurai, T., & Tadano, H. (2007). CIRR: a Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems. Hokkaido mathematical journal, 36(4), 745-757.
11. Tsutomu Ikegami, Tetsuya Sakurai and Umpei Nagashima: A Filter Diagonalization for Generalized Eigenvalue Problems Based on the Sakurai-Sugiura Projection Method, J. Compu. Appl. Math., Vol.233, No.8, pp.1927–1936 (2010).
12. Anthony P. Austin and Lloyd N. Trefethen: Computing Eigenvalues of Real Symmetric Matrices with Rational Filters in Real Arithmetic, SIAM J. Sci. Comput, Vol.37, No.3, pp.A1365–A1387 (2015).
13. Hiroshi Murakami: Filter Diagonalization Method by Using a Polynomial of a Resolvent as the Filter for a Real Symmetric-Definite Generalized Eigenproblem, in proceedings of EPASA2015, Springer, LNCSE-117, pp.205–232 (2018).
14. Hiroshi Murakami: Filters Consist of a Few Resolvents to Solve Real Symmetric-Definite Generalized Eigenproblems, Japan J. Indust. Appl. Math., Vol.36, No.2, pp.579–618 (July 2019).

参考文献

和書

• 一松信：「数値解析」、朝倉書店（新数学講座13）、ISBN 978-4254114430（1982年10月）。
• 森正武：「数値解析法」、朝倉書店（朝倉現代物理学講座 7）、ISBN 978-4254135671 (1984年11月)。
• 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）
• 櫻井鉄也, 松尾宇泰, 片桐孝洋編：数値線形代数の数理とHPC, 共立出版（シリーズ応用数理 / 日本応用数理学会監修, 第6巻）（2018年8月)。
• 大石進一 編著：『精度保証付き数値計算の基礎』、コロナ社、2018年。
• 日本計算工学会(編):「固有値計算と特異値計算」、丸善、ISBN 978-4-621-30473-0 (2019年12月20日)。

洋書

• David S. Watkins (2008), The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM.
• Saad, Y. (2011). Numerical methods for large eigenvalue problems: revised edition. SIAM.
• Gene H. Golub and Charles F. Van Loan: "Matrix Computations", 3rd Edition, The Johns Hopkins University Press, ISBN 0-8018-5413-X(hard cover), ISBN 0-8018-5414-8(pbk), (1996).
• Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., & van der Vorst, H. (Eds.). (2000). Templates for the solution of algebraic eigenvalue problems: a practical guide. SIAM.
• Lehoucq, R. B., Sorensen, D. C., & Yang, C. (1998). ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM.
• Wilkinson, J. H. (1965). The algebraic eigenvalue problem. Clarendon: Oxford.
• Chatelin, F. (Ed.). (2012). Eigenvalues of Matrices: Revised Edition. SIAM.

外部リンク

• 固有値問題の高速高精度解法の研究