[RESOLVED] Real roots of a polynomial.

[BlindSniper]

Hi all,
I've recently tried to further my mathematical programming and I'm trying to make a program to find all the Real valued roots of a polynomial. Using Newton's Method I can find one root depending on what my initial guess is, But I need to find all of the roots, and I have no idea how to continue. Any help please ?

[BlindSniper]

I found the solution myself: Just do long division with the root you have and you will get a polynomial who's roots are the remaining roots of the previous polynomial, Use newton's method to find another root and repeat.

[jemidiah]

Now you've gotten me curious--can a real root finding method, polynomial division, and perhaps a few other basic manipulations be combined to get the complex roots of an arbitrary polynomial with real coefficients?


After a few minutes of trying, I haven't found anything of use. My rambling attempts follow. Simply splitting p(x+iy) into real and complex polynomials requires the solution of a system of two two-variable polynomial equations. Considering p(x + r) for real r similarly gives a two-variable polynomial equation. For some r (equal to the real part of a complex root), the resulting polynomial (in x) has two purely imaginary roots, so that p(ix+r) has two real roots--but I don't see how to figure out which r works by computing some real root. Taking the derivative works in the quadratic case, but not in the higher order cases, as far as I can tell. I keep wanting to encode the roots of p(x) in some q(x) so that q(x) has real roots with magnitude given by the roots of p(x). But I don't see how to do that, and one would still need a method to find the phase.

One can compute the minimum value of a polynomial over real inputs using the methods above, at least. If it's odd-order obviously the minimum is -infinity. If it's even-order with a negative leading coefficient, it's again -infinity. If it's even-order with a positive leading coefficient, the minimum necessarily occurs at a local minimum, hence a point where the derivative is 0. Compute the derivative and find the real roots, testing each successively to see where the polynomial is smallest. The same type of reasoning computes maximum values as well. Naively trying to extend this to computing min/max over complex inputs requires (again) the solution of a pair of two-variable polynomials.