How to upper-bound the smallest positive root of a polynomial?

Question

Is there any algorithm for (upper-)bounding the smallest positive root of a polynomial of an arbitrary degree if it exists, or detecting that it does not exist otherwise?

Edit: I'm looking for a bound that is smaller than the next largest root.

Answer 1

I figured out a way thanks to the links in the comments above.
One way to bracket the roots is to find a Sturm chain as follows.

Here's an example with Mathematica, assuming f1 is the polynomial. First, find f2:

f1[x] = x^5 - 3 x - 1
f2[x] = D[f1[x], x]

Then repeatedly execute the following and evaluate f1 at a desired point x each time, where x is not a root of the polynomial:

f3[x] = PolynomialRemainder[f1[x], f2[x] , x]
f1[x] = f2[x]
f2[x] = -f3[x]

The number of sign changes in the resulting sequence is the number of roots to the right of x.
I'm not sure if this includes duplicate roots, but it does seem to include complex roots.

(Taking the difference of two of these counts tells us the number of roots in a given interval.)