Interval analysis

A theory intended for the calculation of rounding errors of calculations on numerical computers. Since not all numbers can be represented exactly in a computer with finite arithmetic, the result of each calculation may contain some errors, resulting from rounding initial data and intermediate results. To calculate the total effect of these errors, with each quantity one associates a pair of numbers, bounding it from above and below, that have an exact representation in the computer. Thus, each quantity is replaced by an interval containing it. Under the arithmetical operations, new intervals are formed according to special operations.

Let $ \mathbf G $ be the set of intervals $ \{ [ a , b ] \} $. The elementary arithmetical operations on intervals are defined as follows:

$$ I \star J = \ \{ {x \star y } : {x \in I , y \in J } \} ,\ \ I , J \in \mathbf G , $$

where $ \star \in \{ + , - , \cdot , / \} $. Division is possible only if the divisor interval does not contain zero. The set $ \mathbf G $ is a semi-group under addition and multiplication. The following equalities hold:

$ I + ( J + K ) = ( I + J ) + K $— associativity of addition;

$ I \cdot ( J \cdot K ) = ( I \cdot J ) \cdot K $— associativity of multiplication;

$ I + J = J + I $— commutativity of addition;

$ I \cdot J = J \cdot I $— commutativity of multiplication. The zero and unit are, respectively, the intervals $ \mathbf 0 = [ 0 , 0 ] $ and $ \mathbf 1 = [ 1 , 1 ] $. A particular feature of these algebraic structures is that inverse elements, both under addition and multiplication, are not uniquely determined, i.e. the equations (in $ X $) $ I + X = J $ and $ I \cdot X = J $ have, in general, non-unique solutions. Moreover, the distributivity law does not hold, e.g.

$$ [ 1 , 2 ] \cdot ( [ 1 , 2 ] - [ 1 , 2 ] ) = [ 1 , 2 ] \cdot [ - 1 , 1 ] = [ - 2 , 2 ] , $$

while

$$ [ 1 , 2 ] \cdot [ 1 , 2 ] - [ 1 , 2 ] \cdot [ 1 , 2 ] = \ [ 1 , 4 ] - [ 1 , 4 ] = \ [ - 3 , 3 ] . $$

There is only subdistributivity:

$$ I \cdot ( J + K ) \subseteq I \cdot J + I \cdot K . $$

The operations over intervals are monotone with respect to inclusion. If $ I \subset K $, $ J \subset L $, then

$$ I + J \subset K + L ,\ \ I - J \subset K - L ,\ \ I \cdot J \subset K \cdot L ,\ \ I / J \subset K / L . $$

A topology is introduced in $ \mathbf G $ by the metric $ \rho ( I , J ) = \max ( | c - a | , | d - b | ) $, where $ I = [ a , b ] $, $ J=[ c , d ] $, and a partial order is given by: $ I < J $ if $ b \leq c $, and $ I = J $ if $ a = c $ and $ b = d $.

A simple-valued function from $ \mathbf G $ into $ \mathbf G $ is called an interval function. The concept of continuity of an interval function is introduced in the ordinary way. The derivative, indefinite and definite integral of an interval function can be defined.

Interval analysis is successfully applied when solving certain problems. However, using this method is expensive: the amount of operations to be performed as well as the memory space needed is more than doubled. Moreover, in sufficiently large problems the interval containing the final answer is often so large that practically one has not solved the problem. To overcome the latter problem, an interval analysis with structures of probability theory has been developed (cf. [3]).

References

[1]	R.E. Moore, "Interval analysis" , Prentice-Hall (1969)
[2]	R.W. Hemming, "Numerical methods for scientists and engineers" , McGraw-Hill (1973)
[3]	K. Nickel (ed.) , Interval mathematics , Lect. notes in comp. science , 29 , Springer (1975)

References

[a1]	W.L. Miranker, U. Kulisch, "Computer arithmetic in theory and practice" , Acad. Press (1981)
[a2]	W.L. Miranker, U. Kulisch, "A new approach in scientific computing" , Acad. Press (1983)
[a3]	J.M. Yohe, "Software for interval arithmetic" ACM Trans. Math. Software , 5 (1979) pp. 50–63