Next: 3.4.3 Optimality Up: 3.4 Polynomial Interval Arithmetic Previous: 3.4.1 Interpolating Polynomials

## 3.4.2 Charts

We now prove that the rules given in section , for constructing a chart, are correct.

The forbidden region is clearly correct since is a function; we simply decree that as our use of the chart does not depend on how such points are treated. For (x,y) in the zero region, and ; so for any point in the zero region , which implies .

For the remaining regions, consider the polynomial

From the construction of p(x) it is clear that

for any . Consider the polynomial

which interpolates for any value of m. The k roots of the k degree polynomial p are . The polynomial p has no other roots since it is not identically zero. For large x, p(x) is positive:

Imagine p(x) as x decreases; the sign of p(x) will reverse each time x crosses a root of p(x). This sign changing corresponds with the checkboard labelling of .

Consider the point (x,y) which is away from :

If

then

Earlier we proved q(x) interpolated for any m. We have now shown q(x) interpolates . The leading coefficient of q(x) is m. The sign of m relates to : the sign of m is positive if the region (x,y) resides in is labelled with ; the sign of m is negative if the region (x,y) resides in is labelled with .

Next: 3.4.3 Optimality Up: 3.4 Polynomial Interval Arithmetic Previous: 3.4.1 Interpolating Polynomials
 Jeff Tupper March 1996