Monday, December 24, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (22)

How to compute the eigenvectrors?

これまで,固有ベクトルがどのようなものかは説明してきたが,計算方法については述べてこなかった.実際に固有値ベクトルをどう計算するかのアルゴリズムはここでは述べず,既にあるフリーソフうウェアを使うことにする.octave では eig という関数が教えてくれるのでこれを使おう.

計算してみよう.

octave:34> [L V] = eig(M)
L =
   0.83205  -0.70711
   0.55470   0.70711
V =
Diagonal Matrix
   1.00000         0
         0   0.50000
以前私は固有値が matrix と同じに見えると言った.確かにそうであるが,一つの数字で matrix を完全に表すことはできない.もしできるのならば,matrixは不要になってしまう.実は通常の matrix は複数の固有値と複数の固有ベクトルを持つ.それでも matrix の要素の数 \(n^2\) に比較して \(n\) しか固有値は存在しないのでかなり簡単になる.

この Matrix の固有値は 1 と 0.5, 対応する固有ベクトルは (0.83205,0.55470) と (-0.70711, 0.70711) である.ここでは 0.5 の固有値は無視する.なぜなら,この固有値は Markov matrix がどのように収束するかついては教えてくれないからである.詳しく知りたい読者は Matrix diagonalization について調べてみて欲しい.固有値が 1 の固有ベクトルが,Markov matrix がどのような値に収束するのかを教えてくれる.それを計算して,総人口1000 人の分布を見ると以下のようになる.
octave:38> x1 = L(:,1)/ sum(L(:,1))
   0.60000
   0.40000
octave:39> x1 * 1000
   600
   400
これは前節の結果と一致する.何が違うかというと,固有値を求める方法では,M を 100回掛ける必要がないということである.この位小さな行列では計算機で計算すると計算時間にあまり違いはでてこないが,大規模な行列を扱う場合にはそうではない.その場合には固有値と固有ベクトルを求める効率的な手法が知られているので,それを利用することになるだろう.


次回は隣接行列から Markov 行列を生成する方法について述べよう.駅のネットワークの例では,これによってどの駅にいる可能性が高いのかを計算することができる.そしてそれは実は著者のネットワークの評価と同じである.理論編も大詰めになってきたようだ.


No comments:

Post a Comment