Interval Arithemetic

Course Notes for CptS 330 Numerical Computing

1. Interval Numbers

The notation [a,b] denotes all real numbers between a and b, including a and b. The interval can be represted by the computer by the ordered pair [a,b]. By convention a <= b.

2. Arithmetic on Intervals

Arithmetic operations may be defined on intervals. The operations are expected to return an interval that contains the image of the input intervals under the operation, but the resulting interval need not be the smallest interval that contains the results of the operations.

[a,b] + [c,d] = [a+c,b+d],

[a,b] - [c,d] = [a-d,b-c],

[a,b] * [c,d] = [min(ac,ad,bc,bd),max(ac,ad,bc,bd)],

1/[a,b] = [1/b,1/a] only if 0 not in [a,b].

Using the above rules, interval versions of polynomials and rational functions (quotients of polynomials) can be evaluated. Under these rules, we are only guaranteed that

r(X) contain {r(x) | x in X}

for an interval rational function r and a given interval X. We are however able to also guarantee that if X is a subset of X', then r(X) is a subset of r(X').

3. The Natural Interval Extension

Using the above rules, interval versions of polynomials and rational functions (quotients of polynomials) can be evaluated.

The natural interval extension of any function that is monotonic (always increasing or decreasing) returns the interval whose endpoints are the function applied to the input enpoints. For example

[a,b]^3 = [a^3,b^3],

exp([a,b]) = [exp(a),exp(b)].

The natural interval extension of any differentiable function is found by the extrema of the functions results. These extrema occur at the images of the interval's endpoints and at the critical values of the function. The point x is a critical point of f if f'(x) = 0, and the critical value is the result of f(x). Hence, for a function f with critical points a < x1,x2,... < b the natural interval extension returns

f([a,b]) = [min(f(a),f(x1),f(x2),...,f(b)),max(f(a),f(x1),f(x2),...,f(b))].

4. Finding All Zeroes of a Function

The zeroes of a function are the points x such that f(x) = 0. Assuming one has an interval implementation of a function f and its derivative f', the following procedure will isolate the zeroes of the function.

Given an interval [a,b]

  1. If f([a,b]) does not contain zero, then there are no zeroes between a and b.
  2. Otherwise, if f'([a,b]) does not contain zero, then the function is monotonic over [a,b] and there is a single zero between a and b. Use a root refinement method, such as Newton's method, midpoint subdivision or regula falsi to find the root.
  3. Otherwise if b - a > e (where e is some machine-precision epsilon), then recursively call this routine on the intervals [a.(a+b)/2] and [(a+b)/2,b].
  4. Otherwise return a (multiple) zero at (a+b)/2.

5. Interval Newton's Method

Once a zero is isolated (such as from the above method) it can be refined using the following method. Given a function f, let F be its interval version, and F' the interval version of its derivative. Then the interval Newton iteration step is produced by the function

N(X) = m(X) - f(m(X))/F'(X)

where m([a,b]) returns (a+b)/2.

References

  1. Don P. Mitchell. Robust ray intersection with interval arithmetic. Proc. of Graphics Interface '90. Morgan Kauffman, 1990, 68-74.
  2. Ramon E. Moore. Interval Analysis. Prentice Hall, Englewood Cliffs, NJ, 1966.

John C. Hart
School of EECS
Washington State University
1 December, 1996