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?

Noe Cowan

Noe Cowan

Answered question

2022-11-16

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 & Explanation

boursecasa2je

boursecasa2je

Beginner2022-11-17Added 15 answers

Step 1
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.
Step 2
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 [ 1 , 1 ].
I think you can take it from there with the case of zero values at the end points.
Barrett Osborn

Barrett Osborn

Beginner2022-11-18Added 3 answers

MathJax(?): Can't find handler for document MathJax(?): Can't find handler for document Step 1
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 [ a , a ]. Then we evaluate
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 ]
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.
Step 2
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
math xmlns="http://www.w3.org/1998/Math/MathML"> 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?