n✕n行列(非対称)の固有値問題のアルゴリズム

よろしくおねがいします。

タイトルの通り、
n✕n行列の固有値を求めるプログラムを作成しようと考えています。
ただし、行列は非対称行列とするためJacobi法等は使えません。

そこで、
このプログラムを作成する際の一般的なアルゴリズムを教えていただきたいです。
例えば、どういった法則を使うのか？などです。
具体的であればあるほどありがたいです。

しょぼい質問ですがお願いします。

No.5 回答者： tknakamuri 回答日時： 2012/10/14 18:20

4 x 4 でしたら、固有方程式を直接といたほうが簡単です。

ヤコビとか QR とかは巨大な行列に使う手法です。

ベアストウヒッチコックとかDKAとか、いろいろとやり方があります。

No.4 回答者： tknakamuri 回答日時： 2012/10/05 21:22

肝心なところを書き忘れました。

原理的には QR だけで固有値は求まります。小さな行列ではこれで十分ですが、
数十、数百の大きさの行列では　QR だけでは収束が遅すぎるので、
他の手法(加速処置)との組み合わせが必要です。とんでもなく速くなります。

この回答へのお礼

具体的なところまでありがとうございます。

実際求めたい行列は4✕4の非対称行列なので
QR法のみで大丈夫な気がします。

QR法は初めて聞くアルゴリズムなので
勉強してから実装したいと思います！

実際のところ
Cで組むとしたら大変でしょうか？？

お礼日時：2012/10/06 15:24

No.3 回答者： tknakamuri 回答日時： 2012/10/05 21:16

私が勉強した頃は、非対称行列では

Reduction(ヘッセンベルク化、3重対角化) + QR + 原点移動 + 減次

が定石だったと思います。最近は違っていたらすいません。

Reduction(ヘッセンベルク化、3重対角化) はハウスホルダー法を実装したことが
ありますが、他にもいろいろなやり方があるようです。
＃双ランチョス法とか・・・実装経験なし。対称行列のように3重対角化できるようなので
＃メチャ速いかも。

Reduction で計算量を減らしたあと、QR + 原点移動 + 減次 をセットで行うと
収束が速いようです。

逆にセットでやらないととても遅くなって実用的ではありませんでした。

拙い情報ですが・・・

No.2 回答者： Tacosan 回答日時： 2012/10/05 12:25

条件にもよるけど, べき乗法 (逆べき乗法) や LR法など, いくつかあるよ.

というか, 調査した?

この回答への補足

回答ありがとうございます。

条件は非対称行列である、
すべての固有値を求めたい、
C言語を使いたいぐらいです。

調べて見たところ、
フレーム法+ベアストウ法を用いるものは見つけましたが、
なかなか非対称行列の例題がないため他はわかりませんでした。

そこで
その他にもアルゴリズムがあるのかを知りたくて投稿しました。

言葉足らずですみません。

補足日時：2012/10/05 18:26

No.1 回答者： kamiyasiro 回答日時： 2012/10/05 07:47

企業で統計を扱う部門の者です。

固有値は対称行列しか求めることができません。

非対称行列の固有値を求めたいということは、
ランク落ちに近い、すなわち最小固有値がきわめて0に近い
状態を知りたいのでしょうか。

もし、そうであれば、

rank（A）＝rank（A'A）＝rank（AA'）

という公式がありますので、
それを用いて対称行列にしてから固有値を求めてはどうでしょうか。

この回答へのお礼

回答ありがとうございます。

簡単にいうと近似して求めるということですね。

参考にさせていただきます。

お礼日時：2012/10/05 19:01