Eigenwerte kleiner Matrizen

8

Ich schreibe eine kleine numerische Bibliothek für 2x2-, 3x3- und 4x4-Matrizen (real, unsymmetrisch).

Viele numerische Analysetexte empfehlen dringend, die Wurzeln des charakteristischen Polynoms nicht zu berechnen, und empfehlen die Verwendung des doppelt verschobenen QR-Algorithmus. Die Größe der Matrizen lässt mich jedoch fragen, ob es einfach ausreichen kann, einfach das charakteristische Polynom zu berechnen und die Wurzeln zu finden. Ich habe diese Antwort auf StackExchange gefunden , die dies unterstützt, aber ich weiß, dass Fehler in den Polynomkoeffizienten ungenaue Nullen des Polynoms (und damit unterschiedliche Eigenwerte) erzeugen können. Andererseits ist die Gleichung bestenfalls vierteljährlich und wir haben analytische Formeln für die Polynomwurzeln, damit wir nicht zu weit weg kommen.

Was sind die Vor- und Nachteile der Verwendung des charakteristischen Polynoms, um Eigenwerte speziell für diesen Fall zu erhalten?

CADJunkie
quelle

Antworten:

12

Das erste, was zu beachten ist, ist, dass die Entsprechung zwischen dem Finden der Wurzeln eines Polynoms (eines beliebigen Polynoms) und dem Finden der Eigenwerte einer beliebigen Matrix wirklich direkt ist und ein reichhaltiges Thema darstellt, siehe Pseudozeros von Polynomen und Pseudospektren von Begleitmatrizen von Toh und Trefethen und die Referenzen dort.

Grundsätzlich ist der 2 × 2-Fall trivial und die Standardformel ist numerisch stabil und genau, solange die Determinante genau ausgewertet wird - die direkte Formel ist ungenau, wenn , aber es gibt eine genaue Formel aufgrund von Kahan, die FMAs verwendet ( https://hal.inria.fr/ensl-00649347v1/document ).

x1=bsign(b)Δ2a,x2=c/(ax1),Δ=det(b2a2cb)
Δb24ac

Selbst für kubische Polynome gibt es kein solches direktes Äquivalent. ( Bearbeiten: Siehe den Link zu Kahans Methode unten in CADJunkies Kommentar. Dies könnte durchaus falsch sein. ) Die direkte Formel ist nicht immer numerisch stabil (entgegen Ihrer Annahme, denke ich) und kann nicht gleich numerisch stabil gemacht werden Weg wie die quadratische Formel durch Einfügen der richtigen Zeichen irgendwo. Sie können versuchen, es mit besonderer Genauigkeit auszuwerten, z. B. mit doppelter nativer Arithmetik. Die Ansätze, die direkt auf das Polynom wirken, sind jedoch ziemlich kompliziert. Zum Beispiel ( https://doi.org/10.1145/2699468 , das auch für Quartic-Polynome funktioniert) könnten Sie Newtons Methode mit einer guten vorberechneten ersten Vermutung verwenden, aber sie wird wirklich ziemlich kompliziert und die Beschleunigung ist nicht einmal allzu groß .

Die expliziten Formeln für Polynome 4. Grades sind ebenfalls nicht immer numerisch stabil. Die Polynome, die am härtesten sind, haben in der Regel ungewöhnliche Wurzeln (klein oder nahe beieinander, die sich in ihrer Größe stark unterscheiden), aber selbst das Testen Ihres Codes an einigen Milliarden rein zufälligen Polynomen kann normalerweise numerische Fehler aufdecken.

Eine merkwürdige Sache, die damit zusammenhängt, ist, dass Jenkins-Traub, ein guter üblicher Weg, um Polynomwurzeln zu finden, tatsächlich ein getarnter Eigenwertalgorithmus (inverse Iteration) ist.

Ich würde sagen, dass die Aussagekraft der Formeln in gewisser Weise irreführend ist: Sie werden zu der Annahme verleitet, dass die Formel eine geschlossene Form hat, was bedeutet, dass sie irgendwie billiger / einfacher ist. Ich würde wirklich empfehlen, dass Sie dies tatsächlich anhand einiger Testdaten testen / vergleichen. Es muss nicht wahr sein: Die Bestimmung der Wurzeln von Grad- Polynomen liegt innerhalb eines kleinen ganzzahligen Schwierigkeitsfaktors des vollständigen Problems der Bestimmung der Eigenwerte einer kleinen Matrix, und die Standardbibliotheksroutinen für Eigenwerte sind viel robuster und gut getestet. Indem Sie das Problem des kleinen Eigenwerts auf ein Problem mit Polynomwurzeln niedrigen Grades reduzieren, müssen Sie es nicht unbedingt vereinfachen.3

Was sind die Vor- und Nachteile der Verwendung des charakteristischen Polynoms, um Eigenwerte speziell für diesen Fall zu erhalten?

Ich denke, der Hauptnachteil ist, dass diese Annahme, die Sie machen:

Andererseits ist die Gleichung bestenfalls vierteljährlich und wir haben analytische Formeln für die Polynomwurzeln, damit wir nicht zu weit weg kommen.

Da eine Formel in geschlossener Form und analytisch vorliegt, bedeutet dies, dass sie einfach / billig / genau ist, ist dies nicht unbedingt der Fall. Es könnte für bestimmte Daten zutreffen, die Sie möglicherweise haben, aber soweit ich weiß, ist dies im Allgemeinen nicht der Fall.

PS Die gesamte Unterscheidung zwischen geschlossener und nicht geschlossener Form wird bei der Computerarithmetik sehr schwierig: Sie könnten denken, dass in einer kubischen Formel eine geschlossene Form ist, aber was die Computerarithmetik betrifft ist besorgt, das ist nur eine weitere ungefähre rationale Funktion, sie ist vielleicht schneller, aber nicht grundlegend anders als die ungefähre rationale Funktion, die das Ergebnis eines Eigenwertalgorithmus definiert.cos()

Kirill
quelle
Vielen Dank für die tolle Antwort. Das bisschen über das Verbinden von Eigenwerten und Polywurzeln war für mich neu. Ich sehe, dass geschlossene Lösungen im Umgang mit Computerarithmetik nicht unbedingt besser sind. Ich hatte vor, einen quadratischen und kubischen Polywurzellöser zu verwenden , über den Kahan geschrieben hat ( people.eecs.berkeley.edu/~wkahan/Math128/Cubic.pdf ) und den Quartic mithilfe der Descartes-Faktorisierung für meine Lösungen in einen Cubic umzuwandeln. Würden Sie empfehlen, den QR-Algorithmus oder meinen angegebenen Ansatz zu implementieren?
CADJunkie
@CADJunkie Das ist cool, danke, ich wusste nicht, dass Kahan das geschrieben hat, das werde ich später lesen. Es ist schwierig, dies zu empfehlen. Der bessere Weg, diese Fragen zu klären, besteht darin, die Ideen umzusetzen, sie dann zu testen und zu bewerten und diese Benchmarks zu verwenden. Das ist viel definitiver. Die Leistung ist sehr schwer vorherzusagen, bevor Ergebnisse erzielt werden. Aber stellen Sie zumindest sicher, dass Sie mit allen Eigenwertlösern der Standardbibliothek vergleichen.
Kirill
@CADJunkie Basierend auf dem, was Kahan geschrieben hat, könnte der kubische Fall auch besser direkt gemacht werden. Vorausgesetzt, ich denke, was ich geschrieben habe, ist für Quartics und höher in Ordnung.
Kirill
1

Die Verwendung eines QR-Algorithmus ist der bessere Weg. Ich denke, es ist am besten, einen Algorithmus zu verwenden, der für die jeweilige Aufgabe am besten geeignet ist.

Selbst wenn Sie versuchen, die Wurzeln eines Polynoms zu berechnen, ohne sie als Eigenwerte einer Matrix verwenden zu wollen, wird häufig empfohlen, die Begleitmatrix für dieses Polynom zu erstellen und nach den Eigenwerten dieser Matrix zu suchen. (Führen Sie also das Gegenteil von dem aus, was Sie in Betracht ziehen.) Der Prozess ist äußerst robust, aber nicht sehr rechnerisch effizient. Ein Algorithmus, der für die Aufgabe des Findens von Polynomwurzeln spezifisch ist (z. B. Jenkins-Traub, Methode von Laguerre usw.), wäre effizienter. Und selbst wenn Sie eine dieser Methoden verwenden, kann es dennoch Fälle geben, in denen die Bildung der Begleitmatrix und die Berechnung ihrer Eigenwerte immer noch bessere Ergebnisse liefert.

Wie Kirill angedeutet hat, gibt es auch keine Möglichkeit, die Lösungen in geschlossener Form für ein Polynom 3. oder 4. Grades zu nutzen. Ich habe mich vor einigen Jahren damit befasst, bevor ich eine Übersetzung des Jenkins-Traub-Algorithmus geschrieben habe. Für numerische Ergebnisse ist es immer noch am besten, einen Algorithmus von Grund auf als diskreten Löser zu schreiben und die Lösungen in geschlossener Form zu ignorieren.

DavidB2013
quelle