[場所1E501（月曜日5限）]
このページは7/22に行われた授業に基づいています。
これはマトウセクのMiniature 1に関する内容です。
フィボナッチ数列とは、
$F_{n+2}=F_{n+1}+F_n$
かつ $F_0=0$ かつ $F_1=1$ を満たすものをいいます。
このフィボナッチ数列の第 $n$ 項 $F_n$ を計算するのに、
この漸化式を用いれば、大体 $n$ 回の加法によって計算されます。
この回数のオーダーを計算量ということにすると、
この計算量は $n$ ということになります。
今、${\bf v}_n=\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}$
とし、
$$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$$
とおくと、
$${\bf v}_{n+1}=M\cdot {\bf v}_n$$
が成り立ちます。そうすると、
${\bf v}_n=M^n\cdot {\bf v}_0$ となります。
ゆえに、${\bf v}_n$ を計算するのに $n$ 回の行列の掛け算を
計算することになりますので、やはり計算量は $n$ ということになります。
しかし、$n=2^m$ の場合、以下のように計算を工夫します。
$M^2=M\cdot M$, $M^4=M^2\cdot M^2$, $M^8=M^4\cdot M^4,\cdots $
$M^{2^m}=(M^{2^{m-1}})^2$ として計算をするのです。
そうすると $M^{2^m}$ を計算するのに、$m$ 回の行列の掛け算を計算すればよい
つまり、$m$ 回の計算量ということになります。
$m=\log_2n$ だけ計算すればよいことになり、
この工夫により、計算量 $n$ からは大分改善されたことになります。
一般にはどうかというと、一般の自然数 $n$ は
$k_1<k_2<\cdots <k_t$ なる単調増加な自然数列を用いて、
$n=2^{k_1}+\cdots +2^{k_t}$
のように一意的に表すことができます。
これは２進法です。よって、特に、$2^{k_t}\le n<2^{k_t+1}$ となります。
よって、$M^n=M^{2^{k_1}}M^{2^{k_2}}\cdots M^{2^{k_t}}$
のように書くことができます。
$M^n$ を計算するに、上とおなじようにしてまずは、$M^{2^{k_t}}$
を計算します。
そのとき、$M^2, M^4,M^8,\cdots$ は計算されているので、
それを用いて、$M^{2^{k_1}}M^{2^{k_2}}\cdots M^{2^{k_t}}$ が計算できます。
フィボナッチ数列とは、
$F_{n+2}=F_{n+1}+F_n$
かつ $F_0=0$ かつ $F_1=1$ を満たすものをいいます。
このフィボナッチ数列の第 $n$ 項 $F_n$ を計算するのに、
この漸化式を用いれば、大体 $n$ 回の加法によって計算されます。
この回数のオーダーを計算量ということにすると、
この計算量は $n$ ということになります。
今、${\bf v}_n=\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}$
とし、
$$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$$
とおくと、
$${\bf v}_{n+1}=M\cdot {\bf v}_n$$
が成り立ちます。そうすると、
${\bf v}_n=M^n\cdot {\bf v}_0$ となります。
ゆえに、${\bf v}_n$ を計算するのに $n$ 回の行列の掛け算を
計算することになりますので、やはり計算量は $n$ ということになります。
しかし、$n=2^m$ の場合、以下のように計算を工夫します。
$M^2=M\cdot M$, $M^4=M^2\cdot M^2$, $M^8=M^4\cdot M^4,\cdots $
$M^{2^m}=(M^{2^{m-1}})^2$ として計算をするのです。
そうすると $M^{2^m}$ を計算するのに、$m$ 回の行列の掛け算を計算すればよい
つまり、$m$ 回の計算量ということになります。
$m=\log_2n$ だけ計算すればよいことになり、
この工夫により、計算量 $n$ からは大分改善されたことになります。
一般にはどうかというと、一般の自然数 $n$ は
$k_1<k_2<\cdots <k_t$ なる単調増加な自然数列を用いて、
$n=2^{k_1}+\cdots +2^{k_t}$
のように一意的に表すことができます。
これは２進法です。よって、特に、$2^{k_t}\le n<2^{k_t+1}$ となります。
よって、$M^n=M^{2^{k_1}}M^{2^{k_2}}\cdots M^{2^{k_t}}$
のように書くことができます。
$M^n$ を計算するに、上とおなじようにしてまずは、$M^{2^{k_t}}$
を計算します。
そのとき、$M^2, M^4,M^8,\cdots$ は計算されているので、
それを用いて、$M^{2^{k_1}}M^{2^{k_2}}\cdots M^{2^{k_t}}$ が計算できます。
よって、合計で計算量 $2k_t$ で $M^n$ が計算できることになります。
$2^{k_t}\le n$ であるから、$k_t \le \log_2n$ よって、$2\log_2n$ の
計算量となります。
フィボナッチ数列の一般項
これはマトウセクのMiniature 2の内容です。
上の数列の一般項 $F_n$ を線形代数を用いて計算します。
$(a_0,a_1,a_2,\cdots, a_n,\cdots )\in {\mathbb R}^\infty$
のように、数列の集合を考えます。この集合は各成分をそれぞれ足すことによって
また、それぞれの成分にスカラー倍することによって
ベクトル空間になります。
ふつうの有限次元ベクトル空間の構造の素直な拡張になっています。
$(a_0,a_1,a_2,\cdots, a_n,\cdots )=(a_n)$ と書くことにします。
$W=\{(a_n)\in {\mathbb R}^\infty|a_{n+2}=a_{n+1}+a_n\}$ とします。
このとき、$W$ は ${\mathbb R}^\infty$ の部分ベクトル空間となります。
その証明は省略します。
ただし、ゼロベクトルは ${\bf 0}=(0,0,\cdots)$ となります。
注意
また、フィボナッチ数列は、最初の2項が決まれば、3項目以降は一意的に決ま
ることに注意しておきます。
ここで、$W$ の次元を計算します。
${\bf v}_0=(1,0,1,1,2,3,\cdots )$, ${\bf v}_1=(0,1,1,2,3,5,\cdots)$ とします。
$c_0{\bf v}_0+c_1{\bf v}_1={\bf 0}$ とします。
このとき、$(c_0,c_1,\cdots)=(0,0,\cdots)$ となり、
各成分を比較することによって $c_0=c_1=0$ であるから、${\bf v}_0,{\bf v}_1$ は
1次独立になります。
また、${\bf v}=(a_0,a_1,a_2,\cdots)\in W$ とします。
このとき、${\bf v}-a_0{\bf v}_0-a_1{\bf v}_1=(0,0,\cdots)$
となり、上の注意から、この右辺も $W$ の元であるから、${\bf 0}$
そのものになります。
よって、${\bf v}=a_0{\bf v}_0+a_1{\bf v}_1$ であるから、
${\bf v}_0, {\bf v}_1$ は $W$ の基底となります。
ゆえに、$\dim(W)=2$ となります。
$\tau_1=\frac{1+\sqrt{5}}{2}$ $\tau_2=\frac{1-\sqrt{5}}{2}$
としますと、この数は、
$\tau^2=\tau+1$ の解です。
なので、
${\bf u}=(1,\tau_1,\tau_1^2,\cdots)$ と
${\bf v}=(1,\tau_2,\tau_2^2,\cdots)$ は
$W$ の元であることはすぐわかります。
また、$\tau_1\neq \tau_2$ であるから、
${\bf u}$ と ${\bf v}$ は平行ではないだから、
${\bf u},{\bf v}$ は1次独立となります。
${\bf u}, {\bf v}$ は $W$ の基底となります。
よって、${\bf v}_1=(F_0,F_1,F_2,\cdots)$ は
$\alpha {\bf u}+\beta {\bf v}$ となる実数 $\alpha,\beta\in {\mathbb R}$
が存在します。
この 0 番目の成分を比べると、
$\alpha+\beta =0$ であり、かつ
1番目の成分を比べると、
1番目の成分を比べると、
$\alpha\tau_1+\beta\tau_2=1$ の連立一次方程式を
解くと、
$\alpha=\frac{1}{\sqrt{5}}$, $\beta=-\frac{1}{\sqrt{5}}$
となります。
よって、${\bf v}_1=\frac{1}{\sqrt{5}}{\bf u}-\frac{1}{\sqrt{5}}{\bf v}$
となります。
よって、$n$ 番目の項は、
$$F_n=\frac{1}{\sqrt{5}}(\tau_1^n-\tau_2^n)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$
となります。
0 件のコメント:
コメントを投稿