Intervals and polynomials

Question

If a polynomial is evaluated over an interval (by the use of interval arithmetic and Horner's method), what does the result say about the polynomial's roots?

I mean, if the resulting interval contains zero, does it mean there must be one more more roots inside the original interval? Could it happen that there might be no zero?

If the resulting interval contains no zero (i.e. both of its end-points have the same sign), does it mean there is no polynomial root inside the original interval? What if one of the end-points of the result is zero?

Answer 1

Generally, the interval range enclosure won't be tight. Therefore,

if the resulting interval [enclosure] contains zero [possibly as its endpoint], does it mean there must be one more more roots inside the original interval? Could it happen that there might be no zero?

There could be roots. Or not. It requires further (interval) analysis: monotonicity test using enclosure for the derivative and interval Newton method. But first bisect and calculate enclosures over smaller intervals until you arrive at the following, more favorable, situation:

If the resulting interval [enclosure] contains no zero ..., does it mean there is no polynomial root inside the original interval?

Yes.

Answer 2

A polynomial is a continuous function. Hence by the intermediate value theorem, if its values at the end points of an interval lie on opposite sides of zero, it takes the value zero somewhere in the interval.

On the other hand, if the values at the end points are on the same side of zero, there might still be points in the interval where the value is zero, e.g. $x^2$ with $x\in[-1,1]$.

I think you can take it from there with the case of zero values at the end points.

Answer 3

If the polynomial is just evaluated at the endpoints of the interval and these values have opposite signs (or the value zero), there is at least one root in the interval. If the signs are the same, there is nothing you can say.

If you are able to tightly compute the image of the interval, there are roots iff the image contains zero.

In no case is it possible to determine the exact number of roots.

Answer 4

Using Horner's method naïvely throws away a lot of information about self-correlation. Here's an easy counter-example. Consider the polynomial $f(x) = x^2 + c$. In Horner form this is $f(x) = c + x(0 + x)$. Take the range $x \in [-a, a]$. Then we evaluate $$\begin{eqnarray}f([-a, a]) &=& [c, c] + [-a, a]([0, 0] + [-a, a]) \\ &=& [c, c] + [-a, a][-a, a] \\ &=& [c, c] + [-a^2, a^2] \\ &=& [c -a^2, c + a^2] \\ \end{eqnarray}$$

Whatever the value of $c$, clearly there are values of $a$ for which $a^2 > c$ and so the resulting interval contains $0$. However, there are values of $c$ for which there is no real root.

The problem is that by applying the interval arithmetic rule for multiplication naïvely we have evaluated $x^2$ as $[-a^2, a^2]$ rather than $[0, a^2]$. A more intelligent application of interval arithmetic would give $$f([-a, a]) = [c, c + a^2]$$ and would (in this case) accurately identify whether or not there is a root. However, I don't expect that there is a simple way of fixing Horner's method for arbitrary polynomials.