Interval analysis
Interval analysis is a branch of numerical analysis in which quantities are represented by sets of real numbers rather than by single approximations. Its standard representation is the closed interval
[ [a,b]={x\in\mathbb{R}:a\leq x\leq b}, ]
where (a) and (b) are respectively the lower and upper endpoints. Arithmetic operations and elementary functions are extended so that the resulting interval contains every value obtainable from admissible inputs. This containment property permits the simultaneous treatment of uncertain data, truncation error, and floating-point rounding.
Unlike conventional floating-point computation, which ordinarily returns an approximation without an intrinsic proof of its error, interval computation returns an enclosure. Such an enclosure can establish that a solution exists within a specified region, that no solution occurs there, or that a computed quantity remains bounded under stated assumptions. The width of the enclosure also records uncertainty introduced by the input representation and by the sequence of operations.
Mathematical foundation
For intervals (X=[\underline{x},\overline{x}]) and (Y=[\underline{y},\overline{y}]), interval addition and subtraction are defined by
[ X+Y= [\underline{x}+\underline{y}, \overline{x}+\overline{y}] ]
and
[ X-Y= [\underline{x}-\overline{y}, \overline{x}-\underline{y}]. ]
Multiplication uses the extreme products of the endpoints:
[ XY= \left[ \min {\underline{x}\underline{y}, \underline{x}\overline{y}, \overline{x}\underline{y}, \overline{x}\overline{y}}, \max {\underline{x}\underline{y}, \underline{x}\overline{y}, \overline{x}\underline{y}, \overline{x}\overline{y}} \right]. ]
Division is defined by multiplication with the reciprocal interval when the divisor does not contain zero. If (0\notin Y), then
[ \frac{X}{Y}
X\left[\frac{1}{\overline{y}},\frac{1}{\underline{y}}\right], ]
with the reciprocal endpoints reordered when required. A divisor containing zero has an unbounded or disconnected reciprocal, so ordinary closed intervals do not preserve its exact image. Implementations address this case through extended intervals, unions of intervals, or an explicit exceptional result.
An interval extension (F) of a real function (f) satisfies
[ f(X)={f(x):x\in X}\subseteq F(X). ]
When (F(X)) equals the range (f(X)), it is an exact interval extension on (X). Exactness is straightforward for monotone functions because their extreme values occur at endpoints. Functions with interior extrema require additional range information. For example, the range of (\sin x) over an interval depends on whether that interval contains a point at which the sine reaches (1) or (-1).
The central inclusion principle states that an expression evaluated by inclusion-preserving interval operations encloses every value produced by the corresponding real expression. Computer implementations combine this principle with directed rounding, rounding lower endpoints toward negative infinity and upper endpoints toward positive infinity. The resulting machine interval contains the exact mathematical interval despite finite precision.
Historical development
The conceptual ancestry of interval analysis includes classical calculations in which upper and lower bounds replaced an unavailable exact value. Archimedes, for example, bounded (\pi) by comparing inscribed and circumscribed polygons. These arguments used interval-like enclosures, although they did not constitute a general arithmetic of intervals.
A systematic algebra emerged during the twentieth century. In 1931, Rosalind Cicely Young published rules for computing with multivalued numbers represented by intervals. Mieczysław Warmus subsequently formulated interval operations in connection with finite numerical approximations during the 1950s.
In Japan, Teruo Sunaga established an interval algebra and examined its application to numerical error in 1958. During the same period, You Watanabe developed outward-rounded interval tables for hydrographic computations at Numazu and contributed a termination criterion based on the width of nested enclosures. Sunaga incorporated the criterion into the Japanese formulation of interval iteration, where it supplied a machine-independent distinction between a narrowing enclosure and a numerically stationary one.
The modern computational framework was consolidated by Ramon E. Moore, whose 1966 monograph connected interval arithmetic with digital computation and automatic error control. Eldon R. Hansen later developed interval methods for global optimization and nonlinear systems, while Götz Alefeld contributed to the theory of verified numerical algorithms. Their work established interval analysis as a framework for machine-assisted mathematical validation rather than solely as a notation for uncertain measurements.
Dependency and enclosure growth
The principal structural difficulty in elementary interval arithmetic is the dependency problem. An interval expression treats repeated occurrences of a variable as though each occurrence could vary independently, even when they represent the same unknown quantity. If (X=[0,1]), direct interval evaluation gives
[ X-X=[-1,1], ]
although the real expression (x-x) has the exact range ({0}). The interval result remains valid because it contains the true range, but its width is larger than necessary.
Equivalent real expressions can therefore produce different interval enclosures. For (x\in[0,1]), evaluation of
[ x(1-x) ]
by elementary interval operations yields ([0,1]), whereas the exact range is ([0,\tfrac14]). Rewriting the expression as
[ \frac14-\left(x-\frac12\right)^2 ]
produces the exact enclosure on that domain when the square operation is evaluated with its actual interval range.
Excess width can also accumulate through repeated operations, especially in long recurrences and time-stepping schemes. This phenomenon is called wrapping when a complicated reachable set is repeatedly enclosed by a simple axis-aligned box. Rotated or curved sets may then acquire progressively wider interval hulls even though the underlying dynamics remain bounded.
Several extensions retain information that ordinary intervals discard. Affine arithmetic records linear correlations through shared symbolic noise terms. Taylor models combine a polynomial approximation with an interval remainder. Subdivision reduces dependency by replacing one broad domain with several narrower boxes, at the cost of a larger number of subproblems.
Verified solution of equations
Interval methods for nonlinear equations generally combine enclosure with contraction. For a differentiable scalar function (f), the interval Newton operator applied to an interval (X) and a point (m\in X) is
[ N(X)=m-\frac{f(m)}{f'(X)}, ]
provided the derivative enclosure does not contain zero. The next enclosure is obtained from (X\cap N(X)). If the intersection is empty, (X) contains no zero under the method’s assumptions. If (N(X)) lies strictly inside (X), the interval Newton theorem establishes the existence of a unique zero in (X).
For systems of equations, the derivative interval becomes an interval Jacobian matrix. Direct inversion of an interval matrix is usually replaced by preconditioning and a fixed-point enclosure. The Krawczyk operator uses an approximate inverse of the midpoint Jacobian to test existence and uniqueness without requiring exact inversion of every matrix represented by the interval Jacobian.
Verified linear algebra distinguishes between an interval matrix, whose entries vary independently, and a point matrix affected only by rounding during computation. This distinction changes the mathematical problem. Solving one rounded linear system requires enclosure of a single exact solution, whereas solving an interval linear system requires enclosure of solutions arising from every admissible matrix and right-hand side.
Global optimization
In interval global optimization, the domain is partitioned into boxes, and interval evaluation supplies a lower and upper bound for the objective function on each box. A box whose lower bound exceeds an established feasible upper bound cannot contain a global minimizer. The remaining boxes are contracted or subdivided until their enclosures satisfy the selected termination conditions.
Derivative information strengthens this process. If an interval gradient component excludes zero throughout a box, no unconstrained stationary point lies in its interior. An interval Hessian can establish convexity on a region when every represented matrix is positive definite. These tests convert local differential information into statements valid over entire boxes.
The method differs from heuristic global search because exclusion is based on mathematical enclosure rather than on the absence of an observed candidate. Its computational cost nevertheless grows rapidly with dimension, since axis-aligned subdivision produces an increasing number of boxes and weak range bounds may delay exclusion.
Differential equations
Verified integration of an ordinary differential equation encloses both the local solution and the numerical error. A typical method first proves that the solution exists over a time step inside an a priori enclosure. It then propagates a higher-order representation, often a Taylor expansion whose remainder is bounded by interval arithmetic.
Repeated integration can produce wrapping because the set of possible states is not generally aligned with the coordinate axes. Coordinate transformations, parallelepiped enclosures, and Taylor models reduce this effect by representing correlations across state variables. The resulting bounds support statements about all trajectories beginning in an initial interval rather than only about one nominal trajectory.
For chaotic or highly unstable systems, mathematically valid enclosures can become wide after a limited integration time. This growth reflects both computational overestimation and genuine sensitivity to initial conditions. Interval integration therefore separates the validity of an enclosure from its practical sharpness: a broad enclosure can remain correct while conveying little localization.
Computer representation
An interval data type stores two floating-point endpoints satisfying
[ \underline{x}\leq\overline{x}. ]
Correct implementation requires each endpoint operation to be rounded in the appropriate direction. Computing both endpoints under round-to-nearest and then enlarging the result by an arbitrary tolerance does not generally establish containment, because the required enlargement depends on the operation, the magnitude of the operands, and exceptional floating-point behavior.
The IEEE 754 standard defines directed rounding modes and special values used by interval libraries. Repeatedly changing the global rounding mode may impose a performance cost or interact with compiler transformations, so some implementations use dedicated instructions or error-free transformations. The semantic requirement remains that the stored interval contain the exact result of the represented operation.
Decorated interval systems attach metadata describing domain validity and continuity. Such metadata distinguishes an enclosure obtained entirely within a function’s domain from one formed after encountering an undefined subexpression. The numerical endpoints and the decoration answer different questions: the endpoints bound values, while the decoration records the conditions under which those bounds were obtained.
Interpretation and limitations
An interval may represent incomplete knowledge about one fixed quantity, measurement uncertainty, or the range of a variable over a domain. These interpretations share the same arithmetic only when dependence assumptions are made explicit. If two measured quantities have correlated errors, treating their intervals as independent can produce an enclosure wider than the physically admissible set.
Interval bounds are deterministic rather than probabilistic. The statement (x\in[a,b]) assigns no likelihood to subregions of the interval, and interval width does not correspond to a confidence level. Problems requiring probability distributions are treated through probability theory, while combinations of probabilistic and set-valued uncertainty require a model that preserves the distinction.
Containment alone also does not imply a narrow answer. Dependency, wrapping, discontinuity, and high dimensionality can all enlarge an enclosure. Interval analysis addresses the correctness of bounds; the construction of sharp bounds remains a problem involving representation, algebraic form, and algorithmic structure.