2 解法についての概観

歴史的なことを述べると、以前は対称な問題は Jacobi 法と呼ばれるアルゴ リズムで解かれるのが普通であった。しかし Jacobi 法は $N$ が小さな(せい ぜい数十)である場合には実用的であるが、$N$ の大きな問題を解くのに採用 するのは得策ではない。今では行列の三重対角化や Hessenberg 形への変換を 利用した解法が主流である（対称行列の場合は三重対角化、非対称行列の場合 は Hessenberg 行列への変換を行なうことになる）。行列を三重対角化 (resp. Hessenberg 化) するとは、相似変換を施して、行列を三重対角行列 (resp. Hessenberg 行列) に変換することをいう。この変換の方法は色々あ るが、いずれも $O(N^3)$ の演算量で済む。後で述べるように相似変換で固有 値は不変なので、変換後の「簡単な」行列の固有値を求めれば、元の行列の固 有値が求まったことになる。三重対角行列や Hessenberg 行列に対する固有値 問題は、元の行列よりも簡単に解ける、というのが基本的なアイディアである。

色々な細かな技法 (部品) を、利用者の要求に応じて組み合わせることで、 望ましい解法が出来上がる。以下、それらの原理を説明する。三重対角化や Hessenberg 化のためのアルゴリズムの解説は次節にまわして、ここでは 実際に固有値を求める諸方法を解説する。