next up previous
Next: B..4 Gauss の消去法 Up: B. 線形計算とは Previous: B..2 連立1次方程式の解法概説


B..3 固有値問題の解法概説

(授業では説明する時間的余裕はないと思うが…)

固有値を求めるという問題は代数方程式に帰着されるわけだが、 その逆に任意の代数方程式の問題は行列の固有値を求めるという問題に帰着できる (この事実はしばしば常微分方程式の本に書いてある)。

それゆえ、ある意味で固有値問題は代数方程式と等価であり、 例えば「$ 5$ 次以上の代数方程式の、 四則とべき根を有限回用いた根の公式は存在しない」という有名な定理から、 $ 5$ 次以上の行列の固有値問題は、 有限回の四則演算とべき乗演算では解けないことが分かる。 それゆえ連立1次方程式の解法と対比してみると、 ($ 5$ 次以上の) 固有値問題には直接法は存在せず、 反復法を使うしかないことが分かる。

もう一つ重要なのは、 行列から固有多項式を作ると、 もともとの行列が持っていた情報の多くが消えてしまうということである。 例えば対称な固有値問題は、 そうでない問題よりもうまく (速く安定に) 解けるのだが、 それを固有多項式にしてしまうと、対称性のうま味がなくなってしまう。 その他にも理由があって、結局は

固有値を求めるのに固有方程式を解こうとしてはいけない!

それでは実際にどうするか? 現在では次の 2 ステップで攻略するのが良いと言われている。

(1)
与えられた行列 $ A$ を、 実直交行列 $ U$ で相似変換して、 Hessenberg 行列 (あるいは $ A$ が対称の場合は三重対角行列) $ \widetilde A$ に変換する (つまり $ \widetilde A=U^T A U$ )。
(2)
$ \widetilde A$ に対して、
  1. 冪乗法の系統の方法 (逆反復法, シフト法, 減次)
  2. Strum の方法 (bisection method)
  3. QR 法
などの反復法を施して、固有値を求める。

$ A=(a_{ij})$ Hessenberg 行列とは、

$\displaystyle i>j+1\quad\Then\quad a_{ij}=0
$

が成り立つこと (対角線より二つ以上下は 0 ) を言う。 大ざっぱに言うと、 後一歩で上三角行列になる行列ということである。


next up previous
Next: B..4 Gauss の消去法 Up: B. 線形計算とは Previous: B..2 連立1次方程式の解法概説
桂田 祐史
2012-07-11