数学ガール第4巻『数学ガール/乱択アルゴリズム』と数学ガール1巻の「フィボナッチ数の一般項」を読んでいて,フィボナッチ数列を行列のべき乗で求められるんじゃ無いかと思って試してみた

前提

  • フィボナッチ数p_nの定義
    • p_0=0
    • p_1=1
    • p_{n+2}=p_n+p_{n+1}(n\ge0)

行列

  • 行列\rm{A}=\left(\begin{array}{cc}1&1\\1&0\\\end{array}\right)なる行列がある
  • この行列のべき乗\rm{A}^n=\left(\begin{array}{cc}p_{n+1}&p_n\\p_n&p_{n-1}\\\end{array}\right)となっている(詳しくは数学ガール4巻『数学ガール/乱択アルゴリズム』を参照)
  • \rm{A}=\left(\begin{array}{cc}1&1\\1&0\\\end{array}\right)\rm{A}^2=\left(\begin{array}{cc}2&1\\1&1\\\end{array}\right)\rm{A}^3=\left(\begin{array}{cc}3&2\\2&1\\\end{array}\right)\rm{A}^4=\left(\begin{array}{cc}5&3\\3&2\\\end{array}\right)\rm{A}^5=\left(\begin{array}{cc}8&5\\5&3\\\end{array}\right)
  • という具合に,各行列のべき乗の左下と右上の要素がフィボナッチ数になっている

問題

  • 行列\rm{A}のべき乗\rm{A}^nからフィボナッチ数列の一般項を導出せよ

対角化

  • \rm{A}=\rm{P}\rm{D}\rm{P}^{-1}と分解する*1
  • ケーリー・ハミルトンの定理より,|\rm{A}-\lambda \rm{E}|=0
  • |\rm{A}-\lambda \rm{E}|=|\left(\begin{array}{cc}1-\lambda&1\\1&-\lambda\\\end{array}\right)|=(1-\lambda)(-\lambda)-1=\lambda^2-\lambda-1=0
  • \lambda=\frac{1\pm \sqrt{1-4(-1)}}{2}=\frac{1+ \sqrt{5}}{2},\frac{1- \sqrt{5}}{2}
  • ここで\alpha = \frac{1+ \sqrt{5}}{2},\beta =\frac{1- \sqrt{5}}{2}とする
  • \left(\rm{A}-\lambda \rm{E}\right)\left(\begin{array}{c}x\\y\end{array}\right)=\rm{0}となるベクトル\left(\begin{array}{c}x\\y\end{array}\right)を考える
  • \lambda=\alphaのとき
    • \left(\rm{A}-\alpha \rm{E}\right)\left(\begin{array}{c}x\\y\end{array}\right)=\left(\begin{array}{cc}1-\alpha&1\\1&-\alpha\\\end{array}\right)\left(\begin{array}{c}x\\y\end{array}\right)=\rm{0}より\left(\begin{array}{c}x\\y\end{array}\right)=\left(\begin{array}{c}\alpha\\1\end{array}\right)
  • \lambda=\betaのとき
    • \left(\rm{A}-\beta \rm{E}\right)\left(\begin{array}{c}x\\y\end{array}\right)=\left(\begin{array}{cc}1-\beta&1\\1&-\beta\\\end{array}\right)\left(\begin{array}{c}x\\y\end{array}\right)=\rm{0}より\left(\begin{array}{c}x\\y\end{array}\right)=\left(\begin{array}{c}\beta\\1\end{array}\right)
  • これで行列\rm{A}の固有値\alpha, \betaと固有ベクトルがもとまった.よって
    • \rm{P}=\left(\begin{array}{cc}\alpha&\beta\\1&1\\\end{array}\right)
  • \rm{D}=\left(\begin{array}{cc}\alpha&0\\0&\beta\\\end{array}\right)
  • として,以下のように表せる
  • \rm{A}=\rm{P}\rm{D}\rm{P}^{-1}=\left(\begin{array}{cc}\alpha&\beta\\1&1\\\end{array}\right)\left(\begin{array}{cc}\alpha&0\\0&\beta\\\end{array}\right)\left(\begin{array}{cc}1&-\beta\\-1&\alpha\\\end{array}\right)\frac{1}{\sqrt{5}}
  • 真ん中のDが対角化(=斜めの成分以外が全部0に)できた

べき乗

  • \rm{A}^nを考える
  • \rm{A}^n=\left(\rm{P}\rm{D}\rm{P}^{-1}\right)^n=\rm{P}\rm{D}\rm{P}^{-1}\rm{P}\rm{D}\rm{P}^{-1}\cdots\rm{P}\rm{D}\rm{P}^{-1}=\rm{P}\rm{D}\rm{E}\rm{D}\rm{E}\cdots\rm{E}\rm{D}\rm{P}^{-1}=\rm{P}\rm{D}^n\rm{P}^{-1}
  • \rm{P}\rm{P}^{-1}が打ち消しあってくれるため
  • 展開する
    • \rm{A}^n=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha&\beta\\1&1\\\end{array}\right)\left(\begin{array}{cc}\alpha&0\\0&\beta\\\end{array}\right)^n\left(\begin{array}{cc}1&-\beta\\-1&\alpha\\\end{array}\right)
  • =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha&\beta\\1&1\\\end{array}\right)\left(\begin{array}{cc}\alpha^n&0\\0&\beta^n\\\end{array}\right)\left(\begin{array}{cc}1&-\beta\\-1&\alpha\\\end{array}\right)
  • =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}&\beta^{n+1}\\\alpha^n&\beta^n\\\end{array}\right)\left(\begin{array}{cc}1&-\beta\\-1&\alpha\\\end{array}\right)
  • =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}-\beta^{n+1}&\beta^{n+1}\alpha-\alpha^{n+1}\beta\\\alpha^n-\beta^n&\beta^n\alpha-\alpha^n\beta\\\end{array}\right)
  • 2列目(右側)がごちゃごちゃしてるので,もう少し整理する
    • \frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}-\beta^{n+1}&\beta^{n+1}\alpha-\alpha^{n+1}\beta\\\alpha^n-\beta^n&\beta^n\alpha-\alpha^n\beta\\\end{array}\right)
  • =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}-\beta^{n+1}&\alpha\beta(\beta^n-\alpha^n)\\\alpha^n-\beta^n&\alpha\beta(\beta^{n-1}-\alpha^{n-1})\\\end{array}\right)(\alpha\betaで括った)
  • =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}-\beta^{n+1}&\alpha^n-\beta^n\\\alpha^n-\beta^n&\alpha^{n-1}-\beta^{n-1}\\\end{array}\right)(\alpha\beta=-1)より

恒等式

  • 最初,行列\rm{A}のべき乗\rm{A}^n=\left(\begin{array}{cc}p_{n+1}&p_n\\p_n&p_{n-1}\\\end{array}\right)から始めて,
  • \rm{A}^n=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}-\beta^{n+1}&\alpha^n-\beta^n\\\alpha^n-\beta^n&\alpha^{n-1}-\beta^{n-1}\\\end{array}\right)にたどり着いた
  • 両方を比較すると,
    • \left(\begin{array}{cc}p_{n+1}&p_n\\p_n&p_{n-1}\\\end{array}\right)=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\alpha^{n+1}-\beta^{n+1}&\alpha^n-\beta^n\\\alpha^n-\beta^n&\alpha^{n-1}-\beta^{n-1}\\\end{array}\right)
  • 次式が導かれる
  • p_n=\frac{1}{\sqrt{5}}\left(\alpha^n-\beta^n \right)
  • 今,\alpha = \frac{1+ \sqrt{5}}{2},\beta =\frac{1- \sqrt{5}}{2}としたので,
  • p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}

感想

  • 4巻面白かった
    • きっかけは4巻と間違えた1巻を手にとってしまったこと
    • 1巻ではフィボナッチ数列の一般項の話が出てくる
    • 4巻でフィボナッチ数列を表す行列が出てきたとき,「あれ?」と思って挑戦してみた
  • テトラちゃんじゃないけれど,「例示は理解の試金石」で試しに行列の対角化に挑戦したが,高校で習ったこと全然覚えてなくて愕然・・・
  • 行列の対角化は高校で習ったので,この行列を見たら,高校生の時にフィボナッチ数列の一般項を求められたことになる
    • 数学って奥が深い・・・
  • やっぱり,数学ガールは読んで面白いけれど,自分で手を動かすとなおのこと面白い
  • 特に,4巻はオーダ記法とかクーポン収集問題*2とか,扱ってる範囲が自分的にツボな所だけれで,本当に面白かった
  • ちゃんと導出できてよかった

:数学


*1 対角化の細かい原理は学ガール4巻『数学ガール/乱択アルゴリズム』を参照
*2 連チャン回数の期待値お試しかっ!帰れま10で食べる皿の期待値はクーポン収集問題の変形した問題

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-03-23 (水) 09:16:36 (2439d)