Finding the real roots of a polynomial Recent posts on polynomials have got me thinking.
I want to find the real roots of a polynomial with real coefficients in one real variable $x$. I know I can use a Sturm Sequence to find the number of roots between two chosen limits $a < x < b$.
Given that $p(x) = \sum_{r=0}^n a_rx^r$ with $a_n = 1$ what are the tightest values for $a$  and $b$ which are simply expressed in terms of the coefficients $a_r$ and which make sure I capture all the real roots?
I can quite easily get some loose bounds and crank up the computer to do the rest, and if I approximate solutions by some algorithm I can get tighter. But I want to be greedy and get max value for min work.
 A: What counts as "simply expressed"? The Fujiwara bound on the magnitude of all the roots (complex ones included) is certainly a very good starting point. I used it for a solution to a codegolf.SE problem involving complex roots and found it perfectly good enough for that context.
A: I actually had to do this for school about a month ago, and the method I came up with was as follows:


*

*Note that all zeros of a polynomial are between a local minimum and a local maximum (including the limits at infinity). However, not all adjacent pairs of a min and a max have a zero in between, but that is irrelevant.

*Therefore, one can find the mins and maxes and converge on the root in between by using the bisection method (if they're on opposite sides of the x-axis).

*Finding the mins and maxes is accomplished by taking the derivative and finding its zeros.

*Considering that this is a procedure for finding zeros, step 3 can be done recursively.

*The base case for recursion is a line. Here, $y=ax+b$ and the zero is $-\frac{b}{a}$.


This is a very easy and quick way to find all real zeros (to theoretically arbitrary precision). :D
