Schnellste numerische Lösung eines realen kubischen Polynom?

Question

R Frage: für die schnellste Art und Weise der Suche nach NUMERISCH eine Reihe von willkürlich cubics zu lösen bekannt echte coeffs haben und drei reelle Wurzeln. Die POLYROOT Funktion in R wird berichtet Jenkins-Traub-Algorithmus 419 für komplexe Polynome zu verwenden, aber für echte Polynome die Autoren beziehen sich auf ihre frühere Arbeit. Was sind die Optionen schneller für eine echte kubische oder allgemeiner für ein reelles Polynom?

Answer 1

Konkretisierung Arietta Antwort oben:

> a <- c(1,3,-4)
> m <- matrix(c(0,0,-a[1],1,0,-a[2],0,1,-a[3]), byrow=T, nrow=3)
> roots <- eigen(m, symm=F, only.values=T)$values

Ob dies schneller oder langsamer als die kubische Solver in der GSL-Paket mit (wie durch knguyen oben vorgeschlagen) ist eine Frage der es auf Ihrem System Benchmarking.

Answer 2

Die numerische Lösung dieses viele Male in einem zuverlässigen, stabilen Art und Weise zu tun, beinhalten: (1) die Begleiter Matrix bilden, (2) die Eigenwerte der Begleitmatrix finden

.

Sie mögen denken, dies ein größeres Problem ist als das Original zu lösen, aber das ist, wie die Lösung in den meisten Produktionscode implementiert ist (sagen wir, Matlab).

Für das Polynom:

p(t) = c0 + c1 * t + c2 * t^2 + t^3

die Begleitmatrix ist:

[[0 0 -c0],[1 0 -c1],[0 1 -c2]]

Die Eigenwerte dieser Matrix; sie entsprechen den Wurzeln des ursprünglichen Polynom.

Für diesen sehr schnell tun, laden Sie den Einzelwert Subroutinen von LAPACK, kompilieren sie, und verknüpfen sie mit Ihrem Code. Tun Sie dies parallel, wenn Sie zu viele haben (sagen wir etwa eine Million) Sätze von Koeffizienten.

Hinweis

, dass der Koeffizient von t^3 eins ist, wenn diese in Ihrer Polynome nicht der Fall ist, müssen Sie das Ganze mit dem Koeffizienten teilen und dann fortzufahren.

Viel Glück.

Edit: Numpy und Oktave hängen auch von dieser Methode, die Wurzeln der Polynome zur Berechnung. Siehe zum Beispiel diesen Link .

Answer 3

Der schnellste bekannte Art und Weise (das ich kenne) die richtigen Lösungen ein System beliebiger Polynome in finden n Variablen ist polyedrische homotopy. Eine detaillierte Erläuterung ist wahrscheinlich über eine Stackoverflow Antwort, aber es ist im Wesentlichen ein Pfad-Algorithmus, der die Struktur jeder Gleichung torischen Geometrien ausnutzt. Google wird Ihnen eine Reihe von Papieren .

Vielleicht ist diese Frage ist besser geeignet für mathoverflow ?

Answer 4

Sie benötigen alle drei Wurzeln oder eine gerade? Wenn nur ein, würde ich denken, Newton-Verfahren wäre ok arbeiten. Wenn alle drei dann könnte es unter Umständen problematisch sein, wo zwei nahe beieinander liegen.

Answer 5

1) Lösen Sie für die Ableitung Polynom P‘Ihre drei Wurzeln zu suchen. Siehe es wissen, wie es richtig zu machen. Rufen Sie jene Wurzeln a und b (mit a

2) Für die mittlere Wurzel, ein paar Schritte von bisection zwischen a und b verwenden, und wenn Sie in der Nähe sind genug, Finish mit dem Newton-Verfahren.

3) Für die MIN- und MAX-Wurzel, „Jagd“ die Lösung. Für den max root:

• Starten Sie mit x0 = b, x1 = b + (b - a) * Lambda, wobei Lambda ist eine moderate Zahl (etwa 1,6)
• do x_n = b + (x_ {n - 1} - a) * Lambda bis P (x_n) und P (b) unterschiedliche Vorzeichen
• Führen bisection + newton zwischen x_ {n - 1} und x_n

Answer 6

Die gängigen Methoden zur Verfügung:. Newton-Verfahren, Bisektionsmethode, Schnittene, Fixpunktiteration usw. Google eine von ihnen

Wenn Sie eine nicht-lineare System auf der anderen Seite (zB ein System auf N Polynom Gleichung ist in N Unbekannten), ein Verfahren, wie hohe Ordnung Newton verwendet werden kann.

Answer 7

Haben Sie versucht, Blick in das Paket http: // cran .r-project.org / web / packages / GSL / index.html ?