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=−b−sign(b)Δ−−√2a,x2=c/(ax1),Δ=det(b2c2ab)
Δb2≈4ac
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(⋯)
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.
quelle