Soluzione numerica più veloce di un polinomio cubico reale?

Question

Domanda R:Alla ricerca del modo più veloce per risolvere NUMERICAMENTE un gruppo di cubi arbitrari noti per avere coefficienti reali e tre radici reali.Si dice che la funzione polyroot in R utilizzi l'algoritmo 419 di Jenkins-Traub per i polinomi complessi, ma per i polinomi reali gli autori fanno riferimento al loro lavoro precedente.Quali sono le opzioni più veloci per un cubico reale, o più in generale per un polinomio reale?

Answer 1

Concretizzare la risposta di Arietta sopra:

> 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

Se questo è più veloce o più lento rispetto all'uso del risolutore cubica nel pacchetto GSL (come suggerito da knguyen sopra) è una questione di analisi comparativa sul vostro sistema.

Answer 2

La soluzione numerica per eseguire questa operazione più volte in modo affidabile e stabile implica:(1) Formare la matrice compagna, (2) trovare gli autovalori della matrice compagna.

Potresti pensare che questo sia un problema più difficile da risolvere rispetto a quello originale, ma è così che la soluzione viene implementata nella maggior parte del codice di produzione (ad esempio Matlab).

Per il polinomio:

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

la matrice compagna è:

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

Trovare gli autovalori di tale matrice;corrispondono alle radici del polinomio originale.

Per farlo molto velocemente, scarica le subroutine dei valori singolari da LAPACK, compilale e collegale al tuo codice.Fallo in parallelo se hai troppi set di coefficienti (diciamo, circa un milione).

Si noti che il coefficiente di t^3 è uno, se nei tuoi polinomi non è così, dovrai dividere il tutto per il coefficiente e poi procedere.

Buona fortuna.

Modificare:Anche Numpy e l'ottava dipendono da questa metodologia per calcolare le radici dei polinomi.Vedi, ad esempio, questo link.

Answer 3

Il modo più veloce noto (che io sappia) per trovare le soluzioni reali di un sistema di polinomi arbitrarie in n variabili è omotopia poliedrica. Una descrizione dettagliata è probabilmente oltre una risposta StackOverflow, ma essenzialmente è un algoritmo percorso che sfrutta la struttura di ciascuna equazione utilizzando geometrie toriche. Google vi darà una serie di documenti .

Forse a questa domanda è più adatto per mathoverflow ?

Answer 4

Avete bisogno di tutte e 3 le radici o uno solo? Se solo uno, penserei il metodo di Newton avrebbe funzionato bene. Se tutti e 3 allora potrebbe essere problematico in circostanze in cui due sono vicini tra loro.

Answer 5

1) Risolvere per il derivato polinomio P' per individuare i tre radici. Vedere ci per sapere come farlo correttamente. Chiamare quelle radici A e B (con un

2) Per la radice di mezzo, utilizzare a pochi passi di bisection tra A e B, e quando sei abbastanza vicino, finire con il metodo di Newton.

3) Per il min e max radice, "caccia" la soluzione. Per la radice max:

• Inizia con x0 = b, x1 = b + (b - a) * lambda, dove lambda è un numero moderato (diciamo 1,6)
• fare x_n = b + (x_ {n - 1} - a) * lambda fino a P (x_n) e P (b) avere segni diversi
• Eseguire bisection + newton tra x_ {n - 1} e x_n

Answer 6

I metodi comuni sono disponibili:. Metodo di Newton, metodo di bisezione, secante, iterazione di punto fisso, ecc Google uno di essi

Se si dispone di un non-lineare Sistema d'altra parte (per esempio un sistema N EQN polinomi di n incognite), un metodo come ordine elevato Newton può essere utilizzato.

Answer 7

Hai provato a guardare nel pacchetto http: // cran .R-project.org / web / pacchetti / GSL / index.html ?