Finding the real roots of a polynomial

Question

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.

Answer 1

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.

Answer 2

I actually had to do this for school about a month ago, and the method I came up with was as follows:

1. 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.
2. 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).
3. Finding the mins and maxes is accomplished by taking the derivative and finding its zeros.
4. Considering that this is a procedure for finding zeros, step 3 can be done recursively.
5. 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