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
x
[a,b]
x
x
a
b
f
x
[c,d]
f(x)
x\in[a,b]
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.
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
[a,b]=\{x\inR\mida\lex\leb\},
a={-infty}
b={infty}
a
b
r
[r,r],
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
[79.5,80.5)
The BMI of a man who weighs 80 kg and is 1.80m 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
[24.537,24.846]
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
[24.5,24.9]
[24.6,24.8]
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
[1.785,1.795)
[79.5,80.5) | |
[1.785,1.795)2 |
\subseteq[24.673,25.266].
A binary operation
\star
[x1,x2]{\star}[y1,y2]=\{x\stary|x\in[x1,x2]\landy\in[y1,y2]\}.
In other words, it is the set of all possible values of
x\stary
x
y
\star
0
[x1,x2]\star[y1,y2]=\left[min\{x1\stary1,x1\stary2,x2\stary1,x2\stary2\},max\{x1\stary1,x1\stary2,x2\stary1,x2\stary2\}\right],
x\stary
x\in[x1,x2]
y\in[y1,y2]
For practical applications, this can be simplified further:
\frac &= \left [\tfrac{1}{y_2}, \tfrac{1}{y_1} \right ] && \textrm\;0 \notin [y_1, y_2] \\\frac &= \left [-\infty, \tfrac{1}{y_1} \right ] \\\frac &= \left [\tfrac{1}{y_2}, \infty \right ] \\\frac &= \left [-\infty, \tfrac{1}{y_1} \right ] \cup \left [\tfrac{1}{y_2}, \infty \right ] \subseteq [-\infty, \infty] && \textrm\;0 \in (y_1, y_2)\end
The last case loses useful information about the exclusion of
(1/y1,1/y2)
\left[-infty,\tfrac{1}{y1}\right]
\left[\tfrac{1}{y2},infty\right]
Interval multiplication often only requires two multiplications. If
x1
y1
[x1,x2] ⋅ [y1,y2]=[x1 ⋅ y1,x2 ⋅ y2], ifx1,y1\geq0.
The multiplication can be interpreted as the area of a rectangle with varying edges. The result interval covers all possible areas, from the 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 ⋅ x+b.
a=[1,2]
b=[5,7]
x=[2,3]
f(a,b,x)=([1,2] ⋅ [2,3])+[5,7]=[1 ⋅ 2,2 ⋅ 3]+[5,7]=[7,13].
To shorten the notation of intervals, brackets can be used.
[x]\equiv[x1,x2]
[x]
[x1,x1]
[\R]:=\left\{[x1,x2]|x1\leqx2andx1,x2\in\R\cup\{-infty,infty\}\right\}
as an abbreviation. For a vector of intervals
\left([x]1,\ldots,[x]n\right)\in[\R]n
[x]
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
[x1,x2],
y1,y2\in[x1,x2]
y1<y2,
f(y1)\leqf(y2)
f(y2)\leqf(y1)
The range corresponding to the interval
[y1,y2]\subseteq[x1,x2]
f([y1,y2])=\left[min\left\{f(y1),f(y2)\right\},max\left\{f(y1),f(y2)\right\}\right].
From this, the following basic features for interval functions can easily be defined:
[x1,x2] | |
a |
=
x1 | |
[a |
x2 | |
,a |
]
a>1,
loga[x1,x2]=[loga{x1},loga{x2}]
[x1,x2]
a>1,
[x1,
n | |
x | |
2] |
=
n] | |
[x | |
2 |
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,
xn
x\in[-1,1]
[0,1]
n=2,4,6,\ldots.
[-1,1]n
[-1,1] ⋅ [-1,1] ⋅ … ⋅ [-1,1]
[-1,1],
More generally one can say that, for piecewise monotonic functions, it is sufficient to consider the endpoints
x1
x2
\left(\tfrac{1}{2}+n\right)\pi
n\pi
n\in\Z
[-1,1]
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:Rn\toR
[f]:[R]n\to[R]
f
[f]([x])\supseteq\{f(y)\midy\in[x]\}.
This definition of the interval extension does not give a precise result. For example, both
[f]([x1,x2])=
x1 | |
[e |
,
x2 | |
e |
]
[g]([x1,x2])=[{-infty},{infty}]
[f]
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
k+1
f
[f]([x]):=f(y)+
| ||||
\sum | ||||
i=1 |
Dif(y) ⋅ ([x]-y)i+[r]([x],[x],y),
y\in[x]
Dif(y)
i
f
y
[r]
r(x,\xi,y)=
1 | |
(k+1)! |
Dk+1f(\xi) ⋅ (x-y)k+1.
The vector
\xi
x
y
x,y\in[x]
\xi
[x]
y
The special case of the Taylor interval extension of degree
k=0
An interval can be defined as a set of points within a specified distance of the center, and this definition can be extended from real numbers to complex numbers. Another extension defines intervals as rectangles in the complex plane. As 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. One can either define complex interval arithmetic using rectangles or using disks, both with their respective advantages and disadvantages.
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 is the case with real interval arithmetic, there is no distributivity between the 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.
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.
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 for it. The range of values of the function
f(x,y)=x+y
x\in[0.1,0.8]
y\in[0.06,0.08]
[0.16,0.88]
[0.2,0.9]
[0.2,0.9]\not\supseteq[0.16,0.88]
f([0.1,0.8],[0.06,0.08])
[0.1,0.9]
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
[\varepsilon1,\varepsilon2]
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
f(x)=x2+x.
[-1,1]
\left[-\tfrac{1}{4},2\right].
[-1,1]2+[-1,1]=[0,1]+[-1,1]=[-1,2],
which is slightly larger; we have instead calculated the infimum and supremum of the function
h(x,y)=x2+y
x,y\in[-1,1].
f
x
f(x)=x2+x
f(x)=\left(x+
1 | |
2 |
\right)2-
1 | |
4 |
.
So the suitable interval calculation is
\left([-1,1]+
1 | |
2 |
\right)2-
1 | |
4 |
=\left[-
1 | |
2 |
,
3 | |
2 |
\right]2-
1 | |
4 |
=\left[0,
9 | |
4 |
\right]-
1 | |
4 |
=\left[-
1 | |
4 |
,2\right]
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
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{cases}x=p\ y=p\end{cases} p\in[-1,1]
is precisely the line between the points
(-1,-1)
(1,1).
[-1,1] x [-1,1].
A linear interval system consists of a matrix interval extension
[A]\in[R]n x
[b]\in[R]n
[x]\in[R]m
x\inRm
(A,b)
A\in[A]
b\in[b]
A ⋅ x=b
For quadratic systems - in other words, for
n=m
[x]
[A]
[b]
A rough solution
[x]
i
\begin{pmatrix} {[a11]}& … &{[a1n]}\\ \vdots&\ddots&\vdots\\ {[an1]}& … &{[ann]} \end{pmatrix} ⋅ \begin{pmatrix} {x1}\\ \vdots\\ {xn} \end{pmatrix} = \begin{pmatrix} {[b1]}\\ \vdots\\ {[bn]} \end{pmatrix}
xi
1/[aii]
xj\in[xj]
xj\in
[bi]-\sum\limitsk[aik] ⋅ [xk] | |
[aii] |
[xj]
[xj]\cap
[bi]-\sum\limitsk[aik] ⋅ [xk] | |
[aii] |
[x]
[A] ⋅ x=[b],
M
(M ⋅ [A]) ⋅ x=M ⋅ [b]
M=A-1
A\in[A]
M ⋅ [A]
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
A\in[A]
This is only suitable for systems of smaller dimension, since with a fully occupied
n x n
n2 | |
2 |
2n
An interval variant of Newton's method for finding the zeros in an interval vector
[x]
z\in[x]
y\in[x]
f(z)\inf(y)+[Jf]([x]) ⋅ (z-y)
z
f(z)=0
f(y)+[Jf]([x]) ⋅ (z-y)=0
z\iny-
-1 | |
[J | |
f]([x]) |
⋅ f(y)
-1 | |
[J | |
f]([x]) |
⋅ f(y))
In each step of the interval Newton method, an approximate starting value
[x]\in[R]n
[x]\cap\left(y-
-1 | |
[J | |
f]([x]) |
⋅ f(y)\right)
f
[x]
The method converges on all zeros in the starting region. Division by zero can lead to the separation of distinct zeros, though the separation may not be complete; it can be complemented by the bisection method.
As an example, consider the function
f(x)=x2-2
[x]=[-2,2]
y=0
Jf(x)=2x
[-2,2]\cap\left(0-
1 | |
2 ⋅ [-2,2] |
(0-2)\right)=[-2,2]\cap([{-infty},{-0.5}]\cup[{0.5},{infty}])=[{-2},{-0.5}]\cup[{0.5},{2}]
x\in[{-2},{-0.5}]
[{0.5},{2}]
-\sqrt{2}
+\sqrt{2}
The Interval Newton method can also be used with thick functions such as
g(x)=x2-[2,3]
\left[-\sqrt{3},-\sqrt{2}\right]\cup\left[\sqrt{2},\sqrt{3}\right]
The various interval methods deliver conservative results as dependencies between the sizes of different interval extensions are not taken into account. However, the dependency problem becomes less significant for narrower intervals.
Covering an interval vector
[x]
[x1],\ldots,[xk],
[x]=
k | |
cup | |
i=1 |
[xi],
is then valid for the range of values.
f([x])=
k | |
cup | |
i=1 |
f([xi]).
So, for the interval extensions described above the following holds:
[f]([x])\supseteq
k | |
cup | |
i=1 |
[f]([xi]).
Since
[f]([x])
Such a cover can be generated by the bisection method such as thick elements
[xi1,xi2]
[x]=([x11,x12],\ldots,[xn1,xn2])
\left[xi1,\tfrac{1}{2}(xi1+xi2)\right]
\left[\tfrac{1}{2}(xi1+xi2),xi2\right].
2r
r
With very wide intervals, it can be helpful to split all intervals into several subintervals with a constant (and smaller) width, a method known as mincing. This then avoids the calculations for intermediate bisection steps. Both methods are only suitable for problems of low dimension.
Interval arithmetic can be used in various areas (such as set inversion, motion planning, set estimation, or stability analysis) to treat estimates with no exact numerical value.
Interval arithmetic is used with error analysis, to control rounding errors arising from each calculation. The advantage of interval arithmetic is that after each operation there is an interval that reliably includes the true result. The distance between the interval boundaries gives the current calculation of rounding errors directly:
Error =
abs(a-b)
[a,b]
Parameters for which no exact figures can be allocated often arise during the simulation of technical and physical processes. The production process of technical components allows certain tolerances, so some parameters fluctuate within intervals. In addition, many fundamental constants are not known precisely.
If the behavior of such a system affected by tolerances satisfies, for example,
f(x,p)=0
p\in[p]
x
\{x|\existsp\in[p],f(x,p)=0\}
Interval arithmetic can also be used with affiliation functions for fuzzy quantities as they are used in fuzzy logic. Apart from the strict statements
x\in[x]
x\not\in[x]
\mu\in[0,1]
\mu=1
\mu=0
For fuzzy arithmetic only a finite number of discrete affiliation stages
\mui\in[0,1]
\left[x(1)\right]\supset\left[x(2)\right]\supset … \supset\left[x(k)\right].
The interval
\left[x(i)\right]
\mui.
The appropriate distribution for a function
f(x1,\ldots,xn)
x1,\ldots,xn
(1) | |
\left[x | |
1 |
\right]\supset … \supset
(k) | |
\left[x | |
1 |
\right],\ldots,
(1) | |
\left[x | |
n |
\right]\supset … \supset
(k) | |
\left[x | |
n |
\right]
can be approximated by the sequence.
\left[y(1)\right]\supset … \supset\left[y(k)\right],
where
\left[y(i)\right]=f\left(
(i) | |
\left[x | |
1 |
\right],\ldots
(i) | |
\left[x | |
n |
\right]\right)
and can be calculated by interval methods. The value
\left[y(1)\right]
Warwick Tucker used interval arithmetic in order to solve the 14th of Smale's problems, that is, to show that the Lorenz attractor is a strange attractor. Thomas Hales used interval arithmetic in order to solve the Kepler conjecture.
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 223/71 < π < 22/7 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. Arithmetic work on range numbers to improve the reliability of digital systems was then published in a 1951 textbook on linear algebra by ; intervals were used to measure rounding errors associated with floating-point numbers. A comprehensive paper on interval algebra in numerical analysis was published by Teruo Sunaga (1958).
The birth of modern interval arithmetic was marked by the appearance of the book Interval Analysis by Ramon E. Moore in 1966. He had the idea in spring 1958, and a year later he published an article about computer interval arithmetic. Its merit was that starting with a simple principle, it provided a general method for automated error analysis, not just errors resulting from rounding.
Independently in 1956, Mieczyslaw Warmus suggested formulae for calculations with intervals, though Moore found the first non-trivial applications.
In the following twenty years, German groups of researchers carried out pioneering work around Ulrich W. Kulisch and at the University of Karlsruhe and later also at the Bergische University of Wuppertal.For example, explored more effective implementations, while improved containment procedures for the solution set of systems of equations were due to Arnold Neumaier among others. In the 1960s, Eldon R. Hansen dealt with interval extensions for linear equations and then provided crucial contributions to global optimization, including what is now known as Hansen's method, perhaps the most widely used interval algorithm. Classical methods in this often have the problem of determining the largest (or smallest) global value, but could only find a local optimum and could not find better values; Helmut Ratschek and Jon George Rokne developed branch and bound methods, which until then had only applied to integer values, by using intervals to provide applications for continuous values.
In 1988, Rudolf Lohner developed Fortran-based software for reliable solutions for initial value problems using ordinary differential equations.
The journal Reliable Computing (originally Interval Computations) has been published since the 1990s, dedicated to the reliability of computer-aided computations. As lead editor, R. Baker Kearfott, in addition to his work on global optimization, has contributed significantly to the unification of notation and terminology used in interval arithmetic.
In recent years work has concentrated in particular on the estimation of preimages of parameterized functions and to robust control theory by the COPRIN working group of INRIA in Sophia Antipolis in France.
There are many software packages that permit the development of numerical applications using interval arithmetic. These are usually provided in the form of program libraries. There are also C++ and Fortran compilers that handle interval data types and suitable operations as a language extension, so interval arithmetic is supported directly.
Since 1967, Extensions for Scientific Computation (XSC) have been developed in the University of Karlsruhe for various programming languages, such as C++, Fortran, and Pascal. The first platform was a Zuse Z23, for which a new interval data type with appropriate elementary operators was made available. There followed in 1976, Pascal-SC, a Pascal variant on a Zilog Z80 that it made possible to create fast, complicated routines for automated result verification. Then came the Fortran 77-based ACRITH-XSC for the System/370 architecture (FORTRAN-SC), which was later delivered by IBM. Starting from 1991 one could produce code for C compilers with Pascal-XSC; a year later the C++ class library supported C-XSC on many different computer systems. In 1997, all XSC variants were made available under the GNU General Public License. At the beginning of 2000, C-XSC 2.0 was released under the leadership of the working group for scientific computation at the Bergische University of Wuppertal to correspond to the improved C++ standard.
Another C++-class library was created in 1993 at the Hamburg University of Technology called Profil/BIAS (Programmer's Runtime Optimized Fast Interval Library, Basic Interval Arithmetic), which made the usual interval operations more user-friendly. It emphasized the efficient use of hardware, portability, and independence of a particular presentation of intervals.
The Boost collection of C++ libraries contains a template class for intervals. Its authors are aiming to have interval arithmetic in the standard C++ language.
The Frink programming language has an implementation of interval arithmetic that handles arbitrary-precision numbers. Programs written in Frink can use intervals without rewriting or recompilation.
GAOL is another C++ interval arithmetic library that is unique in that it offers the relational interval operators used in interval constraint programming.
The Moore library is an efficient implementation of interval arithmetic in C++. It provides intervals with endpoints of arbitrary precision and is based on the concepts feature of C++.
The Julia programming language has an implementation of interval arithmetics along with high-level features, such as root-finding (for both real and complex-valued functions) and interval constraint programming, via the ValidatedNumerics.jl package.
In addition, computer algebra systems, such as FriCAS, Mathematica, Maple, Maxima (software) and MuPAD, can handle intervals. A Matlab extension Intlab builds on BLAS routines, and the Toolbox b4m makes a Profil/BIAS interface. Moreover, the Software Euler Math Toolbox includes an interval arithmetic.
A library for the functional language OCaml was written in assembly language and C.
A standard for interval arithmetic, IEEE Std 1788-2015, has been approved in June 2015. Two reference implementations are freely available. These have been developed by members of the standard's working group: The libieeep1788 library for C++, and the interval package for GNU Octave.
A minimal subset of the standard, IEEE Std 1788.1-2017, has been approved in December 2017 and published in February 2018. It should be easier to implement and may speed production of implementations.
Several international conferences or workshops take place every year in the world. The main conference is probably SCAN (International Symposium on Scientific Computing, Computer Arithmetic, and Verified Numerical Computation), but there is also SWIM (Small Workshop on Interval Methods), PPAM (International Conference on Parallel Processing and Applied Mathematics), REC (International Workshop on Reliable Engineering Computing).