固有値問題の数値解法

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
検索に移動
数学 > 数値解析 > 数値線形代数 > 固有値問題の数値解法

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

数値解法の必要性[編集]

5次以上の一般の(実数あるいは複素数の)行列において、有限回の(四則及び冪根を開く)代数的操作によって厳密な固有値を求める直接法はない(そうして固有値問題の数値解法は反復法に限られる)。もしも有限回の代数的操作で厳密な固有値を求める方法があるとするならば、係数が一般の代数方程式:

の解同伴行列:

の固有値を求めることにより有限回の代数的操作で求まることになるが、これはガロア理論の結論と相いれない[1]

固有ベクトルの計算[編集]

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

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

代表的な手法[編集]

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

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

出典[編集]

[脚注の使い方]
  1. ^ a b c d 山本哲朗『数値解析入門』サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月、増訂版。ISBN 4-7819-1038-6。
  2. ^ a b c 森正武. 数値解析 第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. ^ 桑島豊, & 重原孝臣. (2005). 実対称三重対角固有値問題の分割統治法の拡張 (行列・固有値問題における線形計算アルゴリズムとその応用). 日本応用数理学会論文誌, 15(2), 89-115.
  7. ^ 桑島豊, & 重原孝臣. (2006). 実対称三重対角固有値問題に対する多分割の分割統治法の改良 (理論, 行列・固有値問題の解法とその応用, 平成 18 年研究部会連合発表会). 日本応用数理学会論文誌, 16(4), 453-480.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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).
  11. ^ 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).
  12. ^ 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).
  13. ^ 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).

参考文献[編集]

和書[編集]

  • 数値線形代数の数理とHPC, 櫻井鉄也, 松尾宇泰, 片桐孝洋編(シリーズ応用数理 / 日本応用数理学会監修, 第6巻)共立出版, 2018.8
  • 『精度保証付き数値計算の基礎』大石進一 編著、コロナ社、2018年。
  • 大石進一:「精度保証付き数値計算」、コロナ社、(1999年)

洋書[編集]

  • 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.
  • 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.