Startseite Mathematik-Online        Themenliste

Mathematik-Online

„ Fibonacci ”  
         ist die Kurzform von Filius (italienisch: Figlio) Bonacci = Sohn des Bonacci.

Fibonacci
ca. 1180 - 1250


Der italienische Mathematiker Leonardo von Pisa (Fibonacci genannt) beobachtete im Garten die Kaninchen und fragte sich:

Ein Paar neugeborener Kaninchen wirft nach zwei Monaten ein neues Paar und in den folgenden Monaten jeweils ein weiteres Paar. Jedes Paar vermehrt sich genauso. Wie viele Paare gibt es (Todesfälle ausgeschlossen) im Jahresverlauf ?

Von Monat zu Monat ist 1, 1, 2, 3, 5, 8, ... die Anzahl der Kaninchenpaare - jede Zahl > 1 ist die Summe der beiden vorangegangenen Zahlen. Dieses Verfahren lässt sich auf verschiedene Phänomene anwenden, wobei meist viel größere Zahlen gesucht sind. Anstatt ständig zu addieren, kann man dann die Formel von Jaques Binet (1786 - 1856) anwenden:

Fibonaccizahlen

Anfrage:  Cindy Rath, web
Ich meiner Facharbeit geht es um Fibonacci-Zahlen und den Goldenen Schnitt. Nach der Formel von Binet lässt sich die n-te Fibonacci-Zahl an wie folgt berechnen:
Formel von Binet.
Bei der Herleitung der Formel wird in der Literatur vorausgesetzt, dass die Fibonacci-Folge eine geometrische Folge ist. Dann ist qn das n-te Folgeglied und somit gilt: qn+2 - qn+1 - qn = 0 usw. Das ist mir klar, aber wieso ist 1, 1, 2, 3 ... eine geometrische Folge?

Antwort:

Die besagte „Herleitung” ist zwar einfach und populär aber leider nur ein Taschenspielertrick; die Fibonaccizahlen bilden natürlich keine geometrische Folge, weil die Quotienten aus benachbarten Folgegliedern verschieden sind.

Die wirkliche Herleitung erfordert ein wenig lineare Algebra: Zuerst erweitert man die Fibonaccifolge um das Glied ao = 0 und ersetzt die Rekursionsgleichung an+2 = an+1 + an durch an+1 = an + an-1. Mit der Gleichung an = an + 0 · an-1 ergibt das ein lineares Gleichungssystem. A sei die entsprechende 2×2-Matrix, dann liefert das Produkt An · (1,0)t die Formel von Binet. Das eigentliche Problem, die Potenz An zu berechnen, lässt sich durch Diagonalisierung der Matrix A lösen.

Erläuterungen zur Diagonalisierung von Matrizen finden Sie in den Lehrbüchern der linearen Algebra.


Mathematik-Online, Fibonaccizahlen


Bemerkung:

Die Formel von Binet liefert zum Beispiel für n = 30 die Fibonaccizahl:

Explizite Berechnung der Fibonaccizahl a30.  =  832040.

Wir haben oben die Herleitung von Binets Formel skizziert und wollen das jetzt ausführlich darlegen: Die Gleichung an+1 = an + an-1 erweitern wir zum linearen Gleichungssystem

lineares Gleichungssystem

Die obige Matrix bezeichnen wir mit A und erhalten sukzessive:

Jetzt muss man „nur” noch die Matrix A hoch n
         berechnen.

Um die Matrix An effektiv berechnen zu können, fassen wir A als lineare Abbildung (Endomorphismus) h auf, die den Vektor (v1,v2)tIR² auf den Vektor (v1+v2, v1)t  abbildet. Wir suchen jetzt eine IR²-Basis (u,v), so dass h in Bezug auf diese Basis einer Diagonalmatrix

allgemeine 2x2-Diagonalmatrix

entspricht, deren Potenzen man explizit bestimmen kann. Die Zahlen λ und μ bezeichnet man als Eigenwerte von h, sie sind die beiden Nullstellen des charakteristischen Polynoms  x² - x - 1 von h. Daraus folgt: λ = ½ + ½·5 und μ = ½ - ½·5.   Das Additionsverfahren liefert mit Hilfe der Eigenwerte die gesuchten Basisvektoren

Eigenvektoren

die man als Eigenvektoren von h bezeichnet. Bezüglich (u,v) korrespondiert der Endomorphismus h daher zur Diagonalmatrix

Diagonalmatrix

Die Vektoren u, v fassen wir zu einer Matrix B zusammen und bezeichnen die zu B inverse Matrix mit B-1. Es gilt: A = B·D·B-1 und daraus folgt: A² = (B·D·B-1)·(B·D·B-1) = (B·D) ·(B-1·B) · (D·B-1) = B··B-1. Daraus folgt schließlich: An  =  B·Dn·B-1. Damit erhalten wir:

exlizite Berechnung von A hoch n.

Nun kann man das Produkt An·(1,0)t  berechnen und erhält Binets Formel.


Mathematik-Online, Fibonaccizahlen


Dieses Verfahren lässt sich auf alle linearen Rekursionsgleichungen vom Typ an+1 = r·an + s·an-1 übertragen, falls A (also der korrespondierende Endomorphismus h) zwei verschiedene reelle Eigenwerte besitzt. Sonst kann man wie folgt vorgehen:

1. Fall  (Jordansche Normalform)  -  die jeweilige 2×2-Matrix A hat genau einen (doppelten reellen) Eigenwert λ: Wir bezeichnen die Einheitsmatrix mit E, dann besteht die Matrix A - λ·E aus den Zeilen r-λ  s, 1  -λ und ist somit nicht die Nullmatrix. Die Dimension des einzigen Eigenraumes Eλ ist also kleiner als 2, womit A nicht diagonalisierbar ist. Das charakteristische Polynom von A zerfällt aber in reelle Linearfaktoren, folglich existiert eine Basis (u, v) des IR², so dass A in Bezug auf die kanonische Basis sowie die obere Dreiecksmatrix

Jordanmatrix

bezüglich der Basis (u,v) den gleichen Endomorphismus darstellen. Die Matrix B-1 bewirke den entsprechenden Basiswechsel, dann folgt analog zum Fibonacci-Fall: An = B·Jn·B-1. Die allgemeine n-te Potenz von J kann man explizit angeben, ferner lassen sich die Basisvektoren u, v und somit die Matrizen B, B-1 problemlos berechnen. Zum Beispiel erhalten wir für die Rekursionsgleichung   an+1 = 2an - an-1  die Matrix An =

Berechnung von A hoch n.

Für beliebige Startwerte a0, a1 gilt daher: an = n·a1 + (1-n)·a0.


Mathematik-Online, Fibonaccizahlen


2. Fall - es existiert kein reeller Eigenwert:
Die 2×2-Matrix A hat daher zwei konjugiert-komplexe Eigenwerte λ, μ und ist folglich über dem Körper |C der komplexen Zahlen diagonalisierbar. Alle Berechnungen erfolgen analog zur reellen Diagonalisierung. Dabei sind die Rechenregeln für komplexe Zahlen zu beachten.

Ein Beispiel hierzu ist die Gleichung  an+1 = an - an-1.  Daraus folgt:   An =

Berechnung von A hoch n.

Für beliebige Startwerte a0, a1 erhalten wir damit das n-te Folgeglied an =

Komlexe Darstellung des n-ten Folgegliedes.

Diesem Term sieht man zunächst nicht an, dass er für reelle Startwerte selbstverständlich nur reelle Folgeglieder liefern kann, die sich außerdem periodisch wiederholen. Es entpuppt sich jedoch mit Hilfe der Relationen

Eulersche Formel.

die reelle Formel:

reelle Darstellung des n-ten Folgegliedes.

Die Zahlenfolge  an+1 = an - an-1   kann man allerdings auch einfacher in den Griff bekommen. Ansonsten ist das aber selten der Fall, wie sich etwa an der Fibonaccifolge zeigt, für die unser oben beschriebenes Verfahren die elementarste Methode ist, um die explizite Darstellung herzuleiten.
Themenliste Jordansche Normalform