Mais rápida solução numérica de um polinômio cúbico real?

Question

pergunta R: Procurando a maneira mais rápida de resolver numericamente um monte de cúbicas arbitrárias conhecidos por terem coeffs reais e três raízes reais. A função POLYROOT em R é relatado para usar o algoritmo de Jenkins-Traub 419 para polinômios complexos, mas para polinômios reais os autores referem-se a seus trabalhos anteriores. Quais são as opções mais rápidas para uma verdadeira cúbico, ou mais geralmente para um polinômio real?

Answer 1

consubstanciar a resposta de Arietta acima:

> 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 isto é mais rápido ou mais lento do que usando o solver cúbico no pacote GSL (como sugerido por knguyen acima) é uma questão de avaliação comparativa lo em seu sistema.

Answer 2

A solução numérica para fazer isso muitas vezes de uma forma fiável, estável, envolver:. (1) formar a matriz companheiro, (2) encontrar os valores próprios da matriz de companheiro

Você pode pensar que este é um problema mais difícil de resolver do que o original, mas é assim que a solução é implementada na maior código de produção (por exemplo, Matlab).

Para o polinômio:

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

a matriz companheira é:

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

Encontre os valores próprios de tal matriz; eles correspondem às raízes do polinômio originais.

Para fazer isso muito rápido, baixar os sub-rotinas valor singular de LAPACK, compilá-los, e ligá-los ao seu código. Fazei isto em paralelo, se você tem muitos (por exemplo, cerca de um milhão) conjuntos de coeficientes.

Observe que o coeficiente de t^3 é um, se este não é o caso em seus polinômios, você terá que dividir a coisa toda pelo coeficiente e depois prosseguir.

Boa sorte.

Edit: Numpy e oitava também dependem desta metodologia para calcular as raízes de polinômios. Ver, por exemplo, este link .

Answer 3

A maneira mais rápida conhecida (que eu saiba) para encontrar as soluções reais um sistema de polinômios arbitrárias em n variáveis ??é homotopy poliédrica. Uma explicação detalhada é provavelmente além de uma resposta StackOverflow, mas essencialmente é um algoritmo de caminho que explora a estrutura de cada equação usando geometrias tóricas. Google vai lhe dar uma série de documentos .

Talvez esta pergunta é mais adequado para mathoverflow ?

Answer 4

Do que você precisa todos os 3 raízes ou apenas um? Se apenas um, eu acho que o método de Newton iria funcionar ok. Se tudo 3, então pode ser problemático em circunstâncias em que dois estão juntos.

Answer 5

1) Resolva a derivada polinômio P' para localizar seus três raízes. Consulte há saber como fazê-lo corretamente. Chamar essas raízes a e b (com a

2) Para a raiz média, usar alguns passos de bisection entre um e b, e quando você está perto o suficiente, terminar com o método de Newton.

3) Para o min e raiz max, "caça" a solução. Para a raiz máx:

• Comece com x0 = b, x1 = b + (b - a) * lambda, onde lambda é um número moderado (digamos 1.6)
• fazer x_n = b + (x_ {n - 1} - a) * P lambda até (x_n) e P (b) têm diferentes sinais
• Execute bisection + newton entre x_ {n - 1} e x_n

Answer 6

Os métodos mais comuns estão disponíveis: de Newton Método, Método Bissecção, Secante, ponto de iteração fixa, etc. Google qualquer um deles

.

Se você tem um um método como de alta ordem Newton pode ser utilizado.

Answer 7

Você já tentou olhar para o pacote GSL http: // cran .R-project.org / web / packages / gsl / index.html ?