Fibonacciho posloupnost

Úkol: Nalezněte explicitní vzorec pro $ n$-tý člen Fibonacciho posloupnosti, která je definovaná počátečními podmínkami $ a_1=a_2=1$ a rekurzivním předpisem $ a_{n+1}=a_n+a_{n-1}$ (tedy $ 1,1,2,3,5,8,13,\dots$). Spočtěte limitu podílu $ a_n/a_{n-1}$ pro $ n\to\infty$. Návod: najděte zobrazení $ f:${\bb R}$ ^2\to${\bb R}$ ^2$, $ f(a_{n-1},a_n)=(a_n,a_{n+1})$ a diagonalizujte jej.

Poznámka: Úlohu také lze vyřešit, aniž bychom zmínili pojem ,,diagonalizace zobrazení''. V úvodu ke kapitole 8 jsme odvodili vztah 49, který lze použít pro libovolnou posloupnost definovanou lineárním rekurentním vztahem $ D_n=pD_{n-1}+qD_{n-2}$. Metoda, kterou použijeme nyní, je početně stejně pracná jako odvození v kapitole 8. Její výhodou je ale systematičnost a to, že používá standardní nástroj lineární algebry, vlastní čísla.


Řešení: Díky linearitě předpisu $ a_{n+1}=a_n+a_{n-1}$ lze posloupnost popsat pomocí lineárního zobrazení

$\displaystyle \nonumber f:\tb{c}a_{n-1}\\ a_n.\mapsto
\tb{c}a_n\\ a_{n+1}.={A}\tb{c}a_{n-1}\\ a_n.,\qquad
{A}=\tb{cc}\circ&1\\ 1&1.$

Matici $ A$ nyní zdiagonalizujeme; že to půjde, zaručuje její symetrie.

Charakteristickou rovnici $ 0=\mathop{\rm det}\nolimits ({A}-\lambda\mathbbm{1})=\lambda^2-\lambda-1$ řeší vlastní čísla

$\displaystyle \nonumber \lambda_{\pm}=\frac{1\pm \sqrt 5}2,\qquad
\lambda_+\doteq 1,618, \quad \lambda_-\doteq-0,618\,.$

Vlastní vektory $ \vec{v}_\pm$, které splňují rovnici $ ({A}-\lambda_\pm\mathbbm{1})\vec{v}_\pm=0$, mají (až na libovolný násobek) tvar

$\displaystyle \vec{v}_+={1\choose \lambda_+}\,, \qquad \vec{v}_-={1\choose
\lambda_-}\,.$

a tyto vektory je třeba zapsat jako sloupce matice $ {C}$ do formule diagonalizace $ {A}={C} {D} {C}^{-1}$.

$\displaystyle \tb{cc}\circ&1\\ 1&1.=\tb{ll}1&1\\ 
 \lambda_+&\lambda_-.\tb{ll}\...
...\circ\\ \circ &\lambda_-.
 \tb{rr}-\lambda_-&1\\ \lambda_+&-1.\frac{1}{\sqrt 5}$ (55)

Inverzní matici $ {C}^{-1}$ rozměru $ 2\times 2$ jsme spočetli jako ostřílení pionýři z hlavy podle Čihákova vzorce:

$\displaystyle \tb{cc}a&b\\ c&d.^{-1}=
\frac{1}{ad-bc}\tb{rr}d&-b\\ -c&a.$

Matici $ {A}^n$, priřazující $ (a_0,a_1)^T$ vektor $ (a_n,a_{n+1})^T$, získáme z (55) lehce:

$\displaystyle \nonumber \tb{cc}\circ&1\\ 1&1.^n\hskip-1pt=\tb{ll}1&1\\
\lambd...
...\circ &\lambda_-^n.
\tb{rr}-\lambda_-&1\\ \lambda_+&-1.\frac{1}{\sqrt 5}=\dots$

Jedno maticové násobení nám dává

$\displaystyle \dots= \tb{rr}1\cdot\lambda_+^n&1\cdot\lambda_-^n\\ 
 \lambda_+\c...
...lambda_-\cdot\lambda_-^n.
 \tb{rr}-\lambda_-&1\\ \lambda_+&-1.\frac{1}{\sqrt 5}$ (56)

a jelikož $ a_0=a_2-a_1=0$ a $ a_1=1$, výsledek $ a_n$ lze odečíst na pozici 12 -- zajímá nás horní složka vektoru $ (a_n,a_{n+1})^T=A^n(a_0,a_1)^T={A}^n (0,1)^T$ a vidíme $ a_n=(A^n)_{12}a_1$.

Prvek matice (56) v pravém horním rohu je

$\displaystyle a_n=\frac{1}{\sqrt 5}(\lambda_+^n-\lambda_-^n).$ (57)

Všimněte si, že pro velká $ n$ lze zanedbat druhý člen, a tudíž poměr $ a_n/a_{n-1}$ se asymptoticky blíží právě k vlastnímu číslu $ \lambda_+\doteq 1,618$, jak jsme mohli očekávat od chvíle, kdy jsme spočítali vlastní čísla. Ptáte se proč? Násobit nějaký vektor $ \vec{v}$ maticí $ A$ znamená zapsat jej jako $ \alpha\vec{v}_++\beta\vec{v}_-$ a první složku násobit $ \lambda_+$ a druhou $ \lambda_-$

$\displaystyle A(\alpha\vec{v}_++\beta\vec{v}_-)=\lambda_+\alpha\vec{v}_++
\lambda_-\beta\vec{v}_-\,.
$

Takto tedy vypadá diagonalizované zobrazení26 $ A$. Při násobení vektoru maticí $ A^n$ zaměníme $ \lambda_\pm$ za $ \lambda_\pm^n$ a vidíme, že ve výsledku bude dominovat složka příslušná největšímu vlastnímu číslu (srovnejte s příkladem 14.1). Exaktně zapsáno $ A^n(a_1,a_0)^T=\lambda_+^n(a_1,a_0)^T+o(\lambda_+^n)\cdot (1,1)^T$, a tudíž $ a_{n+1}/a_n=\lambda_+^{n+1}/\lambda_+^n+o(1)=\lambda_++o(1)$.

Uvedenému poměru se říká zlatý řez, je to zároveň poměr stran obdélníka, z něhož po odříznutí čtverce zbude obdélník původnímu podobný, což Fibonacciho posloupnost napodobuje.

$ \ast$LM$ \ast$