Math - f(n)=r*f(n-1)+f(n-2)

[richy]

Hi
Zur Entspannung spiele ich mal wieder bischen mit Zahlen.

Gegeben sei die DZGL (modifizierte Fibonacci Folge)
f(n)=r*f(n-1)+f(n-2), f(0)=f(1)=1
Wie lautet der Grenzwert
g=limit n=infinity f(n+1)/f(n) ?

Man koennte nun so vorgehen, dass man die DZGL loest und dann das Verhaeltnis bildet. Das waere aber recht aufwendig.
Maple macht hier schlapp. Mittels z-Transformation koennte man die Aufgabe in der Vorgehensweise loesen. Aber mit immensem Rechenaufwand.
Hier hab ich das mal fuer r=1 von Hand gerechnet :
http://home.arcor.de/richardon/richy...c/fib/fib1.htm

Ich versuche die Aufgabe ueber einen voellig anderen Ansatz einer DZGL 1.ter Ordnung zu loesen.
Warum dieser Ansatz zum Erfolg fuehrt basiert auf meiner Erfahrung mit der Kettenbruchdarstellung der DZGL 1 ter Ordnung im Loesungsansatz.
Fuer die Loesung des Problems ist diese Kettenbruchentwicklung aber nicht direkt erforderlich.
Ich habe die Betrachtungen daher in quotes geschrieben.
Man kann diese auch weglassen.
EDIT
ES GIBT EINEN SEHR VIEL EINFACHEREN WEG ALS FOLGENDEN HERLEITUNG :
Die Rechnung im Zitatkasten kann man uebergehen.

Zur Loesung betrachte ich also zunaechst die DZGL 1.Ordnung
1) s(n+1)=r+1/s(n) s(0)=1

Nun betrachte ich Zahler und Nenner von s(n) getrennt
s(n)=Z(n)/N(n) Z(0)=N(0)=1
(Ich formulier die Gleichung also um auf ein System, dass sich spaeter als eine DZGL 2.ter Ordnung erweisen wird)

Damit erhalte ich aus 1):
Z(n+1)/N(n+1)=r+1/[Z(n)/N(n)]
Die rechte Seite laesst sich umformen zu :

r+1/[Z(n)/N(n)]=(r*[Z(n)/N(n)]+1)/(Z(n)/N(n)]=
[(r*Z(n)+N(n))/N(n)]/[Z(n)/N(n)=
(r*Z(n)+N(n))/Z(n)
***************

Der neue Zaehler setzt sich zusammen aus alten Zahler multipliziert mit r zu dem ich den alten Nenner addiere.
Der neue Nenner ist einfach der alte Zaehler.
Damit kann ich den Nenner in 2) auch als Zaehler ausdruecken :
3) N(n)=Z(n-1)
Gleichung 3) setze ich in Gleichung 2) ein und erhalte (wie von Zauberhand )

4) Z(n+1)=r*Z(n)+Z(n-1)
********************
Der Zahler verhaelt sich also wie die modifizierte Fibonacci DZGL der Aufgabenstellung ! Was fuer ein Zufall *fg
Und jetzt loest sich alles in Wohlgefallen auf, denn 3) lautete ja :
3) N(n)=Z(n-1)

Damit ist die DZGL s(n+1)=r+1/s(n) s(0)=1 mit s(n)=Z(n)/N(n)
darstellbar als :
4) Z(n+1)=r*Z(n)+Z(n-1)
3) N(n+1)=Z(n)
oder ausgeschrieben : s(n+1)=Z(n+1)/Z(n)
mit Z(n+1)=r*Z(n)+Z(n-1)

EINFACHER WEG :
f(k+1)=r*f(k)+f(k-1) , auf beiden Seiten durch f(k)
f(k+1)/f(k)=r+f(k-1)/f(k)
Substitution s(k+1)=f(k+1)/f(k) => f(k-1)/f(k)=1/s(k)

Die Iterationswerte der Gleichung s(n+1)=r+1/s(n)
entsprechen also fuer jedes n dem Quotienten zweier aufeinanderfolgender Werte der modifizierten Fibonacci Folge.

Ach so. Was ist mit der Loesung von s(k+1)=r+1/s(k) ?
Die DZGL hat einen Attraktor fuer s(k+1)-s(k)=0
also r+1/s(k)-s(k)=0 => r+1/s(k)=s(k), na schon wieder so ein Zufall :-)

Die Werte streben also gegen
s1=1/2*r+1/2*Wurzel(r^2+4) oder
s1=1/2*r+Wurzel(r^2/4+1)
Fuer r=2 ergibt sich 1+Wurzel(2)



VOILA !

[richy]

BTW
Wie bin ich zu diesem Loesungsansatz gekommen ?

Ueber den goldenen Schnitt.
Der ist bekanntlich der Quotient zweier aufeinanderfoldender Fibonacci Zahlen.
Diese koennen durch die bekannte DZGL 2 ter Ordnung gebildet werden.

Der goldene Schnitt kann aber auch als Kettenbruch mit den Koeffizienten [1,1,1,1 ...] dargestellt werden.
Programmiert man diese Kettenbruchdarstellung, so ist es zweckmaessig Nenner und Zaehler getrennt zu betrachten. Alleine hier sieht man schon den Zusammenhang zur Fibonacci DZGL

Letzter Schritt :
Um die doch recht unhandliche Kettenbruchdarstellung zu vermeiden kann man diesen im einfachen Fall auch als eine DZGL 1.Ordnung formulieren.
Uber die verkettete Uebertragungsfunktion wie ich es oben beschrieben habe.
http://home.arcor.de/richardon/richy...tic/sofort.htm
Der Loesungsansatz ist mir also doch nicht einfach zugeflogen :-)

[Hamilton]

Hi,
ich hab jetz nicht alles durchgelesen, aber ich hab ein paar Vorschläge:
1. Wenn Du auf deiner Homepage eine längere Rechnung veröffentlichst, dann ist es absolut unentschuldbar Terme in dieser ASCII-Form etwa f(x)=r^2*(1-(1/(1-x)).... zu schreiben- das sieht einfach sch... aus und das liest sich dann auch niemand durch.
Versuche unbedingt mal LaTeX... Damit kann man schöne Formeln setzen, das ist auch gar nicht so schwer. Latex ist freeware und es gibt sogar ein Programm Latex2Html, das aus dem Ergebnis (üblicherweise ein .dvi oder .ps bzw. .pdf file) ein html doukument macht, das dann hübsch aussieht.

2. ich kenne die modifizierte fibonaccifolge nicht, aber wenn du einen Grenzwert suchst- hast du schon mal versucht die fixpunkte der DZGL auszurechnen?
Also einfach die Gleichung x=f(x) lösen und gucken, ob solch ein x (oder mehrere) existiert?
Ich würde ja denken, dass wenn die die folge gegen einen Wert konvergiert, dann gegen einen ihrer Fixpunke, einen stabilen natürlich.

[soon]

Hallo Richy,
vielleicht sollten ein wenig über die logistische Gleichung plaudern, oder allgemeiner über Gesetzmässigkeiten innerhalb nichlinearer dynamischer Systeme.

Ich versuche mal hier zwei screenshots reinzustellen, - wahrscheinlich muss ich mir aber erst woanders Webspace zulegen.

http://212.80.228.216/sites/frvoeller/parab002.jpg
http://212.80.228.216/sites/frvoeller/parab003.jpg

kann man die Bilder sehen?

Gruss
soon

[Hamilton]

Übrigens:
Ich hab mir grad mal deine Homepage angeschaut und deien Beweis für sqrt(2) ist keine rationale zahl angesehen. Der ist ja ganz schön lang. Kennst Du den?
Beweis durch Widerspruch:
Wenn sqrt(2) eine rationale Zahl ist, dann existiert ein Bruch a/b = sqrt(2), wobei a/b teilerfremd ist.(oder auch maximal gekürzt)
jetzt geht's los:
a²/b² = 2 => a² = 2b² also ist a² eine gerade Zahl, damit auch a, also a =2n
4n²/b² = 2 => b² = 2n² also ist b² auch eine gerade Zahl, damit auch b
=> Widerspruch zur Teilerfremdheit.
Ich gebe aber gern zu, dass der nicht auf meinem Mist gewachsen ist.

[Hamilton]

ja schon, hast du einen eigenen Webserver laufen?
Du kannst aber, wenn du die Bilder etwas stärker komprimierst, die Bilder hier direkt ins Forum laden.
Du solltest vielleicht sagen, was man da sieht.
Ok, links erkenne ich so eine cobweb konstruktion- den anderen kram solltest du mal erläutern.

[richy]

Hi Hamilton
Ich gehe davon aus, dass das Meiste auf meiner Webseite groesstenteils von mir gelesen wird. Es sind eher Merkzettel. Nur bei Dingen die mir besonders wichtig schienen habe ich auch Formeln als Bilder von Maple dargestellt. Du hast natuerlich recht und danke mit dem Tipp mit Latex.
Das Prob mit der modifizierten Fibonaccifolge habe ich doch schon geloest. Und letztendlich mit der Fixpunktmethode.

Ach so. Was ist mit der Loesung von s(k+1)=r+1/s(k) ?
Die DZGL hat einen Attraktor fuer s(k+1)-s(k)=0
also r+1/s(k)-s(k)=0 => r+1/s=s, na schon wieder so ein Zufall :-)

Die Fib Folge hat keinen Attraktor. Aber der Quotient zweier folgender Werte strebt fuer r=1 bekanntlich gegen den goldenen Schnitt.
Auf diesen Quotient kann ich aber direkt keine Fixpunktmethode ansetzen.

Es ist einfach :
Der Quotient q(n) zweier aufeinanderfolgender Werte der Gleichung
1) f(n)=r*f(n-1)+f(n-2), f(0)=f(1)=1
***************************
hat den selben Wert wie
2) q(n)=r+1/q(n-1), q(0)=1 (dies zu zeigen ist der Trick.Ansatz: q(n)=Z(n)/N(n))
********************
(Die Gleichung 1 selbst divergiert)
Und den Grenzwert von 2) fuer n=00 liefert mir die von dir erwaehnte Attraktormethode.
Er erfuellt die Gleichung
q=r+1/q (Anm: Das ist die charakteristische Gleichung der Z Transformierten von Gl1)
q1=1/2*r+Wurzel(r^2/4+1)
*******************

Fuer r=1 ist das z.B.der goldene Schnitt
(Gl 2) stellt auch dessen Kettenbruch dar,Ueber den bin ich ueberhaupt auf diesen Loesungsansatz gekommen )

Den Beweis von Euklid kenne ich natuerlich :-)
Bei mir ist nur die Vorueberlegung bischen laenger. Letztendlich bekomme ich eine Arbeitsanweisung :
Wenn frac(s)=frac(1/s) ist s irrational.
Die ist aufgruend der Kuerze praktischer als Euklid.
Mit meinem Gedaechntnis ist es nicht so weit her :-)

Probiers mit 1 + Wurzel(2) einfach mal aus.
Es ist aber keine notwendige sondern nur hinreichende Bedingung.

@soon
Das sind Bilder der logistischen Gleichung ?
Links oben die Iteration ueber die 45 Grad Linie, Rechts oben kenne ich nicht.
In der Mitte der zeitliche Verlauf. Unten kenne ich auch nicht.

Die Darstellung links oben bringt meiner Meinung nicht viel.
Am leistungsfaehigsten ist die Darstellung ueber verkettete Polynome.
Damit kann man einiges loesen, was loesbar ist.
Ich hab sogar die Loesung fuer r=2 gefunden.
Und ich kann auch die Nullstellen aller Loesungen in der komplexen Ebene darstellen.
Und weil die recht boesartig aussehen meine ich: Ausser fuer r=2 ist kaum eine weitere Loesung moeglich.

Aber klar, wir koennen ueber die Verhulst Gleichung gerne diskutieren.
Der Uebergang zum grossen Fenster scheint ein ganz besonderer Parameter r=1+Wurzel(8)
Auch die Eigenschaften der verketteten Polynome waere nochmals eine Betrachtung wert.
Und die scheinbare "ergodizitaet" der Ruckwaertsiterierten, der Nullstellen.
Wie sind deine Erfahrungen mit dem Monster ?

BTW: frac(s*n) ist eine chaotische Funktion wenn s irrational ist.

[soon]

Hi,
@Hamilton
nee, kein eigener Webserver, nur Webspace für eine Visitenkartenseite. Ich weiss nicht, was die mir abbuchen, wenn da ein wenig Trafic entsteht. Die Bilder stärker komprimieren macht Sinn, - direkt hier reinstellen nicht, da bei jedem Threadöffnen neu geladen würde.


@richy
ja, alle 4 Grafiken stellen auf unterschiedliche Weise das Gleiche dar, die logistische Gleichung oder Verhulstgleichung : x_n = ax_n-1(1 - x_n-1) mit a =4


Grafik obenlinks: die grafische Veranschaulichung des Iterationsvorgangs. Ein Startwert (hier 0,3) wird auf der rechten Seite der Gleichung eingesetzt (Iterationsschritt n) . Der neue Wert x_n wird im nächsten Iterationsschritt wieder auf der rechten Seite eingesetzt usw. - es ensteht eine Folge von Iterationswerten.
Der Attraktor der Folge ist 0,75.Grafisch veranschaulicht ist das Wiedereinsetzen des y-Wertes eine Spiegelung an der Winkelhalbierenden. Bei unterschiedlichen Parametern a verhält sich die Folge unterschiedlich: für a gößer 0 und kleiner 4 entsteht eine periodische Folge (Genaueres kann man woanders nachlesen, Stichwort : Feigenbaumkonstante). Für a = 4 ensteht eine chaotische Folge. Alle Werte liegen zwischen 0 und 1, aber welcher Wert im nächsten Iterationschritt entsteht, lässt sich nur durch schrittweises Errechnen ermitteln.

Grafik obenrechts: ist nicht wichtig, nur eine Darstellung von jeweils Schritt1 auf Schritt2

Grafik mitte: der zeitliche oder besser schrittweise Verlauf der Iterationswerte, 0,75 ist Attraktor, wird aber nie erreicht.

Grafik unten: Wenn man alle Iterationswerte nacheinander aufaddieren würde, entstünde eine etwas 'zackelige' aber konstant steigende Linie, da alle Einzelwerte >0 und <1. Deshalb subtrahiere ich von jedem Iterationswert 0,5 so dass jeder einzelne Iterationwert zwischen -0,5 und 0,5 liegt. Der Informationsgehalt des Iterationsverlaufs ändert sich dabei nicht, da sozusagen nur die y-Achse verschoben wird. Danach werden die Werte schrittweise aufaddiert und gezeichnet. Die enstehende Grafik hat schon in dieser Darstellung (mit nur 2000 Werten) grosse Ähnlichkeit mit z.B. einem Börsenkursverlauf. Bei einer grösseren Anzahl von Iterationswerten benuzte ich die üblichen open-high-low-close-Charts. Eine Unterschied zu einem Indexkursverlauf, Euro/Dollar oder dergleichen ist dann nicht mehr vorhanden.



Die Fragen, um die es geht ist einfach: wie geht es weiter? Kann ich aus der Kenntnis des vorhandenen Verlaufs heraus Aussagen über den weiteren Verlauf machen? Dabei geht es mir nicht nur um Börsenkurse, sondern um alle Systeme die aus vielen winzigen Einzelschritten bestehen, bei denen jeder Schritt abhängig ist vom Schritt zuvor.

Gruss
soon

[soon]

Hi,

zitat richy:
<Die Darstellung links oben bringt meiner Meinung nicht viel.>

Doch, immerhin ist es die grafische Herleitung einer chaotischen Zahlenfolge.
Daraus lässt sich folgender Schluss ziehen: die Enstehung einer chaotischen Iterationsfolge ist unabhängig von der Grösse der Parabel. D.h. die Parabel kann auch viel kleiner oder viel grösser sein. Der Parabelabschnitt muss lediglich genauso hoch wie breit sein.
Analog zu : Wenn ich den Satz des Pythagoras grafisch herleiten will, brauche ich ein rechtwinkliges Dreieck,- die Herleitung ist unabhängig von den Seitenlängen des Dreiecks.

Screenshots mit einem Parabelabschitt durch die Punkte (0;0) (15;30) (30;0) :

http://212.80.228.216/sites/frvoeller/parab004.jpg
http://212.80.228.216/sites/frvoeller/parab005.jpg

Die allgemeine Form einer quadratischen Gleichung lautet y = ax² + bx + c .
Bei der Verhulstgleichung mit dem Parameter 4 ist a = -4 ; b = 4 ; c = 0. Dass a = -4 sein muss ist also eine überflüssige Einschränkung. Zur Enstehung einer chaotischen Folge genügt es, dass a negativ ist!

Gruss
soon

[richy]

Hi soon

Zur Enstehung einer chaotischen Folge genügt es, dass a negativ ist!

Das ist eine notwendige aber keine hinreichende Bedingung. Ansonsten koennte man doch genau analytisch berechnen fuer welchen Parameterwert der LG der uebergang zum Chaos stattfindet. Der Wert des Feigenbaumpunktes ist aber nicht genau bekannt.
Ansonsten ist der spezielle Parameterwert 4 damit verknuepft, dass die Gleichung y(k+1)=r*y(k)*(1-y(k)) auf den Maximalwert 1 normiert ist.
Allgemeiner waere y(k+1)=r*y(k)*(a-y(k))=r*a*y(k)-r*y(k)^2

Du summierst in der unteren Darstellung alle Werte auf. Wenn du durch die Anzahl Iterationsschritte teilen wuerdest, entspraeche dies dem Mittelwert der Iterationswerte. EInen Ueberblick darueber kannst du dir auch ueber das Feigenbaumdiagramm oder die verketteten Polynome schaffen.
Letztere kannst du iterativ erzeugen. Z.B. ueber ein analytisches Mathematikprogramm wie Maple.
Oder du berechnest die Iteration fuer alle Anfangswerte 0..1 und stellst diese in jedem Iterationsschritt dar. Genau das stellen die verketteten Polynome dar : Die allgemeine numerische Loesung der Gleichung fuer jeden Iterationsschritt.
Siehe auch:
http://home.arcor.de/richardon/richy...lytic/ana6.htm
Das ist ein maechtiges Hilfsmittel fuer die Verhulst Gleichung.

In dem Bild siehst du die Parabel a*y*(1-y)

Fuer den Parameterwer 4 waere der Maximalwert 1 und daher der stabile Bereich ueberschritten.
Wobei es fuer a>4 auch stabile Bereiche gibt, die eine Cantormenge bilden.