Tutorial on Interval Computations

History

The main idea of Interval Computations was put forward by R. E. Moore in his PhD Dissertation.

Timeline

Archimedes (ca. 250 B.C.) - Bounding of \phi using polygons inscribed in, and circumscribing a circle
R.C. Young (1931) - Computation on sets
P.S. Dwyer (1951) - Closed Intervals
M. Warmus (1956), T. Sunaga (1958) - Development of interval mathematics
Moore (1959, 1966) - Quantication of errors - "Father" of Interval Analysis

Interval

An interval is a subset S of a totally ordered set T with the property that whenever

x

and

y

are in

S

and

x < z < y

then

z

is in

S

. Intervals are precisely the connected subsets of $\mathbb{R}$

Interval Computations / Interval Arithmetic

Interval Analysis/Interval Computations/Interval Arithmetic is an approach to solve numerical problems by performing computations on sets of reals rather than on floating point approximations to reals.

Interval arithmetic defines a set of operations on intervals:

T·S = {x|there is some y in T, and some z in S, such that x = y·z}.

The basic operations of interval arithmetic are, for two intervals [a,b] and [c,d] that are subsets of the real line (-∞,∞),

[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)]
[a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]

Division by an interval containing zero is not defined under the basic interval arithmetic.

Back to Top

Advantages

There are two principal advantages of Interval Analysis over classical numerical analysis.

The first is that the input errors and the round-off errors are automatically incorporated into the result interval. Thus, interval evaluation can be viewed as automatically performing both a calculation and an error analysis.
The second is that IA allows one to compute provably correct upper and lower bounds on the range of a function over an interval, and this proves useful in the construction of verifiable constraint solvers, which return intervals that are guaranteed to contain all the real solutions.