Interval Arithmetic

Interval arithmetic (also known as interval mathematics, interval analysis, or interval computation) is a mathematical technique used to put bounds on rounding errors and measurement errors in mathematical computation. Numerical methods using interval arithmetic can guarantee reliable and mathematically correct results. Instead of representing a value as a single number, interval arithmetic represents each value as a range of possibilities. For example, instead of saying the height of someone is approximately 2 meters, one could using interval arithmetic, say that the height of the person is definitely between 1.97 meters and 2.03 meters.

Mathematically, using interval arithmetic, instead of working with an uncertain real-valued variable $x$, one works with an interval ,b/math> that defines the range of values that $x$ can have. In other words, any value of the variable $x$ lies in the closed interval between $a$ and $b$. A function $f$, when applied to $x$, yields an inexact value; $f$ instead produces an interval ,d/math> which includes all the possible values for $f(x)$ for all x \in ,b/math>.

Interval arithmetic is suitable for a variety of purposes; the most common use is in scientific works, particularly when the calculations are handled by software, where it is used to keep track of rounding errors in calculations and of uncertainties in the knowledge of the exact values of physical and technical parameters. The latter often arise from measurement errors and tolerances for components or due to limits on computational accuracy. Interval arithmetic also helps find guaranteed solutions to equations (such as differential equations) and optimization problems.

Introduction

The main objective of the interval arithmetic is a simple way to calculate upper and lower bounds for the range of a function in one or more variables. These endpoints are not necessarily the true supremum or infimum, since the precise calculation of those values can be difficult or impossible; the bounds only need to contain the function's range as a subset.

This treatment is typically limited to real intervals, so quantities in the form
: ,b= \,
where $a =$ and $b =$ are allowed. With one of $a$, $b$ infinite, the interval would be an unbounded interval; with both infinite, the interval would be the extended real number line. Since a real number $r$ can be interpreted as the interval ,r intervals and real numbers can be freely combined.

As with traditional calculations with real numbers, simple arithmetic operations and functions on elementary intervals must first be defined. More complicated functions can be calculated from these basic elements.

Example

As an example, consider the calculation of body mass index (BMI) and assess whether a person is overweight. BMI is calculated as a person's body weight in kilograms divided by the square of their height in meters. A weighing machine may have a resolution of one kilogram. Intermediate values cannot be discerned, and the true weight is rounded to the nearest whole number. For example, 79.6 kg and 80.3kg are indistinguishable as the weighing machine gives meaningful (correct) values only unto the accuracy of the nearest kilogram. It is unlikely that when the machine reads 80kg, the person weighs ''exactly'' 80.0kg. In normal rounding to the nearest value, if the weighing machine shows 80kg, it indicates a weight between 79.5kg and 80.5kg. This corresponds with the interval 9.5, 80.5/math>.

For a man who weighs 80kg and is 1.80m tall, the BMI is approximately 24.7. A weight of 79.5 kg and the same height yields approx. 24.537, while a weight of 80.5 kg yields approx. 24.846. Since the function is monotonically increasing, we conclude that the true BMI is in the range 4.537, 24.846/math>. Since the entire range is less than 25, which is the cutoff between normal and excessive weight, we conclude that the man is of normal weight.

The error in this case does not affect the conclusion (normal weight), but this is not always the case. If the man was slightly heavier, the BMI's range may include the cutoff value of 25. In that case, the scale's precision was insufficient to make a definitive conclusion.

Also, note that the range of BMI examples could be reported as 4.5, 24.9/math>, since this interval is a superset of the calculated interval. The range could not, however, be reported as 4.6, 24.8/math>, as now the interval does not contain possible BMI values.

Interval arithmetic states the range of possible outcomes explicitly. Results are no longer stated as numbers, but as intervals that represent imprecise values. The size of the intervals are similar to error bars in expressing the extent of uncertainty.

Multiple intervals

Height and body weight both affect the value of the BMI. We have already treated weight as an uncertain measurement, but height is also subject to uncertainty. Height measurements in meters are usually rounded to the nearest centimeter: a recorded measurement of 1.79 meters actually means a height in the interval .785, 1.795/math>. Now, all four combinations of possible height/weight values must be considered. Using the interval methods described below, the BMI lies in the interval

:\frac \subseteq 4.673, 25.266
In this case, the man may have normal weight or be overweight; the weight and height measurements were insufficiently precise to make a definitive conclusion. This demonstrates interval arithmetic's ability to correctly track and propagate errors.

Interval operators

A binary operation $\star$ on two intervals, such as addition or multiplication, is defined by

: _1, x_2 _1, y_2= \.

In other words, it is the set of all possible values of $x \star y$, where $x$ and $y$ are in their corresponding intervals. If $\star$ is monotone in each operand on the intervals, which is the case for the four basic arithmetic operations (except division when the denominator contains $0$), the extreme values occur at the endpoints of the operand intervals. Writing out all combinations, one way of stating this is
: _1, x_2\star _1, y_2= \left \min\, \max \ \right
provided that $x \star y$ is defined for all x\in _1, x_2/math> and y \in _1, y_2/math>.

For practical applications this can be simplified further:

* Addition: _1, x_2+ _1, y_2= _1+y_1, x_2+y_2/math>
* Subtraction: _1, x_2- _1, y_2= _1-y_2, x_2-y_1/math>
* Multiplication: _1, x_2\cdot _1, y_2= min \, \max\/math>
* Division: \frac = _1, x_2\cdot \frac, where \begin
\frac &= \left tfrac, \tfrac \right && \textrm\;0 \notin _1, y_2\\
\frac &= \left \infty, \tfrac \right \\
\frac &= \left tfrac, \infty \right \\
\frac &= \left \infty, \tfrac \right \cup \left tfrac, \infty \right \subseteq \infty, \infty&& \textrm\;0 \in (y_1, y_2)
\end

The last case loses useful information about the exclusion of $(1/y_1, 1/y_2)$. Thus, it is common to work with \left \infty, \tfrac \right /math> and \left tfrac, \infty \right /math> as separate intervals. More generally, when working with discontinuous functions, it is sometimes useful to do the calculation with so-called ''multi-intervals'' of the form \bigcup_ \left a_i, b_i \right The corresponding ''multi-interval arithmetic'' maintains a set of (usually disjoint) intervals and also provides for overlapping intervals to unite.

Interval multiplication often only requires two multiplications. If $x_1$, $y_1$ are nonnegative,

: _1, x_2\cdot _1, y_2= _1 \cdot y_1, x_2 \cdot y_2 \qquad \text x_1, y_1 \geq 0.

The multiplication can be interpreted as the area of a rectangle with varying edges. The result interval covers all possible areas, from smallest to the largest.

With the help of these definitions, it is already possible to calculate the range of simple functions, such as $f(a,b,x) = a \cdot x + b.$ For example, if a = ,2/math>, b = ,7/math> and x = ,3/math>:

:f(a,b,x) = ( ,2\cdot ,3 + ,7= \cdot 2, 2\cdot 3+ ,7= ,13

Notation

To make the notation of intervals smaller in formulae, brackets can be used.

\equiv _1, x_2/math> can be used to represent an interval. Note that in such a compact notation, /math> should not be confused between a single-point interval _1, x_1/math> and a general interval. For the set of all intervals, we can use

: R:= \left \

as an abbreviation. For a vector of intervals \left( 1, \ldots , n \right) \in Rn we can use a bold font: mathbf/math>.

Elementary functions

Interval functions beyond the four basic operators may also be defined.

For monotonic functions in one variable, the range of values is simple to compute. If $f: \R \to \R$ is monotonically increasing (resp. decreasing) in the interval _1, x_2 then for all y_1, y_2 \in _1, x_2/math> such that $y_1 \leq y_2,$ f(y_1) (resp. $f(y_2) < f(y_1)$).

The range corresponding to the interval _1, y_2\subseteq _1, x_2/math> can be therefore calculated by applying the function to its endpoints:

:f( _1, y_2 = \left min \left \, \max \left\\right

From this, the following basic features for interval functions can easily be defined:

* Exponential function: a^ = ^,a^/math> for $a > 1,$
* Logarithm: \log_a _1, x_2= log_a , \log_a /math> for positive intervals _1, x_2/math> and $a>1,$
* Odd powers: _1, x_2n = _1^n,x_2^n/math>, for odd $n\in \N.$

For even powers, the range of values being considered is important, and needs to be dealt with before doing any multiplication. For example, $x^n$ for x \in 1,1/math> should produce the interval ,1/math> when $n = 2, 4, 6, \ldots.$ But if 1,1n is taken by repeating interval multiplication of form 1,1\cdot 1,1\cdot \cdots \cdot 1,1/math> then the result is 1,1 wider than necessary.

More generally one can say that, for piecewise monotonic functions, it is sufficient to consider the endpoints $x_1$, $x_2$of an interval, together with the so-called ''critical points'' within the interval, being those points where the monotonicity of the function changes direction. For the sine and cosine functions, the critical points are at $\left(\tfrac + n\right)\pi$ or $n\pi$ for $n \in \Z$, respectively. Thus, only up to five points within an interval need to be considered, as the resulting interval is 1,1/math> if the interval includes at least two extrema. For sine and cosine, only the endpoints need full evaluation, as the critical points lead to easily pre-calculated values—namely -1, 0, and 1.

Interval extensions of general functions

In general, it may not be easy to find such a simple description of the output interval for many functions. But it may still be possible to extend functions to interval arithmetic.
If $f:\mathbb^n \to \mathbb$ is a function from a real vector to a real number, then mathbbn \to mathbb/math> is called an ''interval extension'' of $f$ if
: mathbf \supseteq \.

This definition of the interval extension does not give a precise result. For example, both _1,x_2 = ^, e^/math> and _1,x_2 = /math> are allowable extensions of the exponential function. Tighter extensions are desirable, though the relative costs of calculation and imprecision should be considered; in this case, /math> should be chosen as it gives the tightest possible result.

Given a real expression, its ''natural interval extension'' is achieved by using the interval extensions of each of its subexpressions, functions and operators.

The ''Taylor interval extension'' (of degree $k$ ) is a $k+1$ times differentiable function $f$ defined by

: mathbf := f(\mathbf) + \sum_^k\frac\mathrm^i f(\mathbf) \cdot ( mathbf- \mathbf)^i + mathbf mathbf \mathbf),
for some \mathbf \in mathbf/math>, where $\mathrm^i f(\mathbf)$ is the $i$-th order differential of $f$ at the point $\mathbf$ and /math> is an interval extension of the ''Taylor remainder''

:$r(\mathbf, \xi, \mathbf) = \frac\mathrm^ f(\xi) \cdot (\mathbf-\mathbf)^.$

The vector $\xi$ lies between $\mathbf$ and $\mathbf$ with \mathbf, \mathbf \in mathbf/math>, $\xi$ is protected by mathbf/math>.
Usually one chooses $\mathbf$ to be the midpoint of the interval and uses the natural interval extension to assess the remainder.

The special case of the Taylor interval extension of degree $k = 0$ is also referred to as the ''mean value form''.

Complex interval arithmetic

An interval can also be defined as a locus of points at a given distance from the center, and this definition can be extended from real numbers to complex numbers. As it is the case with computing with real numbers, computing with complex numbers involves uncertain data. So, given the fact that an interval number is a real closed interval and a complex number is an ordered pair of real numbers, there is no reason to limit the application of interval arithmetic to the measure of uncertainties in computations with real numbers. Interval arithmetic can thus be extended, via complex interval numbers, to determine regions of uncertainty in computing with complex numbers.

The basic algebraic operations for real interval numbers (real closed intervals) can be extended to complex numbers. It is therefore not surprising that complex interval arithmetic is similar to, but not the same as, ordinary complex arithmetic. It can be shown that, as it is the case with real interval arithmetic, there is no distributivity between addition and multiplication of complex interval numbers except for certain special cases, and inverse elements do not always exist for complex interval numbers. Two other useful properties of ordinary complex arithmetic fail to hold in complex interval arithmetic: the additive and multiplicative properties, of ordinary complex conjugates, do not hold for complex interval conjugates.

Interval arithmetic can be extended, in an analogous manner, to other multidimensional number systems such as quaternions and octonions, but with the expense that we have to sacrifice other useful properties of ordinary arithmetic.

Interval methods

The methods of classical numerical analysis cannot be transferred one-to-one into interval-valued algorithms, as dependencies between numerical values are usually not taken into account.

Rounded interval arithmetic

To work effectively in a real-life implementation, intervals must be compatible with floating point computing. The earlier operations were based on exact arithmetic, but in general fast numerical solution methods may not be available. The range of values of the function $f(x, y) = x + y$
for x \in .1, 0.8/math> and y \in .06, 0.08/math> are for example .16, 0.88/math>. Where the same calculation is done with single digit precision, the result would normally be .2, 0.9/math>. But .2, 0.9\not\supseteq .16, 0.88/math>,
so this approach would contradict the basic principles of interval arithmetic, as a part of the domain of f( .1, 0.8 .06, 0.08 would be lost.
Instead, the outward rounded solution .1, 0.9/math> is used.

The standard IEEE 754 for binary floating-point arithmetic also sets out procedures for the implementation of rounding. An IEEE 754 compliant system allows programmers to round to the nearest floating point number; alternatives are rounding towards 0 (truncating), rounding toward positive infinity (i.e. up), or rounding towards negative infinity (i.e. down).

The required ''external rounding'' for interval arithmetic can thus be achieved by changing the rounding settings of the processor in the calculation of the upper limit (up) and lower limit (down). Alternatively, an appropriate small interval varepsilon_1, \varepsilon_2/math> can be added.

Dependency problem

The so-called ''dependency problem'' is a major obstacle to the application of interval arithmetic. Although interval methods can determine the range of elementary arithmetic operations and functions very accurately, this is not always true with more complicated functions. If an interval occurs several times in a calculation using parameters, and each occurrence is taken independently then this can lead to an unwanted expansion of the resulting intervals.

As an illustration, take the function $f$ defined by $f(x) = x^2 + x.$ The values of this function over the interval 1, 1/math> are \left \tfrac, 2 \right As the natural interval extension, it is calculated as:

: 1, 12 + 1, 1= ,1+ 1,1= 1,2

which is slightly larger; we have instead calculated the infimum and supremum of the function $h(x, y)= x^2+y$ over x, y \in 1,1 There is a better expression of $f$ in which the variable $x$ only appears once, namely by rewriting $f(x) = x^2 + x$ as addition and squaring in the quadratic

:$f(x) = \left(x + \frac\right)^2 -\frac.$

So the suitable interval calculation is

:\left( 1,1+ \frac\right)^2 -\frac = \left \frac, \frac\right2 -\frac = \left , \frac\right-\frac = \left \frac,2\right/math>

and gives the correct values.

In general, it can be shown that the exact range of values can be achieved, if each variable appears only once and if $f$ is continuous inside the box. However, not every function can be rewritten this way.

The dependency of the problem causing over-estimation of the value range can go as far as covering a large range, preventing more meaningful conclusions.

An additional increase in the range stems from the solution of areas that do not take the form of an interval vector. The solution set of the linear system

:\begin x = p \\ y = p \end \qquad p\in 1,1/math>

is precisely the line between the points $(-1,-1)$ and $(1,1).$ Using interval methods results in the unit square, 1,1\times 1,1 This is known as the '' wrapping effect''.

Linear interval systems

A linear interval system consists of a matrix interval extension mathbf\in mathbb and an interval vector mathbf\in mathbb. We want the smallest cuboid mathbf\in mathbb