固有ベクトルの高速な求め方
- 固有ベクトルの求め方について調査しました。現在の手法では時間がかかるため、高速なアルゴリズムを探しています。
- 現在固有ベクトルを求める手法は遅く、特に大きな行列の場合は時間がかかります。高速なアルゴリズムの開発が望まれます。
- 対称行列の固有ベクトルを効率的に求める方法を探しています。現在の手法では時間がかかるため、高速化のためのアルゴリズムを研究中です。
- ベストアンサー
行列演算: 固有ベクトルの解法
現在、対称行列の固有値、固有ベクトルを求めるプログラムを作成し、つい最近完成しました。 しかし、とても使い物にならないプログラムになってしまいました。 理由はとても遅いのです。 解法の手順として、まず固有値を求めてから固有ベクトルを求めるようと考え、入力の対称行列をHouseHolder法により三重対角行列に変換し、それをQR法により対角化してまず固有値を求めました。 固有値を求めることができたので、次に固有ベクトルを求めます。手順として、固有値ごとに入力対称行列の対角成分から固有値を減算した行列をLU分解し、連立一次方程式を解くように固有ベクトルを求めていきます。 この一連の手順で、対称行列の固有値、固有ベクトルを求めることができたのですが、とても時間がかかってしまいます。 ただし、対称行列の固有値を求めるまでの時間はとても高速です。 500×500の行列の固有値、固有ベクトルを求めるのに30分はかかってしまいますが、その中で固有値を求める時間は2秒しかかかりません。 つまり今固有値がわかっている状態で、固有ベクトルを高速に求めたいと考えています。 なにか高速に固有ベクトルを求める方法(アルゴリズム)はあるでしょうか?
- noconan
- お礼率80% (76/95)
- 数学・算数
- 回答数2
- ありがとう数2
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
一つ気づいたのですが、もしかして500個の固有値を全部求めていませんか?。そうすると全体で30分(1800秒)だとしても、1個あたりなら、ほんの数秒で、かなり優秀なコードと思えます。 ふつうは、低次の固有値・固有ベクトルを重視するので、せいぜい10個,多くて20個と思います。さっきの話が正しいとして、それなら数10秒です。 もし500個の固有値という事であれば、共役勾配法を利用した原点移動付逆ベキ乗法を試すしかないかな?、と思いました。
その他の回答 (1)
PCの性能にもよりますが、500×500の行列のLU分解に30分というのは、遅すぎると思いました。例えばLU分解に無駄はないでしょうか?。1回で済むところを、Loop手順の誤りで、毎回実行しているとか。 LU分解が正当だとして、対称行列ならば、原点移動付逆ベキ乗法があります。 これは具体的には、(A-λE)x=xを繰り返し解く操作に帰着します。det(A-λE)はほぼ0になるので、A-λEの上三角化において0に近い対角成分がみつかったら、それを10^(-10)とかにおきかえて計算を続行します。得られたxのノルムを1に規格化して、これを数回行うと、xはほぼ固有ベクトルに収束します。xの初期値としては、x=(1,1,・・・,1)なんかを選びます。 A-λEの上三角化は、固定したλに対して1回だけ行い、保存して繰り返し使用できます。これはLU分解1回と同じです。 それでも遅い場合には、上三角化のかわりに共役勾配法を利用できます。共役勾配法は非常に高速です。 参考文献: 行列計算ソフトウェア WS、スーパーコン、並列計算機 フロッピーディスク付(3.5inch2HD) 小国 力 編著 発行元:丸善(株)出版事業部 この本は古いですが、工学系の図書館には必ずあると思います。また小国さんの他の著書も参考になります。
お礼
返答遅れてしまって申し訳ありませんでした。 ちょっと質問の文章があいまいでしたね。すみません。 500×500の行列のLU分解に30分かかっているわけではなく、すべての固有値に対応する固有ベクトルを求めるのに30分必要になるという意味です。 詳しいことは2回目の回答のお礼に書きますね^^
関連するQ&A
- 行列の固有ベクトルの解法
現在行列の固有値と固有ベクトルをもとめるプログラムを作成しています。 手順としては、入力行列をハウスホルダー法により三重対角行列に変換し、その後QR法で対角化を行い固有値を求めます。 固有ベクトルはLU分解を使用して固有値ごとに求めていこうと考えました。 現状固有値を求めるプログラムは作成できました(そして正しく求められていることも確認しました)。そして行列のLU分解を行うプログラムまで作成できたのですが、LU分解後の行列から固有ベクトルを求める方法がわかりません。 詳しく説明します Ax = λx を (A - Iλ)x = 0 として、この(A - Iλ)をLU分解しました。 すると式は LUx = 0 となり 最終的に Ux = 0 をとく問題になります。 ここで行列Uは上三角行列なので、1次の連立方程式を解くように、行列Uの右下の要素を使って計算を始めていくのですが、自分がなにか勘違いをしているのだと思うのですがこの方法で計算すると固有ベクトルが全て0になってしまいます。 行列U x 0 | 2 3 4 5 | |x1| = |0| | 0 4 2 9 | |x2| = |0| | 0 0 7 5 | |x3| = |0| | 0 0 0 8 | |x4| = |0| このような図式になり、固有ベクトルであるxを求めていくのですが、x4から順にもとめても0にしかならないんです。 下記のサイトを参考に学んでいたんですが、この部分が分からずにいます。 http://hooktail.org/computer/index.php?KL%C5%B8%B3%AB2 どこを勘違いしているんでしょうか? アドバイスをお願いします。
- ベストアンサー
- 数学・算数
- 固有値問題の解法について
固有値問題を解くプログラムを作りたいと考えています。 対象とする行列は「実対称行列(正方行列)」で、251次の 行列を考えており、この行列の固有値、固有ベクトルを 求めたいです。そこで、現在調べたところ、ヤコビ法、 QR法などがあるのですが、どの方法がより高速に求められる でしょうか。ご教示願いたいと思います。また、上記の方法 よりも高速に求められる解法などありましたら、教えて頂き たいです。宜しくお願いします。
- ベストアンサー
- 数学・算数
- QR法を使った行列の固有値問題について
行列の固有値と固有ベクトルを求めるプログラムをJavaで 作っています。そこで、アルゴリズムとしてQR法を用いて いるのですが、この方法では固有値のみを求めており、 固有ベクトルは求めていないことがわかりました。そこで、 QR法を用いつつ、固有ベクトルも同時に求める方法がありましたら、 教えて頂きたいと思います。宜しくお願いします。
- 締切済み
- 数学・算数
- 行列の固有ベクトルについて質問です
対称行列を対角化するにあたって,対称行列の固有ベクトルについて次のように教科書に記述があります. 「対称行列の異なる固有値に対する固有ベクトルは互いに直交する」 この記述によれば,異なる固有値から得られる固有ベクトルは必ず互いに直交しますが,固有値が重解となったときに同じ固有値から2つの固有ベクトルが得られる問題がありました. このとき,この得られた2つの固有ベクトルは互いに直交していないのでしょうか? つまり,「同じ固有値から得られた固有ベクトルは絶対に直交しない」のでしょうか? わかりにくい質問ですが,どなたか詳しい回答よろしくお願いします.
- 締切済み
- 数学・算数
- 固有値と固有ベクトルが既知のときの行列
3次の正方行列 A について次の条件が成り立つとする. | 1| | 0| |-1| は固有値 1 の固有ベクトルである. | 1| |-1| | 0| は固有値 -1 の固有ベクトルである. |2| |0| |1| は固有値 0 の固有ベクトルである. このとき以下の問に答えよ. (1) A を求めよ. (2) A を対角化する行列 P と対角行列 P^-1AP を求めよ. (2)は固有ベクトルをPとすれば,1次独立だからPが正則となり答えが分かるのですが,(1)をどのように出すか分かりません.ご教授お願いします.
- ベストアンサー
- 数学・算数
- 行列の固有値、及び直交化問題
(1)対称行列の固有値は、なぜ実数なのですか? (2)対称行列を対角化する行列は、直交するベクトルで構成された行列に限られるのでしょうか?だとしたら、それはなぜですか?
- ベストアンサー
- 数学・算数
- 3×3行列の固有値と固有ベクトル
以下の行列Aの固有ベクトルを求めようとしているのですが,解を見つけられないでいます. 2 1 0 1 2 0 0 0 -2 計算を進めた結果,固有値λは3,1,-2となり,λ=3,1に対応する固有ベクトルはそれぞれ[1,1,0]t,[1,-1,0]tとなったのですが,λ=-2の場合で求めた固有ベクトル[1,1,k]t(kは任意の実数)がAx=λxに対応しない値になってしまいます.私の計算に何か問題があるのでしょうか? また,行列Aは対称行列なのでそれぞれの固有ベクトルの内積は0になると思うのですが,固有ベクトルの値が得られないことと何か関係があるのでしょうか? 回答よろしくお願いします.
- ベストアンサー
- 数学・算数
お礼
あらためて、返答ありがとうございました。 ddtddtddtさんがおっしゃられた通り、500個のすべての固有値を求めています。 それは特異値分解、主成分分析といわれる手法ではすべての固有値と固有ベクトルが必要だからです。そして自分は今大学でその研究をしているからです。 固有値を求めるプログラムは正直自分でも驚くほど高速に求めることができました。固有値を高速に求めるにはQR法を高速に処理する問題になりますが、大概の専門書でのプログラムにおいて、そのなかで計算しなくてもよい部分を発見したため、それにより高速に求めることができました。しかも計算しなくてよい部分は行列の大きさの大体を占めているため、とても高速になります。 アルゴリズム自体は変わらないんですがね。 固有値を求めた後、ひとつの固有値に対してLU分解を行い固有ベクトルを求めますが、固有ベクトルは並列的に計算が可能なため、CPUをフルに活用することができます。 自分のPC環境は Xeon 2.8GHz ですので、シングルコアのマルチスレッディングで2スレッドで計算を行いました。 紹介していただいた参考書、および「共役勾配法を利用した原点移動付逆ベキ乗法」を試してみたいと思います。 ありがとうございました^^