Solución de ecuación cuártica

¿Existe una implementación C abierta para la solución de ecuaciones cuárticas:

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

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

Estoy pensando en una implementación de la solución de Ferrari. En Wikipedia leí que la solución es computacionalmente estable solo para algunas de las posibles combinaciones de signos de los coeficientes. Pero tal vez tenga suerte ... Obtuve una solución pragmática resolviendo analíticamente usando un sistema de álgebra computacional y exportando a C. Pero si hay una implementación probada, preferiría usar esto. Busco un método rápido y prefiero no usar un buscador de raíz general.

Solo necesito soluciones reales.

polynomials nonlinear-equations roots Highsciguy
fuente

¿Necesita todas las soluciones (reales) simultáneamente? Como dice GertVdE a continuación, si tiene problemas de estabilidad con una solución de formulario cerrado, no hay realmente una buena razón para no usar un algoritmo de búsqueda de raíz.

Godric Seer

Me parece curioso que esto se haya etiquetado como álgebra no lineal, ya que simplemente podría calcular los valores propios de la matriz complementaria, que ya está en forma de Hessenberg, y aplicar barridos QR sería bastante simple.

Victor Liu

Eche un vistazo a los solucionadores cúbicos / cuárticos publicados en ACM TOMS (Algoritmo 954) . El código que se incluye en esa revista suele ser de muy alta calidad. El documento en sí está detrás de un muro de pago, pero el código se puede descargar desde este enlace .

GoHokies

... (edición posterior) el código ACM está escrito en FORTRAN 90, pero mi primera impresión es que uno podría llamarlo desde C sin hacer un gran esfuerzo.

GoHokies

@GoHokies Creo que debería convertir su comentario en una respuesta porque creo que es una buena respuesta a esta pregunta. Sobre todo porque el documento vinculado logra evitar las inestabilidades numéricas habituales, y eso no es absolutamente algo trivial.

Kirill

Respuestas:

Recomiendo encarecidamente no utilizar soluciones de forma cerrada, ya que tienden a ser numéricamente muy inestables. Debe tener mucho cuidado en la forma y el orden de sus evaluaciones de los parámetros discriminantes y otros.

El ejemplo clásico es el de la ecuación cuadrática . Calcular las raíces como te meterá en problemas por polinomios donde desde entonces obtienes cancelación en el numerador. 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 en su obra maestra "Precisión y estabilidad de los algoritmos numéricos" (2ª ed., SIAM) utiliza un método de búsqueda directa para encontrar coeficientes de un polinomio cúbico para el que la solución cúbica analítica clásica da resultados muy inexactos. El ejemplo que da es . Para este polinomio, las raíces están bien separadas y, por lo tanto, el problema no está mal condicionado. Sin embargo, si calcula las raíces utilizando el enfoque analítico y evalúa el polinomio en estas raíces, obtiene un residuo de mientras usa un método estándar estable (el método de matriz complementaria) , el residuo es de orden $[a,b,c] = [1.732, 1, 1.2704]$ $\mathcal{O}(10^{-2})$ $\mathcal{O}(10^{-15})$ . Propone una ligera modificación al algoritmo, pero incluso entonces, puede encontrar un conjunto de coeficientes que conducen a residuos de que definitivamente no es bueno. Ver p480-481 del libro mencionado anteriormente. $\mathcal{O}(10^{-11})$

En su caso, aplicaría el método de Bairstow . Utiliza una combinación iterativa de iteración de Newton en formas cuadráticas (y luego se resuelven las raíces de la cuadrática) y la deflación. Se implementa fácilmente e incluso hay algunas implementaciones disponibles en la web.

GertVdE
fuente

¿Podría explicar a qué se refiere con "Recomiendo encarecidamente no utilizar soluciones de forma cerrada, ya que tienden a ser numéricamente muy inestables". ¿Esto se aplica solo a los polinomios de cuarto grado o es una regla general?

NoChance

@EmmadKareem He actualizado mi respuesta anterior.

GertVdE

Ver estos:

Solución de cuárticas y Cubics para los gráficos , publicado originalmente en Gráficos Gems V . El código original está aquí . Ver también esto y esto .
Un método universal para resolver ecuaciones cuárticas .

lhf
fuente

Usando este código en el polinomio con los coeficientes dados en mi respuesta, encuentro lo siguiente: , que tiene un error relativo de comparación con la raíz real (calculado usando el comando de raíces de Octave que usa el método de matriz compañera). Tiene un residuo de mientras que la raíz del método de la matriz compañera tiene un residuo de . Depende de usted si esto es lo suficientemente bueno (para gráficos de computadora puede ser, para algunas otras aplicaciones, no lo 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

Las recetas numéricas en c proporcionan una expresión de forma cerrada para raíces reales de cuadrático y cúbico que presumiblemente tienen una precisión decente. Dado que la solución algebraica del cuarto implica resolver un cubo y luego resolver dos cuadráticos, tal vez un cuarto cerrado con buena precisión no está fuera de discusión.

Nemocopperfield
fuente

Acabo de obtener la raíz del ejemplo cúbico citado dentro de 2e-16 (un poco sobre la precisión de mis flotadores) usando las recetas numéricas en c (press et al) fórmulas cúbicas. Entonces hay razones para esperar.

Nemocopperfield