Fibonacci

Numerische Methoden zur Bestimmung der Wurzeln von Polynomen.

Wir werden uns einige Methoden zur Lösung der Gleichung

x² - x - 1 = 0
anschauen.

Methode 1:
Schreibe die Gleichung in die Form x = 1 + 1/x.
x = 1 + 1/x
Substitution dieser Gleichung in sich selbst führt zu x = 1 + 1/(1 + 1/x).
Wiederholen wir diesen Vorgang immer von Neuem dann entsteht die Vermutung dass

Die Zahl x ist nun geschrieben in der Form eines sogenannten Kettingbruchs.


Die Folge der Teilbrüche

strebt der positiven Nullstelle zu.

Methode 2:
Schreibe jetzt die Gleichung in die Gestalt x = (1 + x)
Wenn wir nun wieder den Trick der wiederholten Substitution anwenden, dann führt uns das zu der Vermutung dass

x = (1 + (1 + (1 + ...)))
Endliche Teile konvergieren gegen die positive Wurzel.
Die erste Methode ist oft anwendbar für Polynome zweiten Grades, die Zweite für Polynome zweiten und dritten Grades. Die dritte und letzte Methode ist am Nützlichsten; sie eignet sich im Algemeinfall.

Methode 3:
Multipliziere die Gleichung mit xⁿ: xⁿ⁺² = xⁿ⁺¹ + xⁿ
Mit G_n = xⁿ gilt also G_n+2 = G_n+1 + G_n für jedes n.
n -> xⁿ ist nicht die einzige Function die der Rekursion genügt (n -> F_n ist eine andere). Eine wichtige Frage ist, ob wir anhand der Rekursion die positive Wurzel errechnen können. Dazu dividieren wir zunächst die Rekursion durch G_n
G_n+2/G_n = G_n+1/G_n + 1 oder (G_n+2/G_n+1)* (G_n+1/G_n) = G_n+1/G_n + 1.
Wir stellen fest, dass wenn G_n+1/G_n gegen a konvergiert, dann ist a² = a + 1, also ist a die verlangte Wurzel.
Also, fangen wir an mit zwei Anfangswerten, zum Beispiel G₀ = 1, G₁ = 2. Dann konvergiert G_n+1/G_n gegen eine Wurzel.
Methode 1 hat eine enge Verwandschaft mit dieser Methode, denn die endligen Kettenbrüche aus Methode 1 haben die Form F_n+1/F_n.
Drollig ist, dass wir gewohnt sind mit Hilfe der oben erwähnten quadratischen Gleichung eine allgemeine Formel für die Fibonaccifolge auf zu stellen. Hier drehen wir die Sache um und nutzen die Fibonacci Rekursion zur Lösung der quadratischen Gleichung.
Die Methode ist ziemlich allgemein brauchbar zur Bestimmung einer Wurzel eines Polynoms. Ein Beispiel. Wir suchen eine Nullstelle des nächsten Polynoms

x³ - 3x² + 2x - 1 = 0

Die zugehörige Rekursion lautet G_n+3 = 3G_n+2 -2G_n+1 + G_n.
Wenn G₁ = 1, G₂ = 1, G₃ = 0, dann ist G₁₀/G₉ = 2,3265. Die reelle Nullzahl der Gleichung ist 2,3247.