Applications of Interval Computations: General
One of the main functions of a computer is crunching numbers, or, to
use a more fancy term, data processing. This data comes either
from measurements, or from expert estimates, or from the results of
the previous processing.
Expert estimates are often very important, but
a computer can easily crunch (and does crunch) thousands and
millions numbers per second. There is not enough experts in the world
to supply that many expert estimates. Therefore, the majority of data
processing algorithms do not use expert estimates at all:
they either directly process the results of the measurements, or
process the results of pre-processing these results. In the second
case, we can consider the entire chain of processors starting from the
sensors and eventually producing the desired result as one huge data
So, in the majority of cases,
data processing processes the results of measurements.
Why Do We Process Data At All?
- First of all, we want to know the world
that we live it. In particular, we want to know the characteristics
of the physical quantities that characterize this world. In a few
cases, we can simply measure them (e.g., body temperature, or weight).
But for more complicated characteristics, like an amount of oil in the
well, or a distance to a star, there is no way to measure them directly.
So, we measure what we can and then, from the results of these
measurements, we try to reconstruct the desired value.
- Second, we want to change this world: we want to
control the objects that already exist, or to change them, or even to
create (synthesize) new objects.
And here comes the problem. Measurements are never absolutely precise. The
result x of measuring a physical quantity x (e.g.,
temperature) may differ from the actual value of that quantity.
E.g., if you have weighed yourself, and the result is 125 pounds,
this does not mean that you weight equals exactly 125. If the scales have
an accuracy +/-2, then the actual weight can be any number from
123(=125-2) to 127=(125+2).
So, the data that we process are not absolutely
precise. This inaccuracy
leads to the inaccuracy in the result of data processing. The
problem is to estimate the resulting inaccuracy.
If we do not know this accuracy, then the result of data processing is
of little practical use: e.g., suppose that we estimated that
a given location contains 100 million
tons of oil, but we do not know the accuracy of this estimate. Then,
if this is 100+/-5, this location is worth developing, but if it is
100+/-100, then we need further analysis to decide what to do.
In Many Cases, We Know Probabilities Of Errors
In many cases, the manufacturer of a measuring instrument provides us
with the probabilities of different values of a measurement error.
For such cases, there exist numerous methods that compute statistical
characteristics of the resulting error.
W. A. Fuller, Measurement error models, J. Wiley
& Sons, New York, 1987.
H. M. Wadsworth, Jr (editor). Handbook of statistical
methods for engineers and scientists, McGraw-Hill Publishing Co.,
In Many Cases, We Do Not Know Probabilities
other cases, however, the values of the probabilities are not known.
Instead, the manufacturer provides us with the guaranteed accuracy
D, i.e., with a guaranteed upper bound
of the error d=x-x
(e.g., ``error cannot exceed 0.1'').
If our measurement results is x, then the
possible values of x=x-d form an
The first person to describe intervals as a result of
measurement was Norbert Wiener: in 1914, he applied intervals
to measuring distances, and in 1921, to measuring time.
Since we are dealing with
intervals, the entire area is called interval computations.
N. Wiener, ``A contribution to the theory of relative position'',
Proc. Cambridge Philos. Soc., 1914, Vol. 17, pp. 441-449.
N. Wiener, ``A new theory of measurement: a study in the logic of
mathematics'', Proceedings of the London Mathematical Society, 1921.
In this case, our problem takes the following form:
Main Problem (In Case We Do Not Know
Suppose that we are interested in the value of a
physical quantity y that is difficult or impossible to measure
directly. To find the value of y, we
measure several other quantities x1,...,xn that
are related to y, and then we reconstruct the value of
y from the results xi of measuring xi.
In other words, we have an algorithm f that takes the values
xi and returns an estimate
(this estimate is called the result of indirect measurement).
In some cases, this algorithm consists of simply applying known
formulas to xi. In other cases, this algorithm implements a
numerical method for solving a system of equations that connect xi
and y. These equations can be algebraic, differential, integral,
etc, and the resulting algorithm can be pretty complicated.
The problem is to estimate the error of the
We are interested in: estimating the interval
y = f(x1,...,xn) of possible values of
y = f(x1,...,xn) when xi is in [xi-Di, xi+Di].
- n intervals xi=[xi-Di,xi+Di] and
- an algorithm f that transforms n real numbers
x1,...,xn into a real number y=f(x1,...,xn).
This is the basic problem of interval computations with
which the entire area started; see, e.g.,
papers on interval computations
R. E. Moore, Automatic error analysis in digital
computation, Lockheed Missiles and Space Co. Technical Report
LMSD-48421, Palo Alto, CA, 1959.
R. E. Moore, C. T. Yang, Interval analysis,
Lockheed Missiles and Space Co. Technical Report
LMSD-285875, Palo Alto, CA, 1959.
R. E. Moore, "The automatic analysis and control of error in
digital computation based on the use of interval numbers", In: L. B.
Rall (ed.), Error in Digital Computation. Proceedings of an
Advanced Seminar Conducted by the Mathematics Research Center, U.S.
Army, at the University of Wisconsin, Madison, October 5-7, 1964,
Vol. 1, John Wiley, N. Y., 1964, pp. 61-130.
R. E. Moore, Interval Analysis, Prentice Hall, Englewood Cliffs,
Where Does This Main Problem Fit In Traditional Mathematics
- For many algorithms f, methods of estimating the
accuracy of the result y have been developed in
numerical mathematics. These methods often produce the exact
- Numerical mathematics does not always give us the solution
to our problem. Error estimation methods of numerical mathematics
are often very complicated, and
require difficult mathematical techniques. Because of that,
algorithms f for which such methods are known form a small subset in
the set of all algorithms that are used for data processing. New data
processing problems appear every day, and new data processing
algorithms are being designed to solve these problems. For a
new data processing algorithm, for a
reasonable period of time, no error estimation method is known.
To handle these algorithms, we need a general tool that would, given
f, xi, and Di, automatically estimate the error
bound for y.
Problems that appear when we do not know the exact distribution,
but we know instead that a distribution belongs to a given class
P of distributions, are called problems of robust
from statistical viewpoint, interval computations is a particular case
of robust statistics, in which P is the class of all
distributions located on a given interval.
P. J. Huber, Robust statistics, Wiley, N.Y., 1981.
- Robust statistics does not always give us the solution
to our problem because robust methods have been developed only for
some functions f.
- The case when instead of a number, we have an interval
(or, more generally, a set) of possible values, has been developed in
mathematics under the name of set-valued analysis
In particular, differential equations with the
uncertain (set-valued) right-hand side (called differential
inclusions) are used, e.g., in control problems.
J.-P. Aubin, A. Cellina, Differential inclusions,
Spinger-Verlag, Grundlehren der math. Wiss., Vol. 264, 1984.
J.-P. Aubin, H. Frankowska, Set-valued analysis, Birkhauser,
Boston, MA, 1990.
- Set-valued analysis does not always give us the solution
to our problem because its methods have been developed only for
specific f, e.g., when
f is a solution of a differential or an
integral equation of a certain type.
A Brief History of Interval Computations
- It started here, in the US.
The main ideas of Interval Computations appeared in the USA, in the Ph.D.
Dissertation of R. E. Moore that was defended at Stanford in 1962.
The first application of interval computation
was presented by R. E. Moore in 1959.
The first monograph, also by R. E. Moore,
appeared in the USA in 1966.
- Moved to Europe.
Later, the center of interval computations moved to Europe, mainly to Germany.
One of the reasons was that in the US, manufacturers were, in
cost-conscious, and they were thus less
worried about inaccuracy of sensors: ``if a sensor is not good enough,
let's spend some more money and buy a better one''.
The main users of this techniques were scientists, for whom this
solution did not work, because they were working at
the cutting edge of accuracy, and they were already using the best
possible sensors to measure their micro-quantities.
- As a result, Interval Computations is not widely
known in the US, while in Germany, it is a part of the standard
qualifying exam for several areas of
Numerical Mathematics. Germany was the place where
the first specialized journal appeared. Germany still hosts regular
conferences in interval computations.
- A recent outburst of activity
Recently, there has been an outburst of activity in the USA and
internationally, related to Interval Computations:
A new international journal Interval Computation has been launched in
1991 (starting from 1995, it is issued under the new title
In 1993, a well-represented International Conference on Interval
Computations was held in Lafayette, LA.
In 1995, an International Workshop on Applications of Interval
Computations was held in El Paso, Texas.
Numerous applications of interval computations are described in the
Proceedings of the International Workshop on Applications of Interval
Computations, held in El Paso, Texas, on February 23-25.
Back to Applications of Interval Computations
Back to the main menu of the Interval