Solução da equação quártica

Existe uma implementação C aberta para a solução de equações quárticas:

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

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

Estou pensando em uma implementação da solução da Ferrari. Na Wikipedia, li que a solução é estável em termos computacionais apenas para algumas das combinações possíveis de sinais dos coeficientes. Mas talvez eu tenha sorte ... Consegui uma solução pragmática resolvendo analiticamente usando um sistema de álgebra computacional e exportando para C. Mas se houver uma implementação testada, prefiro usá-la. Eu procuro um método rápido e prefiro não usar um localizador de raiz geral.

Eu preciso apenas de soluções reais.

polynomials nonlinear-equations roots highsciguy
fonte

Você precisa de todas as soluções (reais) simultaneamente? Como o GertVdE diz abaixo, se você tiver problemas de estabilidade com uma solução de formulário fechado, não há realmente um bom motivo para não usar algum algoritmo de busca de raiz.

Godric Seer

Acho engraçado que isso tenha sido marcado com álgebra não-linear, pois você pode simplesmente calcular os autovalores da matriz complementar, que já está no formato de Hessenberg, e aplicar varreduras QR seria bem simples.

Victor Liu

Veja os solucionadores cúbicos / quárticos publicados no ACM TOMS (Algorithm 954) . O código que entra nesse diário geralmente é de qualidade muito alta. O documento em si está protegido por uma parede de pagamento, mas o código pode ser baixado nesse link .

GoHokies 28/01

... (editar mais tarde) o código ACM está escrito em FORTRAN 90, mas minha primeira impressão é que alguém poderia chamá-lo de C sem fazer muito esforço.

GoHokies

@GoHokies Acho que você deve converter seu comentário em resposta, porque acho que é uma boa resposta para essa pergunta. Especialmente porque o artigo vinculado consegue evitar as instabilidades numéricas usuais, e isso não é absolutamente uma coisa trivial a se fazer.

Kirill

Respostas:

Eu desaconselho fortemente o uso de soluções de formulário fechado, pois elas tendem a ser numericamente muito instáveis. Você precisa tomar muito cuidado na maneira e na ordem de suas avaliações dos parâmetros discriminantes e outros.

O exemplo clássico é o da equação quadrática . Calcular as raízes como causará problemas para os polinômios em que desde então você recebe o cancelamento no numerador. Você precisa calcular . $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, em sua obra-prima "Precisão e estabilidade de algoritmos numéricos" (2ª ed., SIAM), usa um método de pesquisa direta para encontrar coeficientes de um polinômio cúbico para o qual a solução cúbica analítica clássica fornece resultados muito imprecisos. O exemplo que ele fornece é . Para este polinômio, as raízes estão bem separadas e, portanto, o problema não está mal condicionado. Entretanto, se ele calcula as raízes usando a abordagem analítica e avalia o polinômio nessas raízes, ele obtém um resíduo de enquanto usa um método padrão estável (o método da matriz companheira) , o resíduo é da ordem $[a,b,c] = [1.732, 1, 1.2704]$ $\mathcal{O}(10^{-2})$ $\mathcal{O}(10^{-15})$ . Ele propõe uma ligeira modificação no algoritmo, mas, mesmo assim, ele pode encontrar um conjunto de coeficientes que levam a resíduos de que definitivamente não é bom. Veja p480-481 do livro mencionado acima. $\mathcal{O}(10^{-11})$

No seu caso, eu aplicaria o método de Bairstow . Ele usa uma combinação iterativa de iteração de Newton em formas quadráticas (e as raízes do quadrático são resolvidas) e deflação. É facilmente implementável e existem até algumas implementações disponíveis na web.

GertVdE
fonte

Você poderia, por favor, explicar o que você quer dizer com "Eu desaconselharia fortemente o uso de soluções de formulário fechado, pois elas tendem a ser numericamente muito instáveis". Isso se aplica apenas aos polinômios de 4º grau ou é uma regra geral?

NoChance

@EmmadKareem Atualizei minha resposta acima.

GertVdE 5/09/12

Veja estes:

Resolver quárticas e Cubics para gráficos , publicado originalmente em Gráficos Gems V . O código original está aqui . Veja também isto e isto .
Um método universal de resolução de equações quárticas .

lhf
fonte

Usando esse código no polinômio com coeficientes dados na minha resposta, encontro o seguinte: , que possui um erro relativo de comparado à raiz real (calculado usando o comando de raízes do Octave, que usa o método da matriz complementar). Ele possui um resíduo de enquanto a raiz do método da matriz complementar possui um resíduo de . Até você se isso é bom o suficiente (para gráficos de computador que poderia ser, para algumas outras aplicações, não vai ser)

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

As receitas numéricas em c fornecem expressão de forma fechada para raízes reais de quadrática e cúbica que, presumivelmente, possuem precisão decente. Como a solução algébrica do quártico envolve a solução de um cubico e, em seguida, a solução de dois quadráticos, talvez um quártico de forma fechada com boa precisão não esteja fora de questão.

Nemocopperfield
fonte

Acabei de obter a raiz do exemplo cúbico citado em 2e-16 (um pouco acima da precisão dos meus carros alegóricos) usando as receitas numéricas nas fórmulas cúbicas c (press et al). Portanto, há razões para ter esperança.

Nemocopperfield 28/01