The most efficient way to solve the real roots of polynomials

Question

I tried to implement a method that can solve the quartic polynomial given by a, b, c, d, e using this method: https://math.stackexchange.com/a/786/127747

It works for some solutions if there are 1 or 2 real roots, but the problem is that sometimes involved square or cubic roots can cause NaN values ​​to appear in intermediate variables if they take negative values ​​as input, for example Math.sqrt(-9) , which is then mixed with the final answer, making all the NaN roots at the end of the method.

Is there any quick analytical way to get only all the real roots of the apartment polynomial in Java, given variables / coefficients a, b, c, d and e that are not related to some complex library, etc.

Edit: (Any understandable language works, but preferably Java, and if it is not, I will still make a port and edit the answer to add it)

Edit 2: Here is my current code, where s is p from the equation, and q are just variables in order to optimize it a bit, so the same calculations are not performed twice:

 public static double[] solveRealQuarticRoots(double a, double b, double c, double d, double e) { double s1 = 2 * c * c * c - 9 * b * c * d + 27 * (a * d * d + b * b * e) - 72 * a * c * e, q1 = c * c - 3 * b * d + 12 * a * e; s2 = s1 + Math.sqrt(-4 * q1 * q1 * q1 + s1 * s1), q2 = Math.cbrt(s2 / 2), s3 = q1 / (3 * a * q2) + q2 / (3 * a), s4 = Math.sqrt((b * b) / (4 * a * a) - (2 * c) / (3 * a) + s3), s5 = (b * b) / (2 * a * a) - (4 * c) / (3 * a) - s3, s6 = (-(b * b * b) / (a * a * a) + (4 * b * c) / (a * a) - (8 * d) / a) / (4 * s4); double[] roots = new double[4]; for (int i = 0; i < 3; i++) roots[i] = -b / (4 * a) + (i > 1 ? -1 : 1) * (s4 / 2) - (i % 2 == 0 ? -1 : 1) * (Math.sqrt(s5 + (i > 1 ? -1 : 1) * s6) / 2); return roots; } 

Answer 1

You can use the Descartes rule of signs and Sturm's theorem to give upper bounds on the number of roots. Perhaps this can tell you how many roots to expect. Descartes’s rule is fast because it involves only comparing sign changes.

However, you can add branching to your current code to avoid branches where you get complex results.

 public static double[] solveRealQuarticRoots(double a, double b, double c, double d, double e) { double s1 = 2 * c * c * c - 9 * b * c * d + 27 * (a * d * d + b * b * e) - 72 * a * c * e, q1 = c * c - 3 * b * d + 12 * a * e; double discrim1 = -4 * q1 * q1 * q1 + s1 * s1; if(discrim1 >0) { double s2 = s1 + Math.sqrt(discrim1); q2 = Math.cbrt(s2 / 2), s3 = q1 / (3 * a * q2) + q2 / (3 * a), discrim2 = (b * b) / (4 * a * a) - (2 * c) / (3 * a) + s3; if(discrim2>0) { double s4 = Math.sqrt(discrim2); double s5 = (b * b) / (2 * a * a) - (4 * c) / (3 * a) - s3; double s6 = (-(b * b * b) / (a * a * a) + (4 * b * c) / (a * a) - (8 * d) / a) / (4 * s4); double discrim3 = (s5 - s6), discrim4 = (s5 + s6); // actual root values, may not be set double r1, r2, r3, r4; if(discrim3 > 0) { double sqrt1 = Math.sqrt(s5-s6); r1 = -b / (4 * a) - s4/2 + sqrt1 / 2; r2 = -b / (4 * a) - s4/2 - sqrt1 / 2; } else if(discrib3 == 0) { // repeated root case r1 = -b / (4 * a) - s4/2; } if(discrim4 > 0) { double sqrt2 = Math.sqrt(s5+s6); r3 = -b / (4 * a) + s4/2 + sqrt2 / 2; r4 = -b / (4 * a) + s4/2 - sqrt2 / 2; } else if(discrim4 ==0) { r3 = -b / (4 * a) + s4/2; } if(discrim3 > 0 && discrim4 > 0) return {r1,r2,r3,r4}; else if( discrim3 > 0 && discrim4 == 0 ) return {r1,r2,r3}; else if( discrim3 > 0 && discrim4 < 0 ) return {r1,r2}; else if( discrim3 == 0 && discrim4 > 0 ) return {r1,r3,r4}; else if( discrim3 == 0 && discrim4 == 0 ) return {r1,r3}; else if( discrim3 == 0 && discrim4 < 0 ) return {r1}; else if( discrim3 < 0 && discrim4 > 0 ) return {r3,r4}; else if( discrim3 < 0 && discrim4 == 0 ) return {r3}; else if( discrim3 < 0 && discrim4 < 0 ) return new double[0]; } } return new double[0]; 

}

Further answers to the mathematics exchange office include a link to Don Herbison-Evans, Michel Daoud Yakub and Gustavo Faidenenreich's “Search for the Real Quartic Roots”. Here you can find here . In this article, he takes into account numerical problems.

Do not reduce numerical methods. Newton is pretty fast and can quickly converge.

Answer 2

I don’t know how to calculate only the real roots of a polynomial, but you can give the Apache Commons Math library a try, LaguerreSolver can calculate all the complex roots for a given polynomial.