¿Cuál es una manera simple de encontrar raíces reales de un polinomio (cúbico)?

Question

esto me parece una pregunta obvia, pero no pude encontrarla en ningún lado en SO. Tengo un polinomio cúbico y necesito encontrar raíces reales de la función. ¿Cuál es LA forma de hacer esto?

He encontrado varias fórmulas cerradas para las raíces de una función cúbica, pero todas usan números complejos o muchas funciones goniométricas y no me gustan (y tampoco sé cuál elegir) .

Necesito algo simple; más rápido es mejor; y sé que finalmente necesitaré resolver polinomios de orden superior, por lo que tener un solucionador numérico también podría ayudar. Sé que podría usar alguna biblioteca para hacer el trabajo duro por mí, pero digamos que quiero hacer esto como ejercicio.

Estoy codificando en C, por lo que no import magic_poly_solver, por favor.

Pregunta adicional: ¿Cómo encuentro solo las raíces dentro de un intervalo determinado?

Answer 1

Para un polinomio cúbico hay closed form solutions, pero no son especialmente adecuados para el cálculo numérico.

Haría lo siguiente para la caja cúbica: cualquier polinomio cúbico tiene al menos una raíz real, puede encontrarlo fácilmente con el método de Newton. Luego, usa deflation para resolver el polinomio cuadrático restante, consulte mi respuesta there para saber cómo hacer este último paso correctamente.

Una palabra de advertencia: si el discriminante está cerca de cero, habrá una raíz real numéricamente múltiple, y el método de Newton fallará miserablemente. Además, dado que cerca de la raíz, el polinomio es como (x - x0)^2, perderá la mitad de sus dígitos significativos (ya que P (x) será < épsilon tan pronto como x - x0 < sqrt (épsilon))). Así que es posible que desee descartar esto y usar la solución de forma cerrada en este caso particular, o resolver el polinomio derivado.

Si desea encontrar raíces en un intervalo determinado, marque Sturm's theorem.

Un algoritmo más general (complejo) para resolver polinomios genéricos es Jenkins-Traub algorithm. Esto es claramente exagerado aquí, pero funciona bien en cúbicos. Por lo general, utiliza una implementación de terceros.

Dado que usted hace C, usar el GSL es seguramente su mejor opción.

Otro método genérico es encontrar los valores propios de companion matrix con, por ejemplo. descomposición equilibrada de QR, o reducción a la forma del dueño de casa. Este es el enfoque adoptado por GSL.

Answer 2

Si no desea utilizar las soluciones cerradas (o esperar polinomios de orden mayor), el método más obvio sería calcular las raíces aproximadas usando Newton's method.

Desafortunadamente no es posible decidir qué raíces obtendrá al iterar, aunque depende del valor inicial.

Ver también here.

Answer 3

Ver Solving quartics and cubics for graphics por D Herbison-Evans, publicado en Graphics Gems V.

Answer 4

/******************************************************************************* 
* FindCubicRoots solves: 
*  coeff[3] * x^3 + coeff[2] * x^2 + coeff[1] * x + coeff[0] = 0 
* returns: 
*  3 - 3 real roots 
*  1 - 1 real root (2 complex conjugate) 
*******************************************************************************/ 

int FindCubicRoots(const FLOAT coeff[4], FLOAT x[3]); 

http://www.realitypixels.com/turk/opensource/index.html#CubicRoots