Matrix zur Berechnung von Fibonacci-Zahlen>=2 aus F(1) und F(0)

Neue Frage »

mrclndr Auf diesen Beitrag antworten »
Matrix zur Berechnung von Fibonacci-Zahlen>=2 aus F(1) und F(0)
Ich soll folgende Aufgabe lösen:

Zitat:
Die Fibonacci-Zahlen f_0, f_1, f_2, ... sind durch folgende Rekursion definiert:

f_0=0, f_1=1, f_n=f_(n-1)+f_(n-2) für n>=2.

Lösen Sie folgende Aufgaben:
(a) Berechnen Sie die ersten 15 Fibonacci-Zahlen.
(b) Finden Sie eine Matrix A, sodass gilt

(c) Finden Sie für jedes n>=2 eine Matrix B_n, die folgende Gleichung (1) erfüllt:

Hinweis: Folgende Definition ist hilfreich. Sei C eine nxn-Matrix. Wir definieren C^k als die k-te Potenz von C, d.h. C^k ist rekursiv definiert als C^1=c und C^k=C*C^(k-1). Zum Beispiel, C^4=C*C*C*C.
(d) Beweisen Sie per vollständiger Induktion, dass die Matrix B_n aus Punkt 3 tatsächlich Gleichung (1) erfüllt.

a und b habe ich gelöst, so ist bei b die gesuchte Matrix
.

Durch etwas Googlen und den gegebenen Hinweis habe ich am Ende auch eine Lösung für B_n aus der Aufgabe (c) gefunden, nämlich A^(n-1). Das konnte ich auch gut in (d) beweisen, indem ich A^n im Induktionsschritt als A^(n-1)*A dargestellt habe.

Ich wäre - bzw. bin - aber selber nicht auf die Lösung von (c) gekommen, allenfalls durch glückliches Ausprobieren anhand des Hinweises mit der Potenz. (b) habe ich gelöst, indem ich mir das als lineares Gleichungssystem mit einer Matrix A={(a,b), (c,d)} aufgeschrieben habe. Die Lösung war dann offensichtlich.

Bei (c) habe ich viel mit der Potenz herumprobiert, zunächst mal ganz abstrakt mittels einer Matrix {(a,b), (c,d)} von Unbekannten, das ist aber sehr schnell sehr unübersichtlich geworden beim Multiplizieren und ich konnte nicht wirklich etwas herauslesen. Näher dran war ich dann, als ich mir überlegt habe, dass die gesuchte Matrix die Form B_n={(a,b),(b,c)} haben muss. Das entspricht ja dem Fibonacci-Algorithmus. Aber auch da hätte ich beim Ausprobieren der Multiplikationen nie die "Gesetzmäßigkeit" entdecken/sehen können, dass A^(n-1) die Lösung ist. Das war für mich sehr undurchsichtiger Buchstabensalat.

Möglich, dass ich da einfach an fehlender Rechenübung gescheitert bin. Aber ich denke mir, auch mit dem Hintergrund, was gewöhnlich in dieser Lehrveranstaltung von uns "verlangt" wird, dass ich da vielleicht vom Ansatz her zu kompliziert unterwegs bin und die Herleitung viel einfacher möglich sein müsste. Sorry, dass ich das Problem sehr schwammig beschreibe - aber vielleicht kann mir ja wer einen Ansatz geben, welchen Lösungsweg ich da gehen kann/wie genau ich auf die Lösung komme. Würde das gerne besser verstehen. Danke!
URL Auf diesen Beitrag antworten »
RE: Matrix zur Berechnung von Fibonacci-Zahlen>=2 aus F(1) und F(0)
Wegen

kommt man darauf, dass ist.
Um auszurechnen, benutzt man die Diagonalisierbarkeit von A
mrclndr Auf diesen Beitrag antworten »

Ah. Den Wald vor lauter Bäumen nicht sehen. Hammer Vielen Dank!
URL Auf diesen Beitrag antworten »

Ist doch prima, wenn so ein kleiner Anstoß genügt Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »