ヤコビ法とQR法について

質問

現在固有値問題を解いているのですが、ヤコビ法とQR法とでは
どちらがどれくらい計算が速いでしょうか？
解こうとしている行列は最小で1000×1000で、精度を良くする
ために5000×5000程度の行列で解こうと思っています。
どなたか教えていただければ幸いです。お願いします。

回答No.1

stomachman · ベストアンサー

n×n行列Aの固有値問題。
困り度３ということですから、中途半端ながらres付けてしまいます。

ヤコビ法は大きいnには手間が大きくて辛いでしょうね。
QR法が便利だけれど、一手間掛けまして、原点を移動する。つまり狙いの固有値を絶対値≒0になるように座標変換しておいてからQR法を使うのが旨いやり方だと思います。つまり予想される値μを使って、Aの代わりにA-μI の固有値を求めて、得られた答えにμを加えればよい。

反復計算で固有値と固有ベクトルを求める段階では、固有値の絶対値同士がどのぐらい散らばっているかによって計算の手間が全然違う。絶対値の順に固有値を並べた時、隣り合う固有値の比が1に近いと手間が掛かります。固有値が一個ずつ出てくるのを使って問題を減次するのも、nが大きいときには結構な手間です。なかなか一概には論じきれないな。

また固有値と固有ベクトルの近似値μ,vを改良するという仕上げは欠かせません。つまり
(A-μI)x = v
を解いてxを求め、改良された固有ベクトルの近似値xと、固有値の近似値(Ax)[j]/x[j]を求める。これを繰り返します。（これは最初の近似が良ければ凄く速く収束します）。QR法はこの計算にも向いてます。

スパースな行列（つまり零要素が殆ど、という場合）だと、また話が違うようです。

いずれにせよ、誤差の累積が怖いので、計算の精度（有効桁数）を変えて２度計算し、両者の結果が一致することを確認すべきです。もし食い違うようなら、有効桁数が足りない訳です。

お礼

とても有用なご回答ありがとうございます。
もう少しいろいろ調べながらやっていこうと思います。
ありがとうございました。

回答No.2

stomachman

大きい固有値だけに限って求められれば十分、という応用が沢山あります。また、制御工学では不安定な固有値成分だけ取り出したい。そういう場合どうするのか、ちょっと調べてみたら
「ランチョス法に、等角写像を組み合わせる。」
というテクニックがあるみたいです。
等角写像
y = (x+c) / (x-c) （x,yは複素数、cは適当な正の定数）
によって、不安定なやつを単位円の外に、安定な奴を単位円の中に写像しておいて、ランチョス法（絶対値が大きい固有値から順に出てきます）を適用するらしい。
　まだ調査中ですが、お急ぎのようなのでとりあえず。