LOESUNG DER DISKRETEN FIBONACCI-DGL MITTELS Z-TRANSFORMATION

Die FIBANOCCI ZAHLEN sind schon seit dem Jahr 1200 bestens bekannt.
Es gibt Unmengen an Informationen darueber im Internet. Als eine der auffaelligsten Eigenschaften und wohl auch der direkteste Zusammenhang zur Chaostheorie, wuerde ich folgende nennen.
Der Quotient zweier aufeinanderfolgender Fibonacci Zahlen naehert sich fuer grosse Fib-Zahlen dem goldenen Schnitt. g=(1+sqrt(5))/2
limit (n gegen infinit, Fib(n)/Fib(n+1) = g = (1+sqrt(5))/2)
Und der goldene Schnitt ist als irrationalste aller Zahlen, Anti Periodizitaet, Gegenspieler zu den natuerlichen Zahlen. Allgegenwaertig in der Chaostheorie und auch in der Natur. Es gibt sicherlich einige relativ einfache Methoden um diesen Grenzwert herzuleiten, z.B. auch ueber eine Kettenbruchentwicklung. Folgender Weg ist auch recht interessant ist. Allerdings benoetigt man dazu etwas mehr als Schulmathematik, naemlich die Z-Integraltransformation sowie Partialbruchzerlegung. Beliebte Hilfsmittel bei den Ingenieuren. Wen das abschreckt, der kann sich ja auch nur die Loesung anschauen, die im Prinzip der Formel von Binet entspricht. Diese jedoch mal auch in den komplexen Zahlen betrachtet und schliesslich auch eine sehr schoene Grafik fuer die Fib Zahln in der komplexen Zahlenebene liefert.

Grob die Vorgehensweise :

Die Fib Reihe stellt eine lineare ! Differenzengleichung 2 ten Grades dar.
f(k+2)=f(k+1)+f(k); f(0)=f(1)=1;
*************************

Linear ! d.h. diese Differenzengleichung ist analytisch loesbar. Dies heisst wiederum, dass anstatt der iterativen Gleichung sich ein geschlossener Ausdruck angeben laesst, der die Differenzengleichung loest. Zuer Loesung habe ich die Z Transformation benutzt. Koennte man auch mit einem Exponentialansatz loesen. Es ist einsichtig, dass durch die Loesung schliesslich auch ein Ausdruck vorliegt, der die Fib Zahlen nicht nur auf die natuerliche Zahlen besachraenkt.

**************************************
Z TRANSFORMATION, SCHWIERIGER TEIL
**************************************

f(k+2)=f(k+1)+f(k); f(0)=f(1)=1;
Das ist eine lineare Differenzengleichung 2 ter Ordnung. Diese laesst sich mittels Z-Transformation loesen !
Loesungsskizze:
Verschiebungssatz bei einseitiger Z-Transformation:
Z{x(k+1)}=z^i - summe(j=0..i-1, x(j) * z^(i-j)
In die Summe gehen die Anfangswerte ein. Wir erhalten im Z-Bereich somit:
z^2*F(z)-z^2*f0-z*f1=z*F(z)-f0*z+F(z)
F(z)=z^2/(z^2-z-1)*f0 + z/(z^2-z-1)*(f1-f0)
mit f1-f0=1-1=0
Derjenige der mit dem goldenen Schnitt vertraut ist, sieht jetzt schon in welchem Ausdruck dieser vorkommt:
(z^2-z-1) hat die Nullstellen (1+sqrt(5))/2 sowie (1-sqrt(5))/2
Nennen wir diese g (1.618...) sowie g*(-0.618..)
(z^2-z-1)=(z-g)*(z-g*) (g=Theta+1, g*=-Theta)
Fuer die Ruecktransformation fuehren wir eine Parzialbruchzerlegung durch:
Praktischerweise klammert man dazu ein z im Zaehler aus:
z*(z/((z-g)*(z-g*))=z* r0/(z-g) + z*r1/(z-g*) ....
etwas Grenzwertbetrachtung und man erhaelt:
r0=(sqrt(5)+1)/2/sqrt(5)
sowie
r1=(sqrt(5)-1)/2/sqrt(5)
somit und unter f0=1:
F(z)=r0*z/(z-g) + r1*z/(z-g*)

RUECKTRANSFORMATION :
aus Tabelle:
Z_invers{z/(z-a)}=a^k

*************************
ENDE Z TRANSFORMATION
*************************

LOESUNG:
(Formel von Binet)

fib(k)=r0*g^k + r1*(g*)^k
***********************
ausgeschrieben:
Voila das ist die Fibonacci-Funktion :-)
*********************************************************************
fib(k)= (sqrt(5)+1)/2/sqrt(5)*((1+sqrt(5))/2)^k + (sqrt(5)-1)/2/sqrt(5)*((1-sqrt(5))/2)^k *********************************************************************
Die Eigenschaft Theta+1=1/Theta laest sich auszunuetzen.
Der zweite Summand oszilliert wegen (-1)^k

*************
NAEHERUNG
*************

Fuer grosse Werte strebt der zweite Summand gegen Null.
Es bleibt r0*g^k.
Damit ist folgendes leicht zu erklaeren:
Bildet man die bekannte Form
limit k-> infinit fib(k+1)/fib(k) so erhaelt man
r0*g^(k+1) / r0*g^(k) = g = goldener Schnitt ! :-) THETA+1

***************************************************
DIE FORMEL VON BINET ERZEUGT KOMPLEXE ZAHLEN
***************************************************

Noch eine vereinfachte Schreibweise :
fib(k')=g/sqrt(5)*g^k'-g*/sqrt(5)*(g*)^k'
mit k=k'+1 theta sei 0,681 dann gilt
1/theta=1+theata fib=1/sqrt(5) * (theta^(-k) - (-1)^k * theta^k

Auch hier sieht man wieder , dass die Fibanocci Zahlen eigentlich nichts weiter sind als Potenzen von Theta.
Eine kleine komplexe Schwingung korrigiert die Theta Potenzen, so dass diese zu ganzen Zahlen werden.
Ing Schreibweise mit Exponentialfunktion: (gt = theta =0.681 ...)
fib=1/sqrt(5)*( exp(-k*ln(gt)) - exp(k*ln(-gt)) )

Der ln() aus einer negativer Zahl ist komplexwertig !
***************************************
fib=1/sqrt(5)*( exp(-k*ln(gt)) - exp(k*ln(gt)+j*k*PI) )
***************************************

.... bischen rechnen Die Fibonacci Funktion ist komplex !

Realteil: 1/sqrt(5)*( exp(-k*ln(gt)) - exp(k*ln(gt)*cos(k*PI) ) )
Imaginaerteil: - 1/sqrt(5)*exp(k*ln(gt)*sin(k*PI) )

DARSTELLUNG IN DER KOMPLEXEN EBENE
****************************************

Die Funktion laest sich in der komplexen Ebene parametrisch darstellen
( Dreht der Big Boss Schleifchen ? :-)
Eine sehr schoene Funktion:

Von den neg. Zahlen herkommend dreht sich die Funktion an den Nullpunkt.
Die Spirale entsteht durch eine Phasenschiebung zwischen Real und Imaginaerteil. Im positiven Bereich nimmt die Frequenz des Realteils dann natuerlich kontinuierlich ab. Einen Teil der Rechnerei kann man sich natuerlich auch sparen, indem man einfach die Formel von Binet in die Differenzengleichung einsetzt um zu zeigen dass diese eine Loesung darstellt.

Irgendwann 2005