345px|thumb|right|[[Tolerance function () and interval-valued approximation ()]]
Interval arithmetic (also known as interval mathematics, interval analysis or interval computation) is a mathematical technique used to mitigate rounding and measurement errors in mathematical computation by computing function bounds. Numerical methods involving interval arithmetic can guarantee relatively reliable and mathematically correct results. Instead of representing a value as a single number, interval arithmetic or interval mathematics represents each value as a range of possibilities.
Mathematically, instead of working with an uncertain real-valued variable , interval arithmetic works with an interval that defines the range of values that can have. In other words, any value of the variable lies in the closed interval between and . A function , when applied to , produces an interval which includes all the possible values for for all .
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 interval arithmetic is to provide a simple way of calculating upper and lower bounds of a function's range in one or more variables. These endpoints are not necessarily the true supremum or infimum of a range 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
:<math>[a,b] = \{x \in \mathbb{R} \mid a \le x \le b\},</math>
where and are allowed. With one of , infinite, the interval would be an unbounded interval; with both infinite, the interval would be the extended real number line. Since a real number can be interpreted as the interval , intervals and real numbers can be freely combined.
Example
350px|thumb|left|[[Body mass index for a person 1.80 m tall in relation to body weight (in kilograms)]]
Consider the calculation of a person's body mass index (BMI). BMI is calculated as a person's body weight in kilograms divided by the square of their height in meters. Suppose a person uses a scale that has a precision of one kilogram, where intermediate values cannot be discerned, and the true weight is rounded to the nearest whole number. For example, 79.6 kg and 80.3 kg are indistinguishable, as the scale can only display values to the nearest kilogram. It is unlikely that when the scale reads 80 kg, the person has a weight of exactly 80.0 kg. Thus, the scale displaying 80 kg indicates a weight between 79.5 kg and 80.5 kg, or the interval .
The BMI of a man who weighs 80 kg and is 1.80 m tall is approximately 24.7. A weight of 79.5 kg and the same height yields a BMI of 24.537, while a weight of 80.5 kg yields 24.846. Since the body mass is continuous and always increasing for all values within the specified weight interval, the true BMI must lie within the interval . Since the entire interval is less than 25, which is the cutoff between normal and excessive weight, it can be concluded with certainty that the man is of normal weight.
The error in this example does not affect the conclusion (normal weight), but this is not generally true. If the man were slightly heavier, the BMI's range may include the cutoff value of 25. In such a case, the scale's precision would be insufficient to make a definitive conclusion.
The range of BMI examples could be reported as since this interval is a superset of the calculated interval. The range could not, however, be reported as , as the interval does not contain possible BMI values.
Multiple intervals
260px|thumb|right|Body mass index for different weights in relation to height L (in meters)
Height and body weight both affect the value of the BMI. Though the example above only considered variation in weight, height is also subject to uncertainty. Height measurements in meters are usually rounded to the nearest centimeter: a recorded measurement of 1.79 meters represents a height in the interval . Since the BMI uniformly increases with respect to weight and decreases with respect to height, the error interval can be calculated by substituting the lowest and highest values of each interval, and then selecting the lowest and highest results as boundaries. The BMI must therefore exist in the interval
:<math>\frac{[79.5, 80.5)}{[1.785, 1.795)^2} \subseteq [24.673, 25.266].</math>
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.
Interval operators
A binary operation on two intervals, such as addition or multiplication is defined by
:<math>[x_1, x_2] {\,\star\,} [y_1, y_2] = \{ x \star y \, | \, x \in [x_1, x_2] \,\land\, y \in [y_1, y_2] \}.</math>
In other words, it is the set of all possible values of , where and are in their corresponding intervals. If is monotone for each operand on the intervals, which is the case for the four basic arithmetic operations (except division when the denominator contains zero), the extreme values occur at the endpoints of the operand intervals. Writing out all combinations, one way of stating this is
:<math>[x_1, x_2] \star [y_1, y_2] = \left[ \min\{ x_1 \star y_1, x_1 \star y_2, x_2 \star y_1, x_2 \star y_2\}, \max \{x_1 \star y_1, x_1 \star y_2, x_2 \star y_1, x_2 \star y_2\} \right],</math>
provided that is defined for all and .
For practical applications, this can be simplified further:
- Addition: <math display="block">[x_1, x_2] + [y_1, y_2] = [x_1+y_1, x_2+y_2]</math>
- Subtraction: <math display="block">[x_1, x_2] - [y_1, y_2] = [x_1-y_2, x_2-y_1]</math>
- Multiplication: <math display="block">[x_1, x_2] \cdot [y_1, y_2] = [\min \{x_1 y_1,x_1 y_2,x_2 y_1,x_2 y_2\}, \max\{x_1 y_1,x_1 y_2,x_2 y_1,x_2 y_2\}]</math>
- Division: <math display="block">\frac{[x_1, x_2]}{[y_1, y_2]} = [x_1, x_2] \cdot \frac{1}{[y_1, y_2]},</math> where <math display="block">\begin{align}
\frac{1}{[y_1, y_2]} &= \left [\frac{1}{y_2}, \frac{1}{y_1} \right ] && \textrm{if}\;0 \notin [y_1, y_2] \\
\frac{1}{[y_1, 0]} &= \left [-\infty, \frac{1}{y_1} \right ] \\
\frac{1}{[0, y_2]} &= \left [\frac{1}{y_2}, \infty \right ] \\
\frac{1}{[y_1, y_2]} &= \left [-\infty, \frac{1}{y_1} \right ] \cup \left [\frac{1}{y_2}, \infty \right ] \subseteq [-\infty, \infty] && \textrm{if}\;0 \in (y_1, y_2)
\end{align}</math>
The last case loses useful information about the exclusion of . Thus, it is common to work with and 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 . The corresponding multi-interval arithmetic maintains a set of (usually disjoint) intervals and also provides for overlapping intervals to unite. reducing the cost of computation.
Dependency problem
right|thumb|Approximate estimate of the value range
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.
180px|left|thumb|Treating each occurrence of a variable independently
As an illustration, take the function defined by . The values of this function over the interval are . As the natural interval extension, it is calculated as
:<math>[-1, 1]^2 + [-1, 1] = [0,1] + [-1,1] = [-1,2],</math>
which is slightly larger; we have instead calculated the infimum and supremum of the function over . There is a better expression of in which the variable only appears once, namely by rewriting the quadratic by completing the square:
:<math>f(x) = \left(x + \tfrac{1}{2}\right)^2 -\tfrac{1}{4}.</math>
So the suitable interval calculation is
:<math>\left([-1,1] + \tfrac{1}{2}\right)^2 -\tfrac{1}{4} = \left[-\tfrac{1}{2}, \tfrac{3}{2}\right]^2 -\tfrac{1}{4} = \left[0, \tfrac{9}{4}\right] -\tfrac{1}{4} = \left[-\tfrac{1}{4},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 is continuous inside the box. However, not every function can be rewritten this way.
160px|right|thumb|Wrapping effect
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
:<math>\begin{cases} x = p \\ y = p \end{cases} \qquad p\in [-1,1]</math>
is precisely the line between the points and . Using interval methods results in the unit square, . This is known as the wrapping effect.
Linear interval systems
A linear interval system consists of a matrix interval extension and an interval vector . We want the smallest cuboid , for all vectors which there is a pair with and that satisfies
:<math>\mathbf{A} \cdot \mathbf{x} = \mathbf{b}</math>.
For quadratic systems (in other words, for ) there can be such an interval vector , which covers all possible solutions, found simply with the interval Gauss method. This replaces the numerical operations, in that the linear algebra method known as Gaussian elimination becomes its interval version. However, since this method uses the interval entities and repeatedly in the calculation, it can produce poor results for some problems. Hence using the result of the interval-valued Gauss only provides first rough estimates, since although it contains the entire solution set, it also has a large area outside it.
A rough solution can often be improved by an interval version of the Gauss–Seidel method. The motivation for this is that the th row of the interval extension of the linear equation
:<math>
\begin{pmatrix}
{[a_{11}]} & \cdots & {[a_{1n}]} \\
\vdots & \ddots & \vdots \\
{[a_{n1}]} & \cdots & {[a_{nn}]}
\end{pmatrix}
\cdot
\begin{pmatrix}
{x_1} \\
\vdots \\
{x_n}
\end{pmatrix}
=
\begin{pmatrix}
{[b_1]} \\
\vdots \\
{[b_n]}
\end{pmatrix}
</math>
can be determined by the variable if the division is allowed. It is therefore simultaneously
:<math>x_j \in [x_j] \quad \text{and} \quad x_j \in \frac{[b_i]- \sum\limits_{k \neq j} [a_{ik}] \cdot [x_k]}{[a_{ii}]}.</math>
So we can now replace by
:<math>[x_j] \cap \frac{[b_i]- \sum\limits_{k \neq j} [a_{ik}] \cdot [x_k]}{[a_{ii}]},</math>
and so the vector by each element.
Since the procedure is more efficient for a diagonally dominant matrix, instead of the system , one can often try multiplying it by an appropriate rational matrix with the resulting matrix equation
:<math>(\mathbf{M}\cdot[\mathbf{A}])\cdot \mathbf{x} = \mathbf{M}\cdot[\mathbf{b}]</math>
left to solve. If one chooses, for example, for the central matrix , then is an outer extension of the identity matrix.
These methods only work well if the widths of the intervals occurring are sufficiently small. For wider intervals, it can be useful to use an interval-linear system on finite (albeit large) real number equivalent linear systems. If all the matrices are invertible, it is sufficient to consider all possible combinations (upper and lower) of the endpoints occurring in the intervals. The resulting problems can be resolved using conventional numerical methods. Interval arithmetic is still used to determine rounding errors.
This is only suitable for systems of smaller dimension, since with a fully occupied matrix, real matrices need to be inverted, with vectors for the right-hand side. This approach was developed by Jiri Rohn and is still being developed.
History
Interval arithmetic is not a completely new phenomenon in mathematics; it has appeared several times under different names in the course of history. For example, Archimedes calculated lower and upper bounds in the 3rd century BC. Actual calculation with intervals has neither been as popular as other numerical techniques nor been completely forgotten.
Rules for calculating with intervals and other subsets of the real numbers were published in a 1931 work by Rosalind Cicely Young.
Further reading
- (11 pages) (NB. About Triplex-ALGOL Karlsruhe, an ALGOL 60 (1963) implementation with support for triplex numbers.)
External links
- Interval arithmetic (Wolfram Mathworld)
- Validated Numerics for Pedestrians
- Interval Methods from Arnold Neumaier , University of Vienna
- SWIM (Summer Workshop on Interval Methods)
- International Conference on Parallel Processing and Applied Mathematics
- INTLAB, Institute for Reliable Computing , Hamburg University of Technology
- Ball arithmetic by Joris van der Hoeven
- kv - a C++ Library for Verified Numerical Computation
- Arb - a C library for arbitrary-precision ball arithmetic