はじめに
フィボナッチ数列の漸化式は、隣接する2つの項の和が次項となる特殊な3項漸化式を用いてシンプルに表すことができる。ただし、それの一般項は少し複雑な形をしていて、導出も少し面倒である。高校生なら、特性方程式を用いた解法を駆使することでかろうじて解くことができる。しかし、行列を用いた解法の方が計算は少し複雑になるが、応用性が高く解法の方針も極めてシンプルである。そこで今回は計算機を用いて、フィボナッチ数列の各項を計算し、隣接する項の比を計算し、その値が黄金比に収束することを確認する。以下、簡単に計算結果の概要を述べる。
理論計算
3項間漸化式を行列の形に変換し、行列の累乗を対角化を用いて求めることで、一般項（理論解）を求めることができる。これを利用して、一般項を計算機により計算した。
数値計算
3項間漸化式を行列の形に変換し、数値計算を行った。
問題設定
以下の3項間漸化式を行列を用いて解くことを考える。
\begin{cases}
a_{n+2}=a_{n+1}+a_{n} (n\ge 1)\\
a_1=a_2=1 \\
\end{cases}
さて、これを行列の形に変換する。
\begin{pmatrix}
a_{n+2} \\
a_{n+1}\\
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n+1} \\
a_{n}\\
\end{pmatrix}
ここで、上式を以下のように表す。ただし、
\vec{p}_{n+1}=A \vec{p}_{n}
\vec{p}_{n}
=
\begin{pmatrix}
a_{n+1} \\
a_{n}\\
\end{pmatrix}
,A=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
とする。
一般項を行列で表現
上式の漸化式から$\vec{p}_{n}$を行列$A$を用いて表す。
\vec{p}_{n}=A^{n-1}\vec{p}_{1}
ただし、等比数列の一般項の公式を用いた。
行列の対角化と累乗計算
上式より明らかな通り、$A^{n-1}$という行列$A$の累乗を求めることができれば、今回の漸化式の一般項を知ることができる。そこで、行列$A$について対角化のために固有値および固有ベクトルを求める。ただし、理由については後半で説明する。
固有値の導出
突然だが、固有値とは、以下の式を満たす数値のことをいう。
A \vec{q}= \lambda \vec{q}
ただし、$\vec{q}$は、行列$A$の固有ベクトルという。
この式から分かる通り、$A$により固有ベクトルを変換したとしても、なんと向きは不変で大きさだけ元の固有ベクトル$\vec{q}$の$\lambda$倍となる。
さて、上記の方程式を解くことを考える。
まず、
A \vec{q}- \lambda \vec{q}=\vec{0}
と移項する。次に、ここがテクニカルなのだが、左辺を$\vec{q}$で括るために、$A$と$\lambda$を同じ'型'にする必要性がでてくる。つまり、$\lambda$を$\lambda E$ ($E$は単位行列)として以下のような式に変形すると以下のようになる。
(A- \lambda E) \vec{q} =\vec{0}
ここで、
|A- \lambda E|=0
となる場合はクラメルの公式で解くことはできない。なぜなら、上式は解を無数に持ってしまうからである。
つまり、非自明な解（ゼロベクトル以外）を持つ。これが固有ベクトルである。
そこで、
A=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
であることから、
|A- \lambda E|=0
は、以下のように表すことができる。
\begin{vmatrix}
1-\lambda & 1 \\
1 & 0-\lambda
\end{vmatrix}
=0
これは、
\lambda^2-\lambda-1=0
となるため、
上の2次方程式の解は2つ存在し、以下のようになる。
\lambda_1=\frac{1+\sqrt{5}}{2},\lambda_2=\frac{1-\sqrt{5}}{2}
固有ベクトルの導出
\begin{pmatrix}
1 -\lambda & 1 \\
1 & 0-\lambda
\end{pmatrix}
\begin{pmatrix}
q_1 \\
q_2
\end{pmatrix}
=
\begin{pmatrix}
0 \\
0
\end{pmatrix}
を満たす固有ベクトル
\vec{q}
=
\begin{pmatrix}
q_1 \\
q_2
\end{pmatrix}
を求める。
そこで、求める固有ベクトルの1つとして、以下を挙げることができる。
\vec{q}
=
\begin{pmatrix}
\lambda \\
1
\end{pmatrix}
したがって、
\vec{q_1}
=
\begin{pmatrix}
\lambda_1 \\
1
\end{pmatrix}
,
\vec{q_2}
=
\begin{pmatrix}
\lambda_2 \\
1
\end{pmatrix}
対角化
ここで、
P=(\vec{q}_1,\vec{q}_2)
とすると、
AP=(A\vec{q}_1,A\vec{q}_2)=(\lambda_1\vec{q}_1,\lambda_2 \vec{q}_2)
ここで、
P^{-1}=
\begin{pmatrix}
p_{a1}&p_{a2} \\
p_{b1}&p_{b2}
\end{pmatrix}
とする。
P^{-1}AP=P^{-1}(A\vec{q}_1,A\vec{q}_2)=P^{-1}(\lambda_1\vec{q}_1,\lambda_2 \vec{q}_2)=
\begin{pmatrix}
\lambda_{1}&0 \\
0&\lambda_{2}
\end{pmatrix}
=D
したがって、対角化ベクトル$D$を用いると
A=PDP^{-1}
となる。
一般項の導出
行列の累乗について
行列$A$の対角化行列$D$の累乗は比較的平易に以下のように表すことができる。ただし、証明は帰納法で簡単にできるので、是非やってみてほしい。
D^{n}=
\begin{pmatrix}
\lambda_{1}^n&0 \\
0&\lambda_{2}^n
\end{pmatrix}
ここで、対角化の式
A=PDP^{-1}
を用いて、$A^n$を計算すると以下のようにキャンセルする項がでてくるのでシンプルに表すことができる。
A^n=(PDP^{-1})(PDP^{-1})\cdot \cdot \cdot (PDP^{-1})=P D^{n}P^{-1}
これにより、
\vec{p}_n=A^{n-1}\vec{p_1}=(PD^{n-1}P^{-1})\vec{p}_1
プログラム
さて、以上の考察をプログラムに反映すると、以下のようになる。
理論計算
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
import math
n=20
A=np.array([[1,1],[1,0]])
p1=np.array([[1],[1]])
a_ary=[]
i1_ary=[]
lam1=(5**0.5+1)/2
lam2=(-5**0.5+1)/2
P=np.array([[lam1,lam2],[1,1]])
for i in range(n):
i1=i+1
Dn=np.array([[lam1**i,0],[0,lam2**i]])
pn=(P@Dn@np.linalg.inv(P))@p1
a=pn[0,0]/pn[1,0]
a_ary.append(a)
i1_ary.append(i1)
plt.title("理論計算")
plt.xlabel('試行回数')
plt.ylabel('隣接する項の比率')
plt.plot(i1_ary,a_ary,color='blue',label='隣項の比率')
plt.axhline(y=(5**0.5+1)/2, color='red', linestyle='--', label='収束値')
plt.legend()
plt.savefig("行列計算を用いたフィナボッチ数列の隣接する項の比率2.png")
plt.show()
数値計算
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
import math
n=20
A=np.array([[1,1],[1,0]])
p1=np.array([[1],[1]])
a_ary=[]
i1_ary=[]
lam1=(5**0.5+1)/2
lam2=(-5**0.5+1)/2
P=np.array([[lam1,lam2],[1,1]])
for i in range(n):
i1=i+1
Dn=np.array([[lam1**i,0],[0,lam2**i]])
pn=(P@Dn@np.linalg.inv(P))@p1
a=pn[0,0]/pn[1,0]
a_ary.append(a)
i1_ary.append(i1)
plt.title("理論計算")
plt.xlabel('試行回数')
plt.ylabel('隣接する項の比率')
plt.plot(i1_ary,a_ary,color='blue',label='隣項の比率')
plt.axhline(y=(5**0.5+1)/2, color='red', linestyle='--', label='収束値')
plt.legend()
plt.savefig("行列計算を用いたフィナボッチ数列の隣接する項の比率2.png")
plt.show()
結果
理論計算
以下に、理論計算（行列の累乗を対角化によって計算した上記の考察）での結果を示す。
このように、試行回数を増やすほど、$\frac{a_{n+1}}{a_n}\to \frac{1+\sqrt{5}}{2} $と黄金比に漸近することがわかる。
数値計算
3項間漸化式を行列の形に変換し、数値計算を行った。
結果、数値計算と同様な結果を示した。
まとめ
高校数学の数列分野において、3項間漸化式の解法はとりあえず2次方程式の特性方程式を解くことからスタートする。具体的に何故そのような特性方程式を考える必要性があり、特性方程式は何処から来たのかという疑問について高校数学では明確に答えを示すことはできなかった。ただし、今回のような線形代数の考え方を借りれば、行列の累乗計算を行いたく対角化することに固有方程式を用いるからと明確に答えることができる。このように、数列と線形代数という全く異なる分野でも突き詰めれば、高いレベルで相互に関連し合っていることがわかる。したがって、大学数学を学ぶ場合は、高校数学をしっかりと基本におくことは重要である。例えば、高校数学で自明や議論の対象外とされる解き方やお約束は大学数学のどのような考え方をもとにしているのか考えることも大学数学を学ぶための勉強の一つである。