What is a simple way to find the real roots of a (cubic) polynomial?

Question

this seems like an obvious question to me, but I couldn't find it anywhere on SO. I have a cubic polynomial and I need to find the real roots of the function. What is the way to do this?

I found several closed formula formulas for the roots of a cubic function, but they all use either complex numbers or many goniometric functions, and I don’t like them (and also don’t know which one to choose).

I need something simple; faster is better; and I know that I will eventually have to solve higher order polynomials, so having a numerical solver can help. I know that I can use some library to do the hard work for me, but let me say that I want to do this as an exercise.

I am encoded in C, so no import magic_poly_solver , please.

Bonus question: how to find only the roots within a given interval?

Answer 1

For a cubic polynomial, there are closed-form solutions , but they are not particularly well suited for numerical calculus.

I would do the following for the cubic case: any cubic polynomial has at least one real root, you can easily find it using the Newton method. Then you use deflation to get the remaining quadratic polynomial to see my answer there for the correct completion of this last step.

One word of caution: if the discriminant is close to zero, there will be a numerically multiple real root, and the Newton method will fail. Moreover, since the polynomial in the neighborhood of the root is similar to (x - x0) ^ 2, you will lose half of your significant digits (since P (x) will be <epsilon as soon as x - x0 <sqrt (epsilon)). Therefore, you can exclude this and use a closed-form solution in this particular case or solve a derived polynomial.

If you want to find roots in a given interval, check Sturm's theorem .

A more general (complex) algorithm for solving a general polynomial is the Jenkins-Traub algorithm . This is clearly redundant, but works well on cubes. Usually you use a third-party implementation.

Since you are using C, using GSL is definitely the best choice.

Another common method is to search for eigenvalues ​​of the companion matrix using, for example. Balanced QR Decomposition or Reduction to Homeowner Form. This is the approach taken by GSL.

Answer 2

If you do not want to use closed solutions (or expect higher order polynomials), the most obvious method will be to calculate the approximate roots using the Newton Method .

Unfortunately, it is impossible to decide what roots you will get during the iteration, although this depends on the initial value.

Also see here .

Answer 3

See Quark and Dice Solution for D Herbison-Evans Graphics, published in 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