Fibonacci, lineare Algebra und der goldene Schnitt

Dr. Dieter Graessle

email: dieter@dieter-graessle.de
web: dieter-graessle.de

Stell Dir vor, Du hast ein neugeborenes Hasenpaar, ein Männchen und ein Weibchen. Nach einem Monat werden die Hasen geschlechtsreif und nach jedem weiteren Monat bringen sie ein neues Hasenpaar zur Welt. Jedes neugeborene Hasenpaar wird nach einem Monat geschlechtsreif und bringt dann nach jedem weiteren Monat ein neues Hasenpaar zur Welt. Wie viele Hasenpaare hast Du nach einem Jahr, wenn kein Hase stirbt?_

Mit dieser Aufgabe beschrieb Leonardo Fibonacci im Jahr 1202 die Entstehung der nach ihm benannten Fibonacci-Zahlenfolge: 1 1 2 3 5 8 13 21 34 ... Jede neue Zahl der Folge (ab der dritten Stelle) entsteht, indem man die zwei vorhergehenden Zahlen addiert.

Zusammengefasst wird dies in der bekannten Gleichung für die Fibonacci-Folge:

$F_{n}=F_{n-1}+F_{n-2}$

Abbildung 1 zeigt die Entwicklung von $F_n$ in Abhängigkeit von n.

Abbildung 1: Fibonacci-Folge

Es wäre nun natürlich schön, wenn man eine "Formel" hätte, mit der man die n-te Fibonacci-Zahl direkt berechnen könnte, anstatt alle vorhergehenden Zahlen aufsummieren zu müssen. Die lineare Algebra liefert eine solche Formel, die dann zudem die Möglichkeit einer analytischen Untersuchung der Fibonacci-Folge eröffnet. Damit ergibt sich ein erstaunlicher Zusammenhang mit dem goldenen Schnitt.

Beschreibung der Fibonacci-Folge mit linearer Algebra

Matrixdarstellung der Hasenvermehrung

Übergangsdiagramm

Die Entstehung der Fibonacci-Zahlen wird im Folgenden mit Zustandsvektoren und Matrizen modelliert. Hasenpaare sind entweder im Zustand "neugeboren" (N) oder "geschlechtsreif" (G). Die jeweiligen Anzahlen nach n Monaten werden durch den Zustandsvektor $\vec{x_n}= \left(\begin{array}{c} x_{N,n} \\ x_{G,n} \end{array}\right) = \left(\begin{array}{c} \text{Anzahl neugeborene Paare nach n Monaten} \\ \text{Anzahl geschlechtsreife Paare nach n Monaten} \end{array}\right)$ beschrieben.

Die monatlichen Übergänge zwischen den Zuständen werden im Übergangsdiagramm in Abbildung 2 dargestellt.

Abbildung 2: Übergangsdiagramm der Zustände der Hasenpaare

Zum Zeitpunkt 0 befinden sich 1 Hasenpaar im Zustand N und 0 Hasenpaare im Zustand G, somit lautet der Zustandsvektor $\vec{x_0}= \left(\begin{array}{c} 1 \\ 0 \end{array}\right) $.

Nach einem Monat (Zeitpunkt n=1) ist das eine Hasenpaar vom Zustand N übergegangen in den Zustand G und der Zustandsvektor wird zu $\vec{x_1}= \left(\begin{array}{c} 0 \\ 1 \end{array}\right) $.

Nach einem weiteren Monat (Zeitpunkt n=2) hat das Hasenpaar im Zustand G ein neues Hasenpaar geboren und bleibt aber selber im Zustand G. Der Zustandsvektor wird zu $\vec{x_2}= \left(\begin{array}{c} 1 \\ 1 \end{array}\right) $.

Nach einem weiteren Monat (Zeitpunkt n=3) ist das Hasenpaar im Zustand N geschlechtsreif geworden und geht über in den Zustand G. Das Hasenpaar im Zustand G hat ein weiteres neues Hasenpaar geboren und bleibt selbst weiter im Zustand G. Es gibt ein neugeborenes und zwei geschlechtsreife Hasenpaare. Der Zustandsvektor wird also zu $\vec{x_3}= \left(\begin{array}{c} 1 \\ 2 \end{array}\right) $.

Eine Übersicht gibt die folgende Tabelle (Tabelle 1).

n
$\vec{x_n}$
 $F_n$
0 $\vec{x_0}= \left(\begin{array}{c} 1 \\ 0 \end{array}\right) $ 1
1 $\vec{x_1}= \left(\begin{array}{c} 0 \\ 1 \end{array}\right) $ 1
2 $\vec{x_2}= \left(\begin{array}{c} 1 \\ 1 \end{array}\right) $ 2
3 $\vec{x_3}= \left(\begin{array}{c} 1 \\ 2 \end{array}\right) $ 3
4 $\vec{x_4}= \left(\begin{array}{c} 2 \\ 3 \end{array}\right) $ 5
5 $\vec{x_5}= \left(\begin{array}{c} 3 \\ 5 \end{array}\right) $ 8
n $\vec{x_n}= \left(\begin{array}{c} F_{n-2} \\ F_{n-1} \end{array}\right) $ $F_n$
Tabelle 1: Zustandsvektoren und Fibonacci-Zahlen

Die Summe der beiden Komponenten des Zustandsvektors ergibt die Anzahl der Hasenpaare. Wie man erkennt, sind die beiden Kompomenten selbst jeweils aufeinanderfolgende Glieder der Fibonacci-Folge.

Übergangsmatrix

Der Übergang der Zustandsvektoren kann durch eine Übergangsmatrix $A = \left(\begin{array}{c} a_{11} & a_{12}\\ a_{21} & a_{22} \end{array}\right) $ beschrieben werden. Dabei gibt das Matrixelement $a_{ij}$ an, mit welchem Faktor die Anzahl der Hasenpaare im Zustand i multipliziert wird, wenn sie in den Zustand j wechselt. Aus dem Übergangsdiagramm lassen sich die Matrixelemente leicht ablesen:

$ \begin{array}{c} a_{NN} = 0 & a_{GN} = 1\\ a_{NG} = 1 & a_{GG} = 1 \end{array}$

Formuliert als Matrix:

$A = \left(\begin{array}{c} a_{11} & a_{12}\\ a_{21} & a_{22} \end{array}\right)=\left(\begin{array}{c} a_{NN} & a_{GN}\\ a_{NG} & a_{GG} \end{array}\right) = \left(\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}\right)$

Mit Hilfe der Übergangsmatrix A können nun die aufeinanderfolgenden Zustandsvektoren berechnet werden.

$\vec{x_1} = A \cdot \vec{x_0} = \left(\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}\right) \cdot \left(\begin{array}{c} 1 \\ 0 \end{array}\right) = \left(\begin{array}{c} 0 \\ 1 \end{array}\right)$

$\vec{x_2} = A \cdot \vec{x_1} = \left(\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}\right) \cdot \left(\begin{array}{c} 0 \\ 1 \end{array}\right) = \left(\begin{array}{c} 1 \\ 1 \end{array}\right)$

$\vec{x_3} = A \cdot \vec{x_2} = \left(\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}\right) \cdot \left(\begin{array}{c} 1 \\ 1 \end{array}\right) = \left(\begin{array}{c} 1 \\ 2 \end{array}\right)$

...

Verfolgt man die Entwicklung der Zustandsvektoren durch wiederholte Multiplikation mit der Übergangsmatrix, so ergibt sich:

$\vec{x_1} = A \cdot \vec{x_0} $

$\vec{x_2} = A \cdot \vec{x_1} = A \cdot A \cdot \vec{x_0} = A^2 \cdot \vec{x_0}$

$\vec{x_3} = A \cdot \vec{x_2} = A \cdot A \cdot A \cdot \vec{x_0} = A^3 \cdot \vec{x_0}$

...

und somit:

$\vec{x_n} = A^n \cdot \vec{x_0}$

Man hat nun also eine Art "Formel" gefunden, mit der man die n-te Fibonacci-Zahl direkt berechnen kann.

Leider ist diese Formel nun nicht ganz so schön, wie es auf den ersten Blick erscheint, denn die direkte Berechnung der Matrixpotenzen $A^n$ durch sukzessive Matrixmultiplikation ist sehr rechenaufwendig.

Wesentlich einfacher ist hingegen die Potenzierung einer Diagonalmatrix $D = \left(\begin{array}{c} \delta_1 & 0 \\ 0 & \delta_2 \end{array}\right) $, denn es ist $D^n = \left(\begin{array}{c} \delta_1^n & 0 \\ 0 & \delta_2^n \end{array}\right) $.

Bedeutung der Diagonalmatrix

Ist die Matrix diagonalisierbar (die Diagonalisierbarkeit wird hier nicht näher untersucht), so gibt es eine Matrix S mit der Eigenschaft:

$A = SDS^{-1}$

Damit gilt für die Potenzen von A:

$A^n = \underbrace{SDS^{-1}\cdot SDS^{-1} ... \cdot SDS^{-1}}_{\text{n-mal}}$

Da $S^{-1}$ ja die Inverse von S ist, heben sich die Paare $S^{-1}\cdot S$ auf und es ergibt sich:

$A^n = SD^{n}S^{-1}$

Da D eine Diagonalmatrix ist, lässt sie sich sehr einfach Potenzieren, indem man einfach die Diagonalelemente potenziert (siehe oben).

Durch Diagonalisierung von A kann also eine geschlossene Form für $\vec{x_n} = A^n \cdot \vec{x_0}$ konstruiert werden, die eine direkte Berechnung der Fibonacci-Zahlen ermöglicht.

Doch wie erhält man so eine Diagonalmatrix, und wie hängt diese mit der Matrix A zusammen? Die lineare Algebra kennt dafür eine Technik, die mit Hilfe von Eigenwerten und Eigenräumen bzw. Eigenvektoren arbeitet. Eine beeindruckend schöne Erklärung der Eigenwerte findet sich nebenbei bemerkt bei 3blue1brown.

Berechnung der Diagonalmatrix

Eigenwerte

Eigenwerte und Eigenvektoren von A sind charakterisiert durch die folgende Gleichung:

$A \cdot \vec{v} = \lambda \cdot \vec{v}$

$\lambda$ heißt Eigenwert und $\vec{v}$ heißt Eigenvektor. Eine Matrix A kann mehrere Eigenwerte und Eigenvektoren besitzen.

Durch direkte Umformung erhält man:

$A \cdot \vec{v} = \lambda \cdot \vec{v}$

$A \cdot \vec{v} - \lambda \cdot \vec{v} = 0$

$ (A - \lambda E) \cdot \vec{v} = 0$

Diese Gleichung hat die triviale Lösung $\vec{v} = \vec{0}$. Für den nichttrivialen Fall ( also für $\vec{v} \ne \vec{0}$), muss der Rang von $ (A - \lambda E) $ kleiner als die Dimension von $ (A - \lambda E) $ sein . Damit muss die Determinante von $ (A - \lambda E) $ verschwinden:

$\left| (A - \lambda E) \right| = 0$

Ausgeführt ergibt sich:

$ \left | \left(\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}\right) - \left(\begin{array}{c} \lambda & 0 \\ 0 & \lambda \end{array}\right) \right| = 0$

$ \left | \left(\begin{array}{c} -\lambda & 1 \\ 1 & 1-\lambda \end{array}\right) \right| = 0$

Durch Berechnen der Determinante ergibt sich das charakteristische Polynom:

$-\lambda \cdot (1 - \lambda) - 1\cdot1 = 0$

$-\lambda + \lambda^2 -1 = 0$

$ \lambda^2 -\lambda -1 = 0$

Mit der Lösungsformel für quadratische Gleichungen ergeben sich die Eigenwerte $\lambda_1$ und $\lambda_2$:

$\lambda_{1/2} = \frac{1 \pm \sqrt{1 - 4 \cdot 1 \cdot ( -1)}}{2\cdot 1} = \frac{1 \pm \sqrt{5}}{2}$

$\lambda_1 = \frac{1 - \sqrt{5}}{2} $

$\lambda_2 = \frac{1 + \sqrt{5}}{2} $

Eigenvektoren

Für diese Eigenwerte werden nun die zugehörigen Eigenvektoren berechnet.

Eigenwert $\lambda_1$:

$A \cdot \vec{v} = \lambda_1 \cdot \vec{v}$

$ (A - \lambda_1 E) \cdot \vec{v} = 0$

$ \left(\begin{array}{c} -\lambda_1 & 1 \\ 1 & 1-\lambda_1 \end{array}\right)\cdot \vec{v} = \vec{0} $

$ \left(\begin{array}{c} -\frac{1 - \sqrt{5}}{2} & 1 \\ 1 & 1-\frac{1 - \sqrt{5}}{2} \end{array}\right)\cdot \vec{v} = \vec{0} $

$ \left(\begin{array}{c} -\frac{1 - \sqrt{5}}{2} & 1 \\ 1 & \frac{1 + \sqrt{5}}{2} \end{array}\right)\cdot \left(\begin{array}{c} v_1 \\ v_2 \end{array}\right) = \vec{0}$

Es ergibt sich ein lineares Gleichungssystem für $v_1$ und $v_2$:

$ \begin{array}{c} -\frac{1 - \sqrt{5}}{2} \cdot v_1 & + 1 \cdot v_2 & = 0 \\ 1 \cdot v_1 & \frac{1 + \sqrt{5}}{2} \cdot v_2 & = 0\\ \end{array} $

Zur Lösung kann z.B. eine erweiterte Koeffizientenmatrix verwendet werden:

$ \left(\begin{array}{cc|c} -\frac{1 - \sqrt{5}}{2} & 1 & 0\\ 1 & \frac{1 + \sqrt{5}}{2} &0 \end{array}\right)$

Multiplikation der zweiten Zeile mit $ -\frac{1 - \sqrt{5}}{2}$ ergibt:

$ \left(\begin{array}{cc|c} -\frac{1 - \sqrt{5}}{2} & 1 & 0\\ -\frac{1 - \sqrt{5}}{2} & 1 & 0 \end{array}\right)$

Die Zeilen der Matrix sind linear abhängig und damit gilt:

$ \left(\begin{array}{cc|c} -\frac{1 - \sqrt{5}}{2} & 1 & 0\\ 0&0& 0 \end{array}\right)$

Das Gleichungssystem hat also keine eindeutige Lösung. Dies war zu erwarten, da das Gleichungssystem ja unter der Voraussetzung des nicht vollen Ranges hergeleitet wurde (siehe Berechnung der Eigenwerte). Die Menge der Eigenvektoren (der Eigenraum) zum Eigenwert $\lambda_1$ ergibt sich z.B. durch Parametrisierung von $v_1$:

$v_1 = r, r \in \mathbb{R}$

Damit ergibt sich $v_2$ als

$v_2= r \cdot \frac{1 - \sqrt{5}}{2} $

und für den Eigenraum $E(\lambda_1)$:

$ E(\lambda_1)= \left\{ \vec{x}|\vec{x} = \left(\begin{array}{c} r \\ r \cdot \frac{1 - \sqrt{5}}{2}\end{array}\right) ; r \in \mathbb{R} \right\}$

Allerdings wird für die Diagonalisierung nur ein spezieller Eigenvektor benötigt. Wählt man $r = 1$ so ergibt sich $v_1 = 1$ und als Eigenvektor zu $\lambda_1$

$\vec{v_1} = \left( \begin{array}{c} 1 \\ \frac{1 - \sqrt{5}}{2}\\ \end{array} \right) $

Eigenwert $\lambda_2$:

Analog zur Betrachtung von $\lambda_1$ ergibt sich für den Eigenvektor zu $\lambda_2$:

$\vec{v_2} = \left( \begin{array}{c} 1 \\ \frac{1 + \sqrt{5}}{2}\\ \end{array} \right) $

Somit lassen sich die Matrizen S und D für die Diagonalisierung aufstellen:

$ S = \left( \begin{array}{c} 1 & 1 \\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} \end{array} \right)$

$ D = \left( \begin{array}{c} \lambda_1 & 0 \\ 0 & \lambda_2 \end{array} \right) = \left( \begin{array}{c} \frac{1 - \sqrt{5}}{2} & 0 \\ 0 & \frac{1 + \sqrt{5}}{2} \end{array} \right) $

Benötigt wird noch die Inverse zu S. Für eine 2x2-Matrix

$M=\left(\begin{array}{c}a & b \\ c & d \end{array} \right)$ kann die Inverse berechnet werden als

$M^{-1} = \frac{1}{det(M)} \cdot \left(\begin{array}{c}d & -b \\ -c & a \end{array} \right) $ mit der Determinante von M: $det(M) = ad - bc$.

Für S ergibt sich $det(S)=1 \cdot \frac{1+\sqrt{5}}{2} - 1 \cdot \frac{1-\sqrt{5}}{2} = \sqrt{5}$

und

$S^{-1} = \frac{1}{\sqrt{5}} = \left(\begin{array}{c} \frac{1 + \sqrt{5}}{2} & -1 \\ -\frac{1 - \sqrt{5}}{2} &1 \end{array}\right)$.

Somit sind alle Bausteine für die direkte Berechnung der Fibonacci-Zahlen bereit.

Berechnung der Fibonacci-Zahlen mit Hilfe der Diagonalmatrix

Mit den weiter oben hergeleiteten Beziehungen

$\vec{x_n}=A^n \vec{x_0}$ und $ A^n = S D^n S^{-1}$

erhält man

$\vec{x_n} = S D^n S^{-1}\vec{x_0}$

und ausgegeführt:

$\vec{x_n} = \left(\begin{array}{c} 1 & 1 \\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} \end{array}\right) \cdot \left( \begin{array}{c} \frac{1 - \sqrt{5}}{2} & 0 \\ 0 & \frac{1 + \sqrt{5}}{2} \end{array} \right)^n \cdot \frac{1}{\sqrt{5}} \left(\begin{array}{c} \frac{1 + \sqrt{5}}{2} & -1 \\ -\frac{1 - \sqrt{5}}{2} &1 \end{array}\right) \cdot \vec{x_0} $

$\vec{x_n} = \frac{1}{\sqrt{5}}\cdot \left(\begin{array}{c} 1 & 1 \\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} \end{array}\right) \cdot \left( \begin{array}{c} \left( \frac{1 - \sqrt{5}}{2}\right)^n & 0 \\ 0 & \left( \frac{1 + \sqrt{5}}{2}\right)^n \end{array} \right) \cdot \left(\begin{array}{c} \frac{1 + \sqrt{5}}{2} & -1 \\ -\frac{1 - \sqrt{5}}{2} &1 \end{array}\right) \cdot \left(\begin{array}{c} 1 \\ 0 \end{array}\right) $

Multipliziert man nun die einzelnen Komponenten von rechts beginnend, so ergibt sich:

$\vec{x_n} = \frac{1}{\sqrt{5}}\cdot \left(\begin{array}{c} 1 & 1 \\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} \end{array}\right) \cdot \left( \begin{array}{c} \left( \frac{1 - \sqrt{5}}{2}\right)^n & 0 \\ 0 & \left( \frac{1 + \sqrt{5}}{2}\right)^n \end{array} \right) \cdot \left(\begin{array}{c} \frac{1 + \sqrt{5}}{2} \\ -\frac{1 - \sqrt{5}}{2}\end{array}\right) $

$\vec{x_n} = \frac{1}{\sqrt{5}}\cdot \left( \begin{array}{c} 1 & 1 \\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} \end{array} \right) \cdot \left( \begin{array}{c} \left( \frac{1 - \sqrt{5}}{2}\right)^n \cdot \frac{1 + \sqrt{5}}{2} \\ -\left( \frac{1 + \sqrt{5}}{2}\right)^n \cdot \frac{1 - \sqrt{5}}{2} \end{array} \right)$

$\vec{x_n} = \frac{1}{\sqrt{5}}\cdot \left( \begin{array}{c} 1 \\ \frac{1 - \sqrt{5}}{2} \end{array} \right) \cdot \left( \frac{1 - \sqrt{5}}{2}\right)^n \cdot \frac{1 + \sqrt{5}}{2} -\frac{1}{\sqrt{5}}\cdot \left( \begin{array}{c} 1 \\ \frac{1 + \sqrt{5}}{2} \end{array} \right) \cdot \left( \frac{1 + \sqrt{5}}{2}\right)^n \cdot \frac{1 - \sqrt{5}}{2}$

Nach der langen Rechnung nun wieder zurück zu den Fibonacci-Zahlen. Es war $\vec{x_n} = \left(\begin{array}{c} F_{n-2} \\ F_{n-1} \end{array} \right)$

Liest man nun die Vektorgleichung Komponentenweise, so ergibt sich aus der ersten Komponente des Vektors $\vec{x_n}$ eine Gleichung für $F_{n-2}$ :

$F_{n-2} = \frac{1}{\sqrt{5}}\cdot 1 \cdot \left( \frac{1 - \sqrt{5}}{2}\right)^n \cdot \frac{1 + \sqrt{5}}{2} - \frac{1}{\sqrt{5}}\cdot 1 \cdot \left( \frac{1 + \sqrt{5}}{2}\right)^n \cdot \frac{1 - \sqrt{5}}{2} $

$F_{n-2} = \frac{1}{\sqrt{5}}\cdot \left( \frac{1 - \sqrt{5}}{2}\right)^n \cdot \frac{1 + \sqrt{5}}{2} - \frac{1}{\sqrt{5}}\cdot \left( \frac{1 + \sqrt{5}}{2}\right)^n \cdot \frac{1 - \sqrt{5}}{2} $

Um die n-te Fibonacci-Zahl $F_n$ zu erhalten, müssen die Exponenten einfach um 2 erhöht werden. Damit ist nun eine geschlossene Form zur Berechung der Fibonacci-Zahlen ohne Rekursion oder Matrixmultiplikation erreicht.

$F_{n} = \frac{1}{\sqrt{5}}\cdot \left( \frac{1 - \sqrt{5}}{2}\right)^{n+2} \cdot \frac{1 + \sqrt{5}}{2} - \frac{1}{\sqrt{5}}\cdot \left( \frac{1 + \sqrt{5}}{2}\right)^{n+2} \cdot \frac{1 - \sqrt{5}}{2} $

Diese "Formel" sieht zwar kompliziert aus, ist aber bezüglich des Rechenaufwands wesentlich anspruchsloser als eine Berechnung über die rekursive Addition oder Matrixpotenzierung.

Analyse für große n: Der goldene Schnitt

Das Verhalten der Reihe $F_n$ wird durch die beiden Potenzterme $\left( \frac{1 - \sqrt{5}}{2}\right)^{n+2}$ und $\left( \frac{1 + \sqrt{5}}{2}\right)^{n+2}$ bestimmt.

Betrachten wir zuerst den Term $\left( \frac{1 - \sqrt{5}}{2}\right)^{n+2}$ .

Ausgehend von der Ungleichung

$ \sqrt4 < \sqrt5 < \sqrt9$

ergibt sich:

$ 2 < \sqrt5 < 3$ $ | -1$

$2-1 < \sqrt5 -1 < 3-1 $

$1 < \sqrt5 -1 < 2 $ $|:2$

$\frac12 < \frac {\sqrt5 -1}{2} < 1 $ $| \cdot (-1)$

$ - \frac12 > \frac {1-\sqrt5 }{2} > - 1 $ $| \cdot (-1)$

$ -1 < \frac {1-\sqrt5 }{2} < - \frac12 $

Somit gilt:

$\left| \frac {1-\sqrt5 }{2} \right| < 1$

Das bedeutet, dass für wachsendes n die Potenz $\left( \frac{1 - \sqrt{5}}{2}\right)^{n+2}$ gegen 0 geht und der erste Term unserer gefundenen Fibonacci-Formel verschwindet.

Für große n wird die Entwicklung von $F_n$ also vom zweiten Term um die Potenz $\left( \frac{1 + \sqrt{5}}{2}\right)^{n+2}$ dominiert:

Für $n \rightarrow \infty : F_n \rightarrow - \frac{1}{\sqrt{5}}\cdot \left( \frac{1 + \sqrt{5}}{2}\right)^{n+2} \cdot \frac{1 - \sqrt{5}}{2} $

Berechnet man nun das Verhältnis zweiter aufeinanderfolgender Fibonacci-Zahlen, so ergibt sich für große n:

$n \rightarrow \infty : \frac{F_{n+1}}{F_n} \rightarrow \frac{ -\frac{1}{\sqrt{5}}\cdot \left( \frac{1 + \sqrt{5}}{2}\right)^{n+3} \cdot \frac{1 - \sqrt{5}}{2} } {-\frac{1}{\sqrt{5}}\cdot \left( \frac{1 + \sqrt{5}}{2}\right)^{n+2} \cdot \frac{1 - \sqrt{5}}{2} }= \frac{1 + \sqrt{5}}{2}$

Dies ist ein überraschender Grenzwert, denn er ist nicht nur der erste Eigenwert unserer am Anfang definierten Übergangsmatrix A, sondern auch genau der sogenannte goldenene Schnitt.

Das Verhältnis zweier aufeinanderfolgender Fibonacci-Zahlen nähert sich also dem goldenen Schnitt an. Betrachtet man den Verlauf der Näherung $\frac{F_{n+1}}{F_n}$ in Abbildung 3, so überrascht, wie schnell die Folge gegen $\Phi$ konverviert.

Abbildung 3: Näherung des Goldenen Schnitts durch $F_{n+1} / Fn$

Weiteres zum goldenen Schnitt findet sich im nachfolgenden Kapitel.

Berechnung des goldenen Schnitts aus seiner Definition:

Zur Erinnerung: Der "goldene Schnitt" ergibt sich durch die Aufteilung einer Strecke in solcher Weise, dass das Verhältnis vom größeren Teil zur Gesamtstrecke gleich ist dem Verhältnis von kleinerem Teil zu größerem Teil.

Zur Berechnung wird eine Strecke geteilt in die Abschnitte a und b, so dass die Aufteilung im goldenen Schnitt $\frac{a}{b} = \Phi$ erfolgt:

$|---a----|--b--|$

$\frac{a}{b} = \frac{a+b}{a}$

$\frac{a}{b} = \frac{a}{a} + \frac{b}{a}$

$\frac{a}{b} - \frac{a}{a} - \frac{b}{a} = 0$

$\Phi - 1 - \frac{1}{\Phi} = 0$

Mit der quadratischen Lösungsformel erhält man:

$\Phi_{1,2} = \frac{1 \pm \sqrt{(-1)^2 - 4\cdot 1 \cdot (-1)}}{2 \cdot 1} = \frac{1 \pm \sqrt5}{2}$

Das Verhältnis der zwei Strecken muss positiv sein, also bleibt als Lösung nur der positive Term für $\Phi$:

$\Phi = \frac{1 + \sqrt5}{2} \approx 1,62$

Dies ist der Zahlenwert für den goldenen Schnitt.

Grundlegende Berechnungen und Erzeugung der Plots mit Python

In [256]:
%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt
import numpy.linalg as la
#import scipy.linalg as sla

Es werden nun die Matrix A und der Startvektor $\vec{x_0}$ angelegt.

In [257]:
A = np.array([[0,1],
              [1,1]])
#x0 = np.array([1,0]).reshape((2,1)) # Der Form halber wird hier ein Spaltenvektor angelegt.
x0 = np.array([1,0]) # Der Startvektor x0
x1 = np.dot(A,x0) # Der Vektor x1 ergibt sich als A*x0
print(x1)

[0 1]

Berechnung von Fibonacci-Zahlen mittels Potenzierung von A

In [258]:
n = 20
An = la.matrix_power(A,n)
#print(An, "\n")
xn = np.dot(An,x0)
#print(xn, "\n")
Fn = xn[0]+xn[1]
print("Die 20. Fibonacci-Zahl lautet: ", Fn, "\n")

Die 20. Fibonacci-Zahl lautet:  10946
In [259]:
Phi_n = xn[1] / xn[0]
print ("Die Näherung des goldenen Schnitts nach", n , "Schritten: ", Phi_n, "\n")

Die Näherung des goldenen Schnitts nach 20 Schritten:  1.61803396317
In [260]:
def Fibo_Matrix(n=100):
    An = la.matrix_power(A,n)
    xn = np.dot(An,x0)
    Fn = xn[0]+xn[1]
    return Fn

Im Vergleich dazu die Berechnung der n-ten Fibonacci-Zahl mit Hilfe der "matrixfreien" Gleichung:

In [261]:
def Fibo(n=100):
    n = n+2
    r5 = 5**0.5
    Fibo_n = int ( 1/r5 * 1 * ((1-r5)/2)**n * (1+r5)/2 - 1/r5 * 1 * ((1+r5)/2)**n * (1-r5)/2 )
    return Fibo_n

Vergleich der Rechenzeiten der matrixpotenzbasierten mit der diagonalmatrixbasierten Methode

In [262]:
import timeit
print ("Matrixpotenzen: ", timeit.timeit( Fibo_Matrix, number=10 ) )
print ("Diagonalmatrix: ", timeit.timeit(Fibo, number=10) )

Matrixpotenzen:  0.00045610900269821286
Diagonalmatrix:  3.356100933160633e-05

Die auf Matrixpotenzen basierte Methode braucht zur Ermittlung der einhundersten Fibonacci-Zahl ca. zwei Größenordnungen mehr Rechenzeit.

Plots

In [263]:
n = 15
x = np.array(range(n))
y = np.array([ Fibo(i) for i in range(n)])
plt.plot(x,y,'r.')
plt.grid()
plt.xlabel("n")
plt.ylabel("Fn")
plt.savefig('fibonacci.png', dpi=300, bbox_inches='tight')
plt.show()
In [264]:
n = 30
x = np.array(range(n))
y = np.array([ Fibo(i) for i in range(n)])
plt.plot(x,y,'r.')
plt.grid()
plt.xlabel("n")
plt.ylabel("Fn")
plt.savefig('fibonacci2.png', dpi=300, bbox_inches='tight')
plt.show()
In [265]:
n = 10
x = np.array(range(n))

y = np.array([ Fibo(i+1)/Fibo(i) for i in range(n)])

plt.plot(x,y,'r.')
plt.xlabel("n")
plt.ylabel("Fn+1 / Fn")
plt.grid()
plt.savefig('Phi_n.png', dpi=300, bbox_inches='tight')
plt.show()