09.10.2026 - Woche 4

Schnelle Berechnung von Fibonacci Zahlen:

Fast Fibonacci Numbers

Die Fibonacci Folge ist folgendermassen definiert:

$$F_0=0$$ $$F_1=1$$ $$F_n=F_{n-1}+F_{n-2}n\ge 2$$

Es handelt sich also um eine rekursiv definierte Folge. Das bringt denn Nachteil mit, dass wen man $F_{100}$ berechnen möchte man zwingend auf die vorherigen beiden Glieder der Folge $F_{99}$ und $F_{98}$ angewiesen ist. damit man aber wiederum diese beiden Glieder der Folge berechnen kann muss man wieder die beiden vorherigen kennen.
Dies führt dazu, dass wenn man $F_{100}$ berechnen möchte alle Zahlen der Fibonacci Folge zwischen $0$ und $100$ berechnen muss. Somit erhält man also Unmengen von Daten, welche am Schluss gar nicht interessant sind, da man nur an $F_{100}$ interessiert ist.

Hier kommt jetzt die Lineare Algebra ins Spiel. Es stellt sich heraus, dass die folgende Matrix:

$$\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$$

Dazu genutzt werden kann Fibonacci Zahlen zu erzeugen:

$$\left(\begin{array}{c}{F}_{n-1}\\ F_n\end{array}\right)=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]\left(\begin{array}{c}{F}_{n-2}\\ F_{n-1}\end{array}\right)n\ge 2$$

Es liegt also auch hier wieder eine rekursive Definition vor:

$$\left(\begin{array}{c}{F}_{n-1}\\ F_n\end{array}\right)=A\left(\begin{array}{c}{F}_{n-2}\\ F_{n-1}\end{array}\right)=A\left(A\left(\begin{array}{c}{F}_{n-3}\\ F_{n-2}\end{array}\right)\right)=\dots =A\left(\dots \left(A\left(\begin{array}{c}{F}_0\\ F_1\end{array}\right)\right)\dots \right)$$

Was wenn man die Werte $F_0=0$ und $F_1=1$ einsetzt folgendes ergibt:

$$A\left(\dots \left(A\left(\begin{array}{c}0\\ 1\end{array}\right)\right)\dots \right)$$

Was aufgrund von Lemma 2.40 zusammengefasst und wie folgt geschrieben werden kann:

$$A^{n-1}\left(\begin{array}{c}0\\ 1\end{array}\right)$$

Um jetzt also die gesuchte Fibonacci Zahl $F_n$ berechnet zu können muss die Matrix $A^{n-1}$ bekannt sein. Die Matrixmultiplikation $A\cdot A\cdot A\cdot \dots \cdot A$ muss also $n-1$ Mal ausgeführt werden, bevor bei der Rechnung

$$A^{n-1}\left(\begin{array}{c}0\\ 1\end{array}\right)$$

die gesuchte Fibonacci Zahl $F_n$ in der unteren rechten Ecke zu finden ist.
Aber auch hier stellt sich noch die Frage, ob das besser ist. Wenn mit dieser Methode $F_{100}$ berechnet werden soll muss $A^{99}$ bekannt sein und es müssen wieder viele Matrixmultiplikationen durchgeführt werden. Hier kann man sich aber die Methode des iterativen quadrierens zur Hilfe nehmen:

$$A^{99}=(A^{49}{)}^2\cdot A$$ $$A^{49}=(A^{24}{)}^2\cdot A$$ $$A^{24}=(A^{12}{)}^2$$ $$A^{12}=(A^6{)}^2$$ $$A^6=(A^3{)}^2$$ $$A^3=(A{)}^2\cdot A$$

Indem man die Matrix $A$ immer wieder quadriert und notfalls noch mit $A$ multipliziert, damit man auf einen ungeraden Exponenten kommt ist man in 6 Schritten am Ziel.

Mit der obigen Methode kann man den Rechenaufwand zwar schon stark reduzieren, es stellt sich nun aber die Frage: wieso das ganze überhaupt? Es gibt doch eine Formel für die explizite Berechnung von $F_n$:

$$F_n=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]$$

Zwar kann man mit dieser Formel sofort das $n$-te Glied der Folge berechnen, jedoch kann es auf dem Computer, welcher mit Fliesskommazahlen arbeitet bei grossen Zahlen zu starken Rundungsfehlern kommen. Dann hat man zwar schnell die Fibonacci Zahl $F_n$ berechnet, sie ist aufgrund eines solchen Rundungsfehlers aber falsch. Das iterative quadrieren ist also er praktischere Weg, um die $n$-te Fibonacci Zahl zu berechnen, auch wenn der Rechenaufwand höher ist.

Link to original