行列のべき乗とフィボナッチ数列 - AkiWiki

[ トップ ] [ 編集 | 凍結 | 差分 | バックアップ | 添付 | リロード ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

最新の20件

2018-10-23

Jetson TX2でOpenCV4.0.0をビルド

2018-10-01

OpenCV4.0のビルド

2018-08-30

xのx乗

2018-08-21

gnuplotメモ

2018-08-20

vim

2018-07-25

C/C++のトラブル集

2018-07-13

IC乗車券/おさいふケータイ

2018-05-28

割って7余るn

2018-04-27

Arm

2018-04-24

OpenCVの環境変数

2018-04-17

Firefly RK3399

2018-04-12

2018-04-10

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

前提 †

フィボナッチ数 $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)$ となっている(詳しくは数学ガール４巻『数学ガール／乱択アルゴリズム』を参照)

$\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 対角化の細かい原理は学ガール４巻『数学ガール／乱択アルゴリズム』を参照
*2 連チャン回数の期待値やお試しかっ！帰れま10で食べる皿の期待値はクーポン収集問題の変形した問題

Last-modified: 2011-03-23 (水) 09:16:36 (2795d)