Fibonacci und Eigenwerte
Eigenwerte und Eigenvektoren kann man auch benutzen, um bei bestimmten rekursiven Folgen explizite Darstellungen zu finden.
Bsp: Die Fibonaccifolge (a_n)_{n\in IN}
mit a_n=a_{n-1}+a_{n-2} und a_1=1 a_2=1
Idee:
$$\left(\begin{array}{c}a_{n-1}\\a_{n-2}\end{array}\right) \begin{array}{c}M\\ \rightarrow\end{array} \left(\begin{array}{c}a_n\\a_{n-1}\end{array}\right) \Rightarrow \left(\begin{array}{cc}1&1\\1&0\end{array}\right)$$
Mit dem Startvektor \vec{k}_0=\left(\begin{array}{c}1\\1\end{array}\right)=\left(\begin{array}{c}a_2\\a_1\end{array}\right) erhält man dann:
$$\left(\begin{array}{c}a_n\\a_{n-1}\end{array}\right)=M^{n-2}\cdot\left(\begin{array}{c}a_2\\a_1\end{array}\right)=M^{n-2}\cdot\vec{k}_0$$
Wenn M Eigenwerte besitzt und \vec{k}_0 in Eigenvektoren zerlegt werden kann, erhält man eine explizite Darstellung der Folge.
1. Berechnen der Eigenwerte:
$$det(M-\lambda E)=0$$
$$det\left(\begin{array}{cc}1-\lambda&1\\1&-\lambda\end{array}\right)=0$$
$$(1-\lambda)\cdot(-\lambda)-1\cdot1=0$$
$$\lambda^2-\lambda-1=0$$
$$\lambda_{1,2}=\frac{1}{2}\pm\sqrt{\frac{1}{4}+1}$$
$$\lambda_1=\frac{1-\sqrt{5}}{2}$$
$$\lambda_2=\frac{1+\sqrt{5}}{2}$$
2. Berechnung der Eigenvektoren
Für den Vektor \vec{v}_1 gilt:
$$(M-\lambda_1 E_2)\cdot \vec{v}_1=0$$
$$\left(\begin{array}{cc}1-\frac{1-\sqrt{5}}{2}&1\\1&-\frac{1-\sqrt{5}}{2}\end{array}\right)\cdot\left(\begin{array}{c}x\\y\end{array}\right)=\left(\begin{array}{c}0\\0\end{array}\right)$$
Daraus ergibt sich ein lineares Gleichungssystem mit zwei Variablen:
$$\left(1-\frac{1-\sqrt{5}}{2}\right)x+y=0$$
$$x-\frac{1-\sqrt{5}}{2}y=0$$
$$\Leftrightarrow x=\frac{1-\sqrt{5}}{2}y$$
$$\Rightarrow \vec{v}_1=\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\1\end{array}\right)$$
Ebenso gilt für den Vektor \vec{v}_2:
$$(M-\lambda_2 E_2)\cdot \vec{v}_1=0$$
$$\left(\begin{array}{cc}1-\frac{1+\sqrt{5}}{2}&1\\1&-\frac{1+\sqrt{5}}{2}\end{array}\right)\cdot\left(\begin{array}{c}x\\y\end{array}\right)=\left(\begin{array}{c}0\\0\end{array}\right)$$
Daraus ergibt sich ebenfalls ein lineares Gleichungssystem mit zwei Variablen:
$$\left(1-\frac{1+\sqrt{5}}{2}\right)x+y=0$$
$$x-\frac{1+\sqrt{5}}{2}y=0$$
$$\Leftrightarrow x=\frac{1+\sqrt{5}}{2}y$$
$$\Rightarrow \vec{v}_2=\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\1\end{array}\right)$$
3. Aufspaltung des Startvektors in Linearkomponenten
Es gilt:
$$\vec{k}_0=a\cdot\vec{v}_1+b\cdot\vec{v}_2$$
$$\left(\begin{array}{c}1\\1\end{array}\right)=a\cdot\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\1\end{array}\right)+b\cdot\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\1\end{array}\right)$$
Daraus ergibt sich erneut ein lineares Gleichungssytem mit zwei Variablen:
$$\frac{1-\sqrt{5}}{2}a+\frac{1+\sqrt{5}}{2}b=1$$
$$a+b=1$$
Als Lösungen ergeben sich dann:
$$a=-\frac{1}{\sqrt{5}}\frac{1-\sqrt{5}}{2}$$
$$b=\frac{1}{\sqrt{5}}\frac{1+\sqrt{5}}{2}$$
Somit:
$$\left(\begin{array}{c}1\\1\end{array}\right)=-\frac{1}{\sqrt{5}}\cdot\frac{1-\sqrt{5}}{2}\cdot\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\1\end{array}\right)+\frac{1}{\sqrt{5}}\cdot\frac{1+\sqrt{5}}{2}\cdot\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\1\end{array}\right)$$
4. Verwertung der Idee:
Aus unserer Idee haben wir ja M^{n-2}\cdot\vec{k}_0. Also:
$$M^{n-2}\cdot\vec{k}_0=a\cdot M^{n-2}\cdot\vec{v}_1+b\cdot M^{n-2}\cdot\vec{v}_2$$
$$M^{n-2}\cdot\vec{k}_0=a\cdot\lambda_1^{n-2}\cdot\vec{v}_1+b\cdot\lambda_2^{n-2}\cdot\vec{v}_2$$
$$M^{n-2}\cdot\vec{k}_0=-\frac{1}{\sqrt{5}}\cdot\frac{1-\sqrt{5}}{2}\cdot\left(\frac{1-\sqrt{5}}{2}\right)^{n-2}\cdot\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\1\end{array}\right)+\frac{1}{\sqrt{5}}\cdot\frac{1+\sqrt{5}}{2}\cdot\left(\frac{1+\sqrt{5}}{2}\right)^{n-2}\cdot\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\1\end{array}\right)=\left(\begin{array}{c}a_n\\a_{n-1}\end{array}\right)$$
Da wir a_n bestimmen wollen, ist nur der obere Eintrag der Vektoren wichtig. Somit gilt:
$$a_n=-\frac{1}{\sqrt{5}}\cdot\frac{1-\sqrt{5}}{2}\cdot\left(\frac{1-\sqrt{5}}{2}\right)^{n-2}\cdot\frac{1-\sqrt{5}}{2}+\frac{1}{\sqrt{5}}\cdot\frac{1+\sqrt{5}}{2}\cdot\left(\frac{1+\sqrt{5}}{2}\right)^{n-2}\cdot\frac{1+\sqrt{5}}{2}$$
$$a_n=-\frac{1}{\sqrt{5}}\cdot\left(\frac{1-\sqrt{5}}{2}\right)^n+\frac{1}{\sqrt{5}}\cdot\left(\frac{1+\sqrt{5}}{2}\right)^n$$
$$a_n=\frac{1}{\sqrt{5}}\cdot\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$
Somit ist die explizite Dartellung der Fibonaccifolge hergeleitet.