Lösung der Quartalsgleichung

Gibt es eine offene C-Implementierung für die Lösung von Quartalsgleichungen:

a x ⁴ + b x ³ + c x ² + d x + e = 0

$ax⁴+bx³+cx²+dx+e=0$

Ich denke an eine Implementierung der Ferrari-Lösung. Auf Wikipedia habe ich gelesen, dass die Lösung nur für einige der möglichen Vorzeichenkombinationen der Koeffizienten rechenstabil ist. Aber vielleicht habe ich Glück ... Ich habe eine pragmatische Lösung erhalten, indem ich mithilfe eines Computeralgebrasystems analytisch gelöst und nach C exportiert habe. Wenn es jedoch eine getestete Implementierung gibt, würde ich diese vorziehen. Ich suche eine schnelle Methode und bevorzuge es, keinen allgemeinen Wurzelfinder zu verwenden.

Ich brauche nur echte Lösungen.

polynomials nonlinear-equations roots Highsciguy
quelle

Benötigen Sie alle (echten) Lösungen gleichzeitig? Wie GertVdE weiter unten ausführt, gibt es bei Stabilitätsproblemen mit einer Lösung in geschlossener Form keinen guten Grund, keinen Root-Finding-Algorithmus zu verwenden.

Godric Seer

Ich finde es lustig, dass dies als nichtlineare Algebra markiert wurde, da man einfach die Eigenwerte der Begleitmatrix berechnen könnte, die bereits in Hessenberg-Form vorliegt und das Anwenden von QR-Sweeps ziemlich einfach wäre.

Victor Liu

Schauen Sie sich die in ACM TOMS (Algorithmus 954) veröffentlichten kubischen / quartischen Löser an . Code, der es in dieses Journal schafft, ist normalerweise von sehr hoher Qualität. Das Papier selbst befindet sich hinter einer Paywall, aber der Code kann über diesen Link heruntergeladen werden .

GoHokies

... (später bearbeiten) wird der ACM - Code in Fortran geschrieben 90 , aber mein erster Eindruck ist , dass man könnte es aus C ohne Putting in viel Mühe nennen.

GoHokies

@GoHokies Ich denke, Sie sollten Ihren Kommentar in eine Antwort umwandeln, da ich denke, dass dies eine gute Antwort auf diese Frage ist. Zumal das verlinkte Papier es schafft, die üblichen numerischen Instabilitäten zu vermeiden, und das ist absolut keine triviale Sache.

Kirill

Antworten:

Ich würde dringend davon abraten, geschlossene Lösungen zu verwenden, da diese numerisch sehr instabil sind. Sie müssen bei der Bewertung und Reihenfolge Ihrer Bewertungen der Diskriminante und anderer Parameter äußerst vorsichtig sein.

Das klassische Beispiel ist das für die quadratische Gleichung . Wenn Sie die Wurzeln als geraten Sie in Schwierigkeiten mit Polynomen, bei denen seitdem eine Stornierung in der Zähler. Sie müssen . $ax^2+bx+c=0$

x_{1, 2} = \frac{- b \pm \sqrt{b^{2} - 4 a c}}{2 a}

$x_{1,2} = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$

b ≫ 4 a c

$b\gg 4ac$

x_{1} = \frac{- (b + s i g n (b) \sqrt{b^{2} - 4 a c})}{2 a}; x_{2} = \frac{c}{a} \frac{1}{x_{1}}

$x_1 = \frac{-(b+sign(b)\sqrt{b^2-4ac})}{2a}; x_2 = \frac{c}{a}\frac{1}{x_1}$

Higham verwendet in seinem Meisterwerk "Genauigkeit und Stabilität numerischer Algorithmen" (2. Auflage, SIAM) eine direkte Suchmethode, um Koeffizienten eines kubischen Polynoms zu finden, für die die klassische analytische kubische Lösung sehr ungenaue Ergebnisse liefert. Das Beispiel, das er gibt, ist . Für dieses Polynom sind die Wurzeln gut getrennt und daher ist das Problem nicht schlecht konditioniert. Wenn er jedoch die Wurzeln unter Verwendung des analytischen Ansatzes berechnet und das Polynom in diesen Wurzeln bewertet, erhält er einen Rest von unter Verwendung einer stabilen Standardmethode (der Begleitmatrixmethode). ist der Rest in der Reihenfolge $[a,b,c] = [1.732, 1, 1.2704]$ $\mathcal{O}(10^{-2})$ $\mathcal{O}(10^{-15})$ . Er schlägt eine geringfügige Änderung des Algorithmus vor, aber selbst dann kann er eine Reihe von Koeffizienten finden, die zu Resten von was definitiv nicht gut ist. Siehe S. 480-481 des oben genannten Buches. $\mathcal{O}(10^{-11})$

In Ihrem Fall würde ich die Methode von Bairstow anwenden . Es verwendet eine iterative Kombination aus Newton-Iteration für quadratische Formen (und dann werden die Wurzeln des Quadrats gelöst) und Deflation. Es ist einfach zu implementieren und es gibt sogar einige Implementierungen im Web.

GertVdE
quelle

Könnten Sie bitte erklären, was Sie mit "Ich würde dringend davon abraten, geschlossene Lösungen zu verwenden, da diese numerisch sehr instabil sind". Gilt dies nur für Polynome 4. Grades oder ist dies eine allgemeine Regel?

NoChance

@EmmadKareem Ich habe meine Antwort oben aktualisiert.

GertVdE

Siehe diese:

Lösen Quartics und Cubics für Grafiken , die ursprünglich in der veröffentlichten Graphics Gems V . Der Originalcode ist hier . Siehe auch dies und das .
Eine universelle Methode zum Lösen von Quarzgleichungen .

lhf
quelle

Wenn ich diesen Code für das Polynom mit den in meiner Antwort angegebenen Koeffizienten verwende, finde ich Folgendes: , das einen relativen Fehler von Vergleich zur realen Wurzel aufweist (berechnet mit dem Root-Befehl von Octave, der die Companion-Matrix-Methode verwendet). Es hat einen Rest von während die Wurzel der Companion-Matrix-Methode einen Rest von . Es liegt an Ihnen, ob dies gut genug ist (für Computergrafiken könnte es sein, für einige andere Anwendungen wird es nicht sein)

x_{1} = - 1.602644912244132 e + 00

$x_1 = -1.602644912244132e+00$

O (10^{- 8})

$\mathcal{O}(10^{-8})$

O (10^{- 7})

$\mathcal{O}(10^{-7})$

O (10^{- 15})

$\mathcal{O}(10^{-15})$

GertVdE

Numerische Rezepte in c liefern einen Ausdruck in geschlossener Form für echte quadratische und kubische Wurzeln, die vermutlich eine anständige Präzision aufweisen. Da die algebraische Lösung des Quarzes das Lösen einer Kubik und dann das Lösen von zwei Quadraten beinhaltet, kommt eine geschlossene Quarz mit guter Präzision möglicherweise nicht in Frage.

Nemocopperfield
quelle

Ich habe gerade die Wurzel des kubischen Beispiels innerhalb von 2e-16 (ein bisschen über der Präzision meiner Floats) unter Verwendung der numerischen Rezepte in c (press et al) kubischen Formeln erhalten. Es gibt also Grund zur Hoffnung.

Nemocopperfield