# Polynomial root finding

I have an univariate polynomial of some degree - how do I numerically find all of its real roots?

I never thought I would ask this question - everyone knows how to find polynomial roots, right..? Please, can someone explain to me how this works? This is what I think I understand so far:

Newton method - it can find only one root at a time (if it converges) so in order to list all the roots I need to somehow guess where to start from. How to guess?

Bisection - also finds only one root and it needs two endpoints with opposite signs. How to guess those endpoints? What if the function simply does not have opposite signs, for example $f(x) = x*x$?

Do I need to know at least the interval I want to search in? Say, that I'm only interested in roots from -1000 to 1000? Or is it possible to list all the roots without any initial guesses?

Then I found about http://en.wikipedia.org/wiki/Sturm%27s_theorem but I don't really understand it yet - is it somehow helpful in this context?

Is the approach basically combination of the above? Count the signs with Descartes (what for?), find the intervals with Sturm, check if there are opposite signs, if no - find the extreme, if yes - bisect?

And I also read somewhere that it is possible to covert the polynomial into a system of linear equations (matrix?) and solve that? Is this possible?

(Note: I search this forum and found this but I don't really understand any of it - "Homotopy Continuation"?)

-
I'm not an expert in numerical mathematics, but here's an outline of a possible procedure: First, calculate the square-free part of a polynomial $p$ via $\operatorname{gcd}(p,p')$. Then, use Descartes' Rule and Sturm's Theorem to find small-enough intervals for each zero of the polynomial (since it's square-free, the intervals can be made small enough to contain a single zero each); this can be done by bisection. Also, make the intervals so small that any point inside them gives quadratic convergence for Newton iteration, and do Newton iteration from the center point. –  Johannes Kloos Feb 20 '13 at 15:45
@JohannesKloos: why to calculate square-free part? To eliminate multiple roots? And why to use Descartes' Rule - it only gives the number of sign changes, no? "the intervals can be made small enough" - how? by Sturm's Theorem? –  Ecir Hana Feb 20 '13 at 17:33
The square-free part eliminates multiple roots, as you said. This is advantageous for two reasons: a. It allows you to get intervals containing a single zero using Sturm's Theorem. b. I read somewhere that some numerical methods have problems with multiple roots. –  Johannes Kloos Feb 20 '13 at 19:20
The "small enough" thing you can do as follows: As soon as you have seperated the zeroes into intervals (use Sturm's Theorem), it is guaranteed that there is a sign change inside every interval (because there are no repeated zeroes). You can then use, e.g., bisection to find a sub-interval in which Newton's method converges quadratically. –  Johannes Kloos Feb 20 '13 at 19:23