Hallo,
weiss jemand wie man schnell eine Matrize ^ n berechnet?
Es gibt da wohl eine berechnung in nur logarithmusirgendwas von n Schritten.
Danke
Bruno Haller
Hi Bruno,
sehr effektiv dürfte das Vorgehen sein, die Matrix zunächst zu diagonalisieren oder auf Jordan-Normalform zu bringen. Der Aufwand hierfür ist gering im Vergleich zum Potential der Einsparung. Dann erfolgt die Potenzierung und anschließend die Rücktransformation.
Gruß
Ted
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Ouuuh, da haste mich aber auf dem falschen Fuss erwischt *g* davon hab ich nämlich keine Ahnung, hehe, ich weiss grad mal so ungefähr wie das mit den Matrizen geht.
Ach ja, es geht um eine ganz spezielle Matrize, nämlich
[[0,1]
[1,1]]
die um n potenziert werden soll.
anscheinend geht sowas mit logarithmischen Aufwand
Ne URL dazu:
http://xi.nu/gnu/calc/calc_96.html
Bruno
Hi nochmal, Bruno.
Auch auf die Gefahr hin, Dir mathematisch einiges zuzumuten, versuche ich mal an der Erklärung des Vorgehens:
Die von Dir angegebene Matrix [[0,1][1,1]] beschreibt eine Abbildung im R^2, einen sogenannten Endomorphismus. Dabei geht die Voraussetzung ein, dass der R^2 mit seiner kanonischen Basis versehen ist, ergo die Basiselemente die Einheitsvektoren [1,0] und [0,1] sind, also in Richtung der x- und y-Achse liegen. Unter gewissen Voraussetzungen, deren Erläuterung hier zu weit führen würde, gibt es ein Koordinatensystem, bezüglich dessen die Matrix die Gestalt [[Ew1,0][0,Ew2]] annimmt. Solche Endomorphismen nennt man normal. An der Abbildung selbst ändert sich jedoch nichts. Du kannst Dir das etwa so vorstellen, als wenn man einen Ballwurf berechnet. Der eine legt den Nullpunkt seines Koordinatensystems an die Abwurfstelle, der andere an den Zielpunkt, aber beide errechnen dasselbe Ergebnis. Nur ist das Koordinatensystem hier nicht verschoben, sondern gedreht. Die Zahlen Ew1 und Ew2 nennt man dann Eigenwerte der Matrix, die Elemente der neuen Basis sind die zugehörigen Eigenvektoren. Charakteristisch ist, dass das Produkt aus Matrix und Eigenvektor das eigenwertfache des Eigenvektors ergibt.
Jetzt kann man leicht sehen, dass die Matrix der Gestalt [[Ew1,0][0,Ew2]] sehr einfach potenziert werden kann, es gilt nämlich
[[Ew1,0][0,Ew2]]^n = [[Ew1^n,0][0,Ew2^n]],
das Potenzieren der Matrix reduziert sich also auf das zweifache Potenzieren von (hier zum Glück) reellen Zahlen, wenn man in das richtige Koordinatensystem geht.
Die Eigenwerte der von Dir gegebenen Matrix lauten
1/2 + sqrt(5)/2 und 1/2 - sqrt(5)/2,
die zugehörigen Eigenvektoren
[1, 1/2 - sqrt(5)/2] und [1, 1/2 + sqrt(5)/2]
Damit wird die Transformation vom neuen in das alte Koordinatensystem durch die Matrix
[[1,1] [1/2 - sqrt(5)/2, 1/2 + sqrt(5)/2]]
beschrieben, dir Rücktransformation durch die inverse Matrix
[[1/2 + sqrt(5)/10, -sqrt(5)/5][1/2 - sqrt(5)/10, sqrt(5)/5]].
Damit ergibt sich als Rechenvorschrift:
[[0,1][1,1]]^n =
[[1,1] [1/2 - sqrt(5)/2, 1/2 + sqrt(5)/2]] *
[[(1/2 + sqrt(5)/2)^n,0] [0,(1/2 - sqrt(5)/2)^n]] *
[[1/2 + sqrt(5)/10, -sqrt(5)/5][1/2 - sqrt(5)/10, sqrt(5)/5]]
Der Aufwand für die Transformation ist dabei für wachsendes n konstant, der für das Potenzieren der Fließkommazahlen hängt von der Implementation ab, da es im Rechner üblicherweise durch die Logarithmusfunktion erledigt wird. Das eigentliche Problem bei der Sache ist, dass die Zahlen sehr schnell sehr groß werden, sodass Rundungsfehler zunehmend eine Rolle spielen.
Ich hoffe, das war nicht zu kompliziert.
Gruß
Ted
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Ich hoffe, das war nicht zu kompliziert.
Ääääh… naja 
ok, von Eigenwerten hab ich schonmal was gehört. Nur läuft deine Lösung eigentlich genau wieder auf eine Formel raus, die ich mit der Matrizenmultiplikation zu umgehen versuchte
Der Rundungsfehler ist genau mein Problem gewesen, der pflanzt sich derart rasend fort.
Ich bräuchte irgendwas mit ganzen Zahlen am besten 
bin mal gespannt ob ich das noch eines Tages rauskrieg
Bruno
Lieber Bruno,
hier die Lösung für das Potenzieren von Matrizen in O(log(n)).
Wenn exp(A,n) die n-te Potenz der Matrix A berechnen soll, schreibst Du Dir zwei Funktionen mul(A,B) (multipliziert Matrix A mit B) und square(A) (quadriert Matrix A).
Jetzt definierst Du exp(A,n) folgendermaßen:
(Pseudo-Code)
Matrix exp(Matrix A, int n)
{
if (n mod 2 == 0)
return exp(square(A), n/2);
else
return mul(A, exp(A, n-1));
}
Dieser Algorithmus läuft in logarithmischer Zeit ab. Der Ansatz beruht darauf, daß A^n =
(A^2)^(n/2), wenn n gerade ist. Geht übrigens auch, wenn Du irgendetwas anderes otenzieren willst als Matrizen.
Außerdem ist die rekursive Formulierung in meinem Algorithmus auch ohne großen Aufwand in eine iterative zu transformieren, dürfte dann noch schneller laufen. Wofür brauchst Du eigentlich so große Fibonacci-Zahlen, rein akademisches Interesse?
Bernd
Wofür brauchst Du
eigentlich so große Fibonacci-Zahlen,
rein akademisches Interesse?
gar nicht ja reine Studienzwecke, will ein wenig angeben hehe und die Zwei die diese Aufgabe haben übertrumpfen.
Am besten sollte die 5Millionste Fibonacci-Zahl in weniger als 20 Minuten rauskommen, wie es anscheinend letztes Jahr oder so die Studenten geschafft haben.
Bruno
Am besten sollte die 5Millionste
Fibonacci-Zahl in weniger als 20 Minuten
rauskommen, wie es anscheinend letztes
Jahr oder so die Studenten geschafft
haben.Bruno
20 min auf welcher Hardware und mit welcher Sprache? Mein Ansatz schafft die 5Millionste in ca. 50 min in Java auf nem PII-300, da ist aber noch viel zum optimieren, außerdem läufts unter C noch ne ganze Ecke schneller, könnte das ganze sicherlich unter 20 min schaffen, Interesse an weiteren Infos?
Bernd
20 min auf welcher Hardware und mit
welcher Sprache?
Weiss ich leider nicht. Aber ich glaub das war so ne ältere Alpha-Mühle mit Digital UNIX, die sie jetzt ausgemustert haben, nichts grossartiges.
Mein Ansatz schafft die
5Millionste in ca. 50 min in Java auf
nem PII-300, da ist aber noch viel zum
optimieren, außerdem läufts unter C noch
ne ganze Ecke schneller, könnte das
ganze sicherlich unter 20 min schaffen,
Interesse an weiteren Infos?
Sure! Kannst du mir die Source schicken?
Kann zwar kein java, aber soviel ich weiss is die Syntax halbwegs C-ähnlich.
Ich scheitere grad im Moment an der Implementierung der grossen Zahlen im Rechner, nachdem ich das Rechenverfahren jetzt ansich weiss
Bruno