フィボナッチ数列(Fibonacci numbers)の行列表現
フィボナッチ数列
$$
\begin{eqnarray}
a_{n+1}=a_{n}+a_{n-1}\;\cdots\;ただしa_{1}=1,\;a_{2}=1\\
\end{eqnarray}
$$
これを行列で表現すると以下となる．
$$
\begin{eqnarray}
\left(
\begin{array}{cc}
a_{n+1}\\
a_{n}\\
\end{array}
\right)
&=&
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0 \\
\end{array}
\right]
\left(
\begin{array}{cc}
a_{n}\\
a_{n-1}\\
\end{array}
\right)\\
\vec{a}_{(n+1),n}
&=&\mathrm{A}\vec{a}_{n, (n-1)}\\
\end{eqnarray}
$$
フィボナッチ数列の一般項
\(\vec{a}_{n, (n-1)}\)を\(\mathrm{A}\)の固有ベクトル\(\vec{x}_{1,2}\)を用い表せれば，
上式は対応する固有値\(\lambda_{1,2}\)を用いて以下のように表すことができる．
$$
\begin{eqnarray}
\vec{a}_{(n+1),n}
&=&\mathrm{A}\vec{a}_{n, (n-1)}\\
&=&\mathrm{A}\left(C_1\vec{x}_{1}+C_2\vec{x}_{2}\right)
\;\cdots\;C_1,C_2は定数\\
&=&C_1\mathrm{A}\vec{x}_{1}+C_2\mathrm{A}\vec{x}_{2}\\
&=&C_1\lambda_1\vec{x}_{1}+C_2\lambda_2\vec{x}_{2}
\;\cdots\;\mathrm{A}\vec{x}=\lambda \vec{x}\;\cdots\;固有値・固有ベクトルの定義\\
\end{eqnarray}
$$
またこれを繰り返すことで一般項として以下のように表せることになる．
$$
\begin{eqnarray}
\vec{a}_{(n+1),n}
&=&\mathrm{A}^n \vec{a}_{init}\;\cdots\;\vec{a}_{init}は固有ベクトルの和で表された初期条件を満たす定数C_1,C_2を含むベクトル\\
&=&\mathrm{A}^n\left(C_{\vec{a}_{init}1}\vec{x}_{1}+C_{\vec{a}_{init}2}\vec{x}_{2}\right)\\
&=&C_{\vec{a}_{init}1}\mathrm{A}^n\vec{x}_{1}+C_{\vec{a}_{init}2}\mathrm{A}^n\vec{x}_{2}\\
&=&C_{\vec{a}_{init}1}\lambda_1^n\vec{x}_{1}+C_{\vec{a}_{init}2}\lambda_2^n\vec{x}_{2}\\
\end{eqnarray}
$$
そこでまず\(\mathrm{A}\)の固有値を求める．
$$
\begin{eqnarray}
|\mathrm{A}-\lambda \mathrm{E}|&=&0\\
\left|\left[
\begin{array}{cc}
1 & 1 \\
1 & 0 \\
\end{array}
\right]
-\lambda
\left[
\begin{array}{cc}
1 & 0 \\
0 & 1 \\
\end{array}
\right]\right|
&=&\\
\left|
\begin{array}{cc}
1-\lambda & 1 \\
1 & -\lambda \\
\end{array}
\right|
&=&\\
(1-\lambda)(-\lambda)-1
&=&\\
\lambda^2-\lambda-1&=&\\
\lambda&=&\frac{-(-1)\pm\sqrt{(-1)^2-4\;(1)\;(-1)}}{2\;(1)}\\
&=&\frac{1\pm\sqrt{5}}{2}\\
\lambda_1,\lambda_2&=&\frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}\;\cdots\;ここでは\lambda_1\gt\lambda_2とする．
\end{eqnarray}
$$
\(\lambda_1\)に対応する固有値ベクトル\(\vec{x_1}\)を求める．
$$
\begin{eqnarray}
\left(\mathrm{A}-\lambda_1 \mathrm{E}\right)\vec{x_1}&=&\vec{0}\\
\left[
\begin{array}{cc}
1-\lambda_1 & 1 \\
1 & -\lambda_1 \\
\end{array}
\right]
\left(
\begin{array}{cc}
x_{11}\\
x_{12}\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
0\\
0\\
\end{array}
\right)\\
\left[
\begin{array}{cc}
1-\frac{1+\sqrt{5}}{2} & 1 \\
1 & -\frac{1+\sqrt{5}}{2} \\
\end{array}
\right]
\left(
\begin{array}{cc}
x_{11}\\
x_{12}\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
0\\
0\\
\end{array}
\right)\\
\left[
\begin{array}{cc}
\frac{1-\sqrt{5}}{2} & 1 \\
1 & -\frac{1+\sqrt{5}}{2} \\
\end{array}
\right]
\left(
\begin{array}{cc}
x_{11}\\
x_{12}\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
0\\
0\\
\end{array}
\right)\\
\end{eqnarray}
$$
$$
\left\{\begin{align}
\frac{1-\sqrt{5}}{2}x_{11}+x_{12}&=&0\\
x_{11}-\frac{1+\sqrt{5}}{2}x_{12}&=&0\\
\end{align}\right.\\
$$
$$
\begin{eqnarray}
x_{11}&=&\frac{1+\sqrt{5}}{2}x_{12}\\
\vec{x}_1&=&t\left(
\begin{array}{cc}
\frac{1+\sqrt{5}}{2}\\
1\\
\end{array}
\right)\;\cdots\;t:任意の実数\\
\end{eqnarray}
$$
同様に\(\lambda_2\)に対応する固有値ベクトル\(\vec{x_2}\)を求める．
$$
\begin{eqnarray}
\left(\mathrm{A}-\lambda_2 \mathrm{E}\right)\vec{x_2}&=&\vec{0}\\
\left[
\begin{array}{cc}
1-\lambda_2 & 1 \\
1 & -\lambda_2 \\
\end{array}
\right]
\left(
\begin{array}{cc}
x_{21}\\
x_{22}\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
0\\
0\\
\end{array}
\right)\\
\left[
\begin{array}{cc}
1-\frac{1-\sqrt{5}}{2} & 1 \\
1 & -\frac{1-\sqrt{5}}{2} \\
\end{array}
\right]
\left(
\begin{array}{cc}
x_{21}\\
x_{22}\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
0\\
0\\
\end{array}
\right)\\
\left[
\begin{array}{cc}
\frac{1+\sqrt{5}}{2} & 1 \\
1 & -\frac{1-\sqrt{5}}{2} \\
\end{array}
\right]
\left(
\begin{array}{cc}
x_{21}\\
x_{22}\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
0\\
0\\
\end{array}
\right)\\
\end{eqnarray}
$$
$$
\left\{\begin{align}
\frac{1+\sqrt{5}}{2}x_{21}+x_{22}&=&0\\
x_{21}-\frac{1-\sqrt{5}}{2}x_{22}&=&0\\
\end{align}\right.\\
$$
$$
\begin{eqnarray}
x_{21}&=&\frac{1-\sqrt{5}}{2}x_{22}\\
\vec{x}_2&=&t\left(
\begin{array}{cc}
\frac{1-\sqrt{5}}{2}\\
1\\
\end{array}
\right)\;\cdots\;t:任意の実数\\
\end{eqnarray}
$$
よって前述の表現は以下のように書き換えられる．
$$
\begin{eqnarray}
\left(
\begin{array}{cc}
a_{n+1}\\
a_{n}\\
\end{array}
\right)
&=&
C_{\vec{a}_{init}1}\lambda_1^n\vec{x}_1
+C_{\vec{a}_{init}2}\lambda_2^n\vec{x}_2\\
&=&
C_{\vec{a}_{init}1}\left(\frac{1+\sqrt{5}}{2}\right)^n\left(
\begin{array}{cc}
\frac{1+\sqrt{5}}{2}\\
1\\
\end{array}
\right)
+C_{\vec{a}_{init}2}\left(\frac{1-\sqrt{5}}{2}\right)^n\left(
\begin{array}{cc}
\frac{1-\sqrt{5}}{2}\\
1\\
\end{array}
\right)\\
\end{eqnarray}
$$
\(n=1\)の時，\(a_n=a_1=1, a_{n+1}=a_{1+1}=a_2=1\)なので，ここから\(C_{\vec{a}_{init}1},C_{\vec{a}_{init}2}\)を求める．
$$
\begin{eqnarray}
C_{\vec{a}_{init}1}\left(\frac{1+\sqrt{5}}{2}\right)^1\left(
\begin{array}{cc}
\frac{1+\sqrt{5}}{2}\\
1\\
\end{array}
\right)
+C_{\vec{a}_{init}2}\left(\frac{1-\sqrt{5}}{2}\right)^1\left(
\begin{array}{cc}
\frac{1-\sqrt{5}}{2}\\
1\\
\end{array}
\right)
&=&\left(
\begin{array}{cc}
1\\
1\\
\end{array}
\right)\\
\end{eqnarray}
$$
簡単のために以下のようにひとまず置き直す．
$$
\begin{eqnarray}
C_1&:&C_{\vec{a}_{init}1}\\
C_2&:&C_{\vec{a}_{init}2}\\
\alpha_1&:&\frac{1+\sqrt{5}}{2}\\
\alpha_2&:&\frac{1-\sqrt{5}}{2}\\
\end{eqnarray}
$$
上記で書き直す．
$$
\begin{eqnarray}
C_1\left(\lambda_1\right)^1\left(
\begin{array}{cc}
\alpha_1\\
1\\
\end{array}
\right)
+C_2\left(\lambda_2\right)^1\left(
\begin{array}{cc}
\alpha_2\\
1\\
\end{array}
\right)
=\left(
\begin{array}{cc}
1\\
1\\
\end{array}
\right)\\
\end{eqnarray}
$$
行ごとに書き出すと以下のような連立方程式となる．
$$
\left\{\begin{align}
C_1\lambda_1\alpha_1+C_2\lambda_2\alpha_2&=&1\\
C_1\lambda_1+C_2\lambda_2&=&1
\end{align}\right.\\
$$
\(C_1\)について解く．
$$
\begin{eqnarray}
C_1\lambda_1\alpha_2+C_2\lambda_2\alpha_2&=&\alpha_2\;\cdots\;連立方程式の二つ目の式に\alpha_2を掛ける\\
\left(C_1\lambda_1\alpha_1+C_2\lambda_2\alpha_2\right)-\left(C_1\lambda_1\alpha_2+C_2\lambda_2\alpha_2\right)
&=&\left(1\right)-\left(\alpha_2\right)\;\cdots\;連立方程式の一つ目の式より上式を引く\\
C_1\lambda_1\alpha_1-C_1\lambda_1\alpha_2&=&1-\alpha_2\\
C_1\lambda_1\left(\alpha_1-\alpha_2\right)&=&1-\alpha_2\\
C_1\lambda_1\left(\alpha_1-\alpha_2\right)&=&\alpha_1\;\cdots\;1-\alpha_2=1-\frac{1-\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}=\alpha_1\\
C_1&=&\frac{\alpha_1}{\lambda_1\left(\alpha_1-\alpha_2\right)}=\frac{\frac{1+\sqrt{5}}{2}}{\frac{1+\sqrt{5}}{2}\left(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\right)}\\
&=&\frac{1}{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}=\frac{1}{\frac{2\sqrt{5}}{2}}=\frac{1}{\sqrt{5}}\\
\end{eqnarray}
$$
\(C_2\)について解く．
$$
\begin{eqnarray}
C_1\lambda_1\alpha_1+C_2\lambda_2\alpha_1&=&\alpha_1\;\cdots\;連立方程式の二つ目の式に\alpha_1を掛ける\\
\left(C_1\lambda_1\alpha_1+C_2\lambda_2\alpha_2\right)-\left(C_1\lambda_1\alpha_1+C_2\lambda_2\alpha_1\right)
&=&\left(1\right)-\left(\alpha_1\right)\;\cdots\;連立方程式の一つ目の式より上式を引く\\
C_2\lambda_2\alpha_2-C_2\lambda_2\alpha_1&=&1-\alpha_1\\
C_2\lambda_2\left(\alpha_2-\alpha_1\right)&=&1-\alpha_1\\
C_2\lambda_2\left(\alpha_2-\alpha_1\right)&=&\alpha_2\;\cdots\;1-\alpha_1=1-\frac{1+\sqrt{5}}{2}=\frac{1-\sqrt{5}}{2}=\alpha_2\\
C_2&=&\frac{\alpha_2}{\lambda_2\left(\alpha_2-\alpha_1\right)}=\frac{\frac{1-\sqrt{5}}{2}}{\frac{1-\sqrt{5}}{2}\left(\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}\right)}\\
&=&\frac{1}{\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}}=\frac{1}{-\frac{2\sqrt{5}}{2}}=-\frac{1}{\sqrt{5}}\\
\end{eqnarray}
$$
以上よりフィボナッチ数列の一般項\(a_n\)は以下のように表すことができた．
$$
\begin{eqnarray}
a_n&=&C_1\lambda_1^n+C_2\lambda_2^n\\
&=&\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\\
\end{eqnarray}
$$
\(a_{n+1}\)側の式は以下のようになり, \(n+1\)を改めて\(n\)と置き直せば上式と同じになる．
$$
\begin{eqnarray}
a_{n+1}&=&C_1\lambda_1^n\alpha_1+C_2\lambda_2^n\alpha_2\\
&=&\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\frac{1+\sqrt{5}}{2}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\frac{1-\sqrt{5}}{2}\\
&=&\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\\
\end{eqnarray}
$$
0 件のコメント:
コメントを投稿