n次の線形空間Xにおける、ある線形写像を行列Mで表現したとき、 その固有ベクトルはXの(部分)正規直交系になっている。 この性質を利用した固有値と固有ベクトルの計算方法が 通称 iterative method とか power method とか言われているものであります。
固有ベクトルを{v1, v2,...}としましょう。 Xの適当なベクトル x は、 x=Σc1v1, c2v2, … v0 で表現できます。 {v1, v2..} はXの極大正規直交系とは限らないので、 固有ベクトルで足りない分は v0 にまとめました。 それから、表記の都合上、一番大きな固有値に対応する固有ベクトルをv1、 次をv2とします。
さて、 x の M による行き先を考えましょう。 x は Σc1v1, c2v2, … v0 ですから、 Mx= Σc1Mv1, c2Mv2, … Mv0 です。 v1, v2, ... は全て M の固有ベクトルなので、 これらの分は M で大きさだけが固有値分大きく(あるいは小さく)なり、 方向は変わりません。 v0 は v1, v2, ... と直交なので、固有ベクトルが極大正規直交系であろうが なかろうが、いずれにせよ M による像は0です。
この操作を何回か繰り返したものを考えると、 圧倒的に v1 の貢献が大きくて、あとは雑魚という状態に陥ります。 まさに、教科書どおりな不動点的挙動です。 要するに、何回もその行列をかければ、どこからスタートしても 最大固有値に対応する固有ベクトルに落ち着くわけです。 これならコーディングも超絶に簡単ですね。
計算上、どんどんベクトルが大きく(あるいは小さく)なっていくのは 精度の上でアレですから毎回 x を最大固有値で割ることにすると、 コードは以下のとおりです。 xが適当なベクトル。l が新たな固有値で ol が以前のループで計算した 固有値。eps が収束判定条件を保持する変数です。
while (l - ol).abs/ol > eps
ol=l
y=m*x
l=y.abs / x.abs
x=y/l
end
うっわ。むっちゃ簡単。まじで？ホンマにこれで計算できんのかいな？ と思うでしょ。是非、お手元のお好きな処理系でやってみてください。
演習: 終了条件はどうやって選べば良いだろうか？ また、この手口が通用しない場合を考察し、対策せよ。
さて、これで最大固有値と対応する固有ベクトルが求まったとして、 そうなると次の固有値と固有ベクトルを計算したくなるのが人間というものです。
これは行列のスペクトル分解 (matrix spectral decomposition)と射影子(orthogonal projection)を使うのが 簡単です。
先の行列Mのスペクトル分解を Σl1V1, l2V2, ... とします。 V1, V2 は対応する固有ベクトル空間への射影子です。 最大固有値と固有ベクトルは判明しましたから、最初のスペクトル分解要素は 計算できます。こいつを M から引き算した行列M'を考えましょう。 かつて習った線形代数を未だに忘れてない人にはもう見当がつくと思いますので、 最後の演習に進んで下さい。
(M-l1V1)x = Mx - l1V1x のうち、 l1V1x に注目です。 V1は v1 による部分空間への射影子です。 x-v1 はv1空間の直交補空間に居るので、この成分の射影子による像は0ですから、 V1x = v1 したがって l1V1x = l1v1 です。 Mx の最初の要素は上で見た通り l1v1 なので、 ちょうど l1v1 がキャンセルされて、 l2v2 以下だけが残ります。 つまり、行列 M'= M-l1V1 の最大固有値は M の第二固有値になっています。 あとは行列 M' について上記 iterative method を適用すれば、 第二固有値及び固有ベクトルを計算することができます。
こうやって第k 固有ベクトルを得る方法を Hotelling 法といいます。 これが考案されたのは、案外最近で1933年の事です。Hotellingさんは 著明な経済学者でもあるそうです。
演習: iterative method は所詮、近似計算です。 第k固有値及び固有ベクトルの誤差を見積もろう。
自宅は団地でして、下の階にはマルコフさんという ロシヤ人が住んでいます。
ロシヤのマルコフさんという名を聞いて、 マルコフ連鎖を思い出さぬ人は居ないでしょう。
グラフ上を、偶然に従って適当にうろつくという、 非決定性有限状態機械というものを考えるとしましょう。 このとき、頂点AからBに移動するステップ数の平均値(期待値ともいう)は幾らか？
なんかね、こう、 その値ってそもそも有限なのか？ みたいな疑問がありませんか？ 俺とか、そういうセンスに全然欠けるところがあって、 これが皆目見当がつかんのですわ。白状すると。
ところがどっこい、驚いた事に、 状態遷移行列を使った比較的簡単な一次方程式として、 この問題が解けるんですよ。 mjdsk sugeeeeeee
興味ある人は探してみて下さい。どっか載ってるかも。