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
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
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. with . I think you can take it from there with the case of zero values at the end points.
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 . In Horner form this is . Take the range . Then we evaluate
Whatever the value of c, clearly there are values of a for which 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 as rather than . A more intelligent application of interval arithmetic would give math xmlns="http://www.w3.org/1998/Math/MathML"> f([−a,a])=[c,c+a2] 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.