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

質問

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

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

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

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

回答No.5

中村 拓男（@tknakamuri）

4 x 4 でしたら、固有方程式を直接といたほうが簡単です。
ヤコビとか QR とかは巨大な行列に使う手法です。

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

回答No.4

中村 拓男（@tknakamuri）

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

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

お礼

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

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

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

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

回答No.3

中村 拓男（@tknakamuri）

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

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

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

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

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

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

拙い情報ですが・・・

回答No.2

Tacosan

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

というか, 調査した?

補足

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

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

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

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

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

回答No.1

kamiyasiro

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

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

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

もし、そうであれば、

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

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

お礼

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

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

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