Applications of Interval Computations: General

Data Processing

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 processing algorithm. So, in the majority of cases, data processing processes the results of measurements.

Why Do We Process Data At All?

Main Problem

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.

In Many Cases, We Do Not Know Probabilities

In many 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 interval [x-D,x+D].

Historical comment.

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.
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.

Since we are dealing with intervals, the entire area is called interval computations.

In this case, our problem takes the following form:

Main Problem (In Case We Do Not Know Probabilities)

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 y=f(x1,...,xn)
(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 estimate y:

We know:

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].

This is the basic problem of interval computations with which the entire area started; see, e.g., early papers on interval computations (see also) including:

Where Does This Main Problem Fit In Traditional Mathematics

A Brief History of Interval Computations


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 Computations website