Interval arithmetic
Interval arithmetic is a computational framework that represents real numbers as closed intervals of the form [a, b], where a \leq b, and defines arithmetic operations on these intervals to produce enclosures that contain all possible outcomes of the corresponding operations on the real numbers within the intervals, thereby providing rigorous bounds on computational errors such as rounding and truncation.[1] This approach ensures inclusion isotonicity, meaning the result interval always contains the exact range of the operation, even in finite-precision arithmetic using outward rounding to account for floating-point limitations.[2] For basic operations, addition and subtraction are straightforward—e.g., [a, b] + [c, d] = [a + c, b + d]—while multiplication and division require evaluating endpoint combinations to determine the tightest enclosing interval, with special handling for division by zero yielding the entire real line or appropriate unions.[3] Developed in the mid-20th century to address uncertainties in numerical computations, interval arithmetic traces its modern origins to Teruo Sunaga's 1958 work on inclusion theory, but it was Ramon E. Moore who formalized and popularized it through his 1962 dissertation and 1966 book Interval Analysis, motivated by error bounding needs at Lockheed Missiles and Space Company.[4] Subsequent advancements in the 1960s and 1970s by researchers including Eldon R. Hansen, William Kahan, Karl Nickel, and Ulrich Kulisch refined its theoretical foundations and implementations, leading to standardized hardware support like interval extensions in IEEE 754 and software libraries such as INTLAB and PROFIL/BIAS.[3] Despite its strengths, interval arithmetic suffers from the dependency problem, where expressions lose information about variable correlations (e.g., x - x = [0, 0] but widened intervals may not), resulting in potentially pessimistic bounds that can be mitigated through centered forms or monotonicity exploitation.[1] Interval arithmetic finds broad applications in verified numerical analysis, where it guarantees enclosures for solutions to equations, optimizations, and simulations, enabling computer-assisted proofs such as the 1998 resolution of Kepler's conjecture.[3] In engineering fields like chemical process design, robotics, and structural analysis, it bounds uncertainties from measurements and models to ensure safety and reliability.[4] It also supports solving nonlinear systems via methods like the interval Newton or Krawczyk algorithms, numerical integration with error guarantees, and global optimization by partitioning search spaces into subintervals.[2] These capabilities make it indispensable for high-stakes computations requiring certified accuracy, though challenges like computational overhead persist in real-time systems.[1]Introduction and Basics
Definition and Motivation
Interval arithmetic provides a framework for performing computations with quantities that are known only within certain bounds, representing uncertainty or approximation in numerical values. An interval X is defined as a closed set [a, b] of real numbers where a \leq b, encapsulating the range of all possible values for a given quantity.[2] This representation allows for the propagation of bounds through arithmetic operations, ensuring that results enclose the true range without requiring exact inputs.[1] The primary motivation for interval arithmetic arises from the inherent limitations of floating-point arithmetic, which introduces rounding errors and complicates the tracking of uncertainty in computations. In fields such as scientific computing, engineering design, and formal verification, where precise error bounds are essential, traditional methods often fail to guarantee containment of all possible outcomes due to accumulated inaccuracies.[5] Interval arithmetic addresses this by systematically bounding errors and uncertainties, enabling reliable analysis even with approximate data.[1] The set of all closed real intervals forms a lattice under the partial order of inclusion, where the meet and join operations correspond to intersection and convex hull, respectively. Arithmetic operations on intervals are defined to yield enclosures—intervals that contain the union of all possible results from applying the operation to values within the input intervals—thus preserving the inclusion property.[5] A key measure is the width of an interval X = [a, b], given by w(X) = b - a, which quantifies the uncertainty or spread represented by the interval.[1] Interval arithmetic originated in the mid-20th century to meet the growing needs of error analysis in digital computing, with foundational developments by R. E. Moore in his 1962 dissertation.[6]Illustrative Examples
To illustrate the basic principle of interval arithmetic, consider the addition of two intervals representing approximate values with known bounds. Suppose the value of π is known to lie within the interval [3.14, 3.15], and an additional correction term is bounded by [0.001, 0.002]. The sum of these intervals is computed as [3.14 + 0.001, 3.15 + 0.002] = [3.141, 3.152]. This result encloses all possible sums of values from the original intervals, providing a guaranteed bound on the uncertainty without requiring exact inputs. Interval arithmetic extends naturally to more complex formulas by propagating bounds through multiple operations. For example, the area of a circle is given by A = \pi r^2, where the radius r is uncertain and lies in the interval [r_1, r_2] with r_1 < r_2. Applying interval arithmetic yields the interval extension \pi [r_1, r_2]^2 = [\pi r_1^2, \pi r_2^2], which contains the true area for any r \in [r_1, r_2]. This demonstrates how uncertainties in input parameters are tracked to bound the output, useful in applications like engineering tolerances. In contrast to point arithmetic, which uses single representative values and may accumulate untracked rounding errors, interval arithmetic produces wider results that rigorously enclose the true value. For instance, point evaluation of the earlier addition using midpoints 3.145 + 0.0015 = 3.1465 might suggest false precision, whereas the interval [3.141, 3.152] ensures containment but reflects the actual uncertainty range. This enclosure property makes interval methods reliable for verified computations, though at the cost of broader bounds due to the dependency problem in repeated uses of the same variable. Visual representations, such as diagrams depicting the overlap of input intervals and the union of their Minkowski sum for addition, or the monotonic expansion of the area interval with increasing radius bounds, can aid understanding of these enclosures.Interval Representation
Standard Notation
In interval arithmetic, an interval X over the real numbers is typically denoted by X = [\underline{x}, \overline{x}], where \underline{x} and \overline{x} represent the lower and upper bounds, respectively, satisfying \underline{x} \leq \overline{x}.[3] This closed notation encompasses all real numbers x such that \underline{x} \leq x \leq \overline{x}, providing a compact representation for sets of possible values in computations involving uncertainty or error bounds.[3] Special cases include degenerate intervals, which are singletons of the form [a, a] equivalent to the real number a itself, representing precise values without width.[3] The empty set is denoted by \emptyset, arising when no real numbers satisfy the interval condition, such as in inconsistent bounds where the lower exceeds the upper.[3] Unbounded intervals, such as [-\infty, b] or [a, \infty), are occasionally considered but rarely emphasized in standard treatments, as the focus remains on finite, closed intervals.[3] These notations assume familiarity with basic properties of the real numbers, including ordering and completeness.[3] The set of all such intervals forms a complete lattice under the partial order of inclusion \subseteq, where X \subseteq Y if and only if \underline{y} \leq \underline{x} and \overline{x} \leq \overline{y}.[3] In this structure, the meet operation corresponds to the intersection X \cap Y, and the join is the convex hull (or interval hull) of the union, ensuring the smallest interval containing both sets.[3] For a finite set of real numbers \{x_1, \dots, x_n\}, the convex hull is given by \operatorname{conv}(\{x_1, \dots, x_n\}) = [\min\{x_1, \dots, x_n\}, \max\{x_1, \dots, x_n\}], which extends naturally to intervals as subsets of the power set of the reals.[3] This lattice framework underpins the algebraic properties essential for rigorous error analysis in numerical computations.[3]Real and Complex Intervals
In interval arithmetic, complex intervals extend the real interval concept to the complex plane, primarily through rectangular representations. A rectangular complex interval Z is defined as the Cartesian product of two real intervals, expressed as Z = [a, b] + i [c, d], where [a, b] and [c, d] are closed real intervals, and i is the imaginary unit. This form encloses all complex numbers z = x + i y such that x \in [a, b] and y \in [c, d], forming an axis-aligned rectangle in the complex plane. Such representations are straightforward to compute using real interval arithmetic on the real and imaginary components separately. Alternative representations for complex intervals include disk or circular forms, which enclose sets as disks centered at a complex point with a radius given by a nonnegative real interval. A circular complex interval can be denoted as Z = z_c + r \mathbb{D}, where z_c is a complex center, r is a real interval radius, and \mathbb{D} is the closed unit disk \{ w \in \mathbb{C} : |w| \leq 1 \}. These forms often provide tighter enclosures for operations involving magnitude or rotation, such as multiplication, but may overestimate for addition or subtraction compared to rectangular forms, leading to trade-offs in enclosure tightness depending on the application.[7] Interval arithmetic extends naturally to higher dimensions via vector and matrix intervals. An interval vector in \mathbb{R}^n is the Cartesian product \mathbf{X} = [a_1, b_1] \times \cdots \times [a_n, b_n], bounding component-wise ranges for vectors. Similarly, an interval matrix consists of entries that are real or complex intervals, enabling enclosures for linear systems and transformations in multi-dimensional spaces. The operations on real, complex, vector, and matrix intervals inherit key properties from real interval arithmetic, including inclusion monotonicity and subdistributivity. Inclusion monotonicity ensures that if X \subseteq Y and Z \subseteq W, then the result of any operation satisfies X \oplus Z \subseteq Y \oplus W, where \oplus denotes addition, subtraction, multiplication, or division (when defined). Subdistributivity holds for multiplication, such that X(Y + Z) \subseteq XY + XZ, though equality does not always obtain due to dependency issues. These properties guarantee that computed enclosures contain all possible values from input uncertainties. For complex addition in rectangular form, the operation proceeds component-wise: given Z_1 = [a_1, b_1] + i [c_1, d_1] and Z_2 = [a_2, b_2] + i [c_2, d_2], Z_1 + Z_2 = [a_1 + a_2, b_1 + b_2] + i [c_1 + c_2, d_1 + d_2]. This preserves the rectangular structure exactly. Unlike real intervals, which have unique closed bounded representations, complex intervals exhibit non-unique enclosures due to the two-dimensional nature and multiple representational choices (e.g., rectangular versus disk), potentially leading to different bounding sets for the same points. Tighter enclosures can often be achieved using alternative forms like polar or disk representations, which better capture rotational symmetries or circular uncertainties in complex computations.[7]Core Operations
Arithmetic Operators
Interval arithmetic defines the basic operations on closed real intervals to ensure that the result contains all possible values arising from pointwise applications of the corresponding real operations on the endpoints. For two intervals X = [\underline{x}, \overline{x}] and Y = [\underline{y}, \overline{y}], where \underline{x} \leq \overline{x} and \underline{y} \leq \overline{y}, the operations are specified as follows.[3] Addition is given by X + Y = [\underline{x} + \underline{y}, \overline{x} + \overline{y}], which directly sums the lower and upper bounds, preserving the inclusion property.[3] Subtraction follows as X - Y = [\underline{x} - \overline{y}, \overline{x} - \underline{y}], subtracting the upper bound of Y from the lower bound of X and the lower bound of Y from the upper bound of X to account for the range of possible differences.[3] Multiplication requires evaluating all combinations of endpoint products and selecting the minimum and maximum: X \cdot Y = [\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}\}], ensuring the result encloses the full range of products.[3] Division is defined as X / Y = X \cdot (1/Y), where the reciprocal interval is \frac{1}{Y} = \left[\frac{1}{\overline{y}}, \frac{1}{\underline{y}}\right] provided $0 \notin Y (i.e., \underline{y} > 0 or \overline{y} < 0); if $0 \in Y, the operation is undefined in standard real interval arithmetic or requires extended intervals incorporating infinity.[3] These operations exhibit inclusion monotonicity: if X \subseteq X' and Y \subseteq Y', then X + Y \subseteq X' + Y', and similarly for subtraction, multiplication (when applicable), and division.[3] Additionally, multiplication satisfies subdistributivity: for intervals X, Y, and Z, X(Y + Z) \subseteq XY + XZ, meaning the interval obtained by multiplying X by the sum Y + Z contains the pointwise range but is contained within the sum of the separate products, potentially leading to tighter bounds in some cases.[3]Elementary Functions
In interval arithmetic, the extension of a continuous unary function f: \mathbb{R} \to \mathbb{R} to an interval X = [\underline{x}, \overline{x}] is defined as the range f(X) = \bigcup \{f(x) \mid x \in X\} = [\inf f(X), \sup f(X)], which provides a tight enclosure of all possible function values over X.[8] This range can be computed exactly for simple cases but often requires approximation methods to ensure inclusion. For monotonic functions, the range simplifies to evaluation at the endpoints: if f is increasing, f(X) = [f(\underline{x}), f(\overline{x})]; if decreasing, f(X) = [f(\overline{x}), f(\underline{x})]. Non-monotonic functions demand more sophisticated techniques, such as subdivision of X into monotonic subintervals or bounding via derivatives (e.g., using the mean value theorem to estimate deviations from a point).[9] The exponential function \exp(X) is monotonic increasing, so its interval extension is straightforward: \exp(X) = [\exp(\underline{x}), \exp(\overline{x})]. For example, \exp([0, 1]) = [1, e], where e \approx 2.718, enclosing all values from \exp(0) to \exp(1).[10] Similarly, the natural logarithm \log(X) is monotonic increasing on X > 0, yielding \log(X) = [\log(\underline{x}), \log(\overline{x})] for \underline{x} > 0; for instance, \log([2.5, 3.5]) \approx [0.916, 1.253] when using endpoint evaluations with rounding adjustments.[11] The square root function, defined for X \geq 0, is also monotonic increasing: \sqrt{X} = [\sqrt{\underline{x}}, \sqrt{\overline{x}}]. An example is \sqrt{[0, 4]} = [0, 2], which precisely bounds the range.[10] For non-monotonic functions like sine, the range cannot rely solely on endpoints and may require subdivision or auxiliary bounds. For \sin(X), the exact range is determined by the minimum and maximum values over X, considering the function's periodicity and critical points (e.g., at \pi/2 + 2k\pi). For example, \sin([0, \pi]) = [0, 1], obtained by evaluating extrema within the interval; more complex intervals like \sin([0.1, 0.3]) use endpoint evaluations since sine is monotonic increasing there, yielding enclosures such as \approx [0.0998, 0.2955].[8][9] The power function X^n for integer n handles cases based on the sign of the base and parity of n. If X \geq 0, it follows monotonicity: for even n, X^n = [0, \max(\underline{x}^n, \overline{x}^n)]; for odd n, endpoint evaluation applies directly. When X includes negative values, even powers yield non-negative results via the convex hull of positive and absolute values, e.g., [-2, -1]^2 = [1, 4]; odd powers preserve sign, e.g., [-2, -1]^3 = [-8, -1]. For X = [-2, 3] and even n=4, X^4 = [0, 81], accounting for the minimum at zero and maximum at the farthest endpoint.[8][12] A key property of these extensions is inclusion isotonicity: for continuous f and nested intervals X \subseteq Y, the extended function satisfies f(X) \subseteq f(Y), ensuring wider inputs produce wider (or equal) output enclosures. This holds because the range union preserves subset relations for continuous functions. Compositions with arithmetic operations from prior sections can form more complex expressions while maintaining inclusion.[8]Extensions to General Functions
Interval arithmetic extends to general functions through the principle of interval extension, which requires constructing an interval-valued function F such that f(x) \in F(X) for all x \in X, where X is an interval containing the domain points of interest. This ensures that the image of any point in X under f lies within the computed interval enclosure, providing guaranteed bounds despite the loss of exact point information. The extension F is typically derived from properties of f, such as differentiability, to minimize overestimation inherent in naive pointwise evaluations. A fundamental approach is the mean value form, which leverages the mean value theorem for differentiable functions. For a differentiable function f on an interval X, the mean value extension is given by f(X) = f(c) + f'(X)(X - c), where c \in X is a chosen point (often the midpoint m(X)) and f'(X) is an interval enclosure of the derivative f' over X. This form guarantees enclosure because, by the mean value theorem, f(y) - f(c) = f'(\xi)(y - c) for some \xi between y and c, so the difference lies in f'(X)(X - c). The mean value form is particularly effective for Lipschitz continuous functions, where the derivative is bounded, allowing tighter enclosures compared to natural extensions.[13] The Lipschitz form provides a coarser but simpler enclosure for functions satisfying a Lipschitz condition, i.e., |f(x) - f(y)| \leq L |x - y| for some constant L > 0 and all x, y \in X. In this case, the extension simplifies to f(X) \subseteq f(c) + L (X - c), where L bounds the absolute value of f' over X, ensuring the width of the enclosure is at most L times the width of X. This form is useful when computing the full range of f' is expensive, as it relies only on a scalar bound rather than an interval for the derivative. For higher accuracy, the Taylor form extends the mean value approach using higher-order derivatives. For an n-times differentiable function f, the Taylor expansion around c \in X is f(X) \approx \sum_{k=0}^{n} \frac{f^{(k)}(c)}{k!} (X - c)^k + R_n(X), where the remainder term R_n(X) encloses the Lagrange form \frac{f^{(n+1)}(\xi)}{(n+1)!} (X - c)^{n+1} for some \xi \in X, typically bounded by an interval extension of f^{(n+1)} over X. This provides a polynomial approximation plus a verified remainder, reducing overestimation for smooth functions by incorporating curvature information. The full Taylor form inclusion is thus f(X) = \sum_{k=0}^{n-1} \frac{f^{(k)}(c)}{k!} (X - c)^k + f^{(n)}(X) \frac{(X - c)^n}{n!}, ensuring enclosure via the generalized mean value theorem for higher derivatives.[13] These extensions are applied to differentiable functions to obtain narrower enclosures than those from arithmetic operations alone, especially when dependencies between variables are present or for non-elementary functions lacking explicit interval rules. The choice depends on available derivative information: mean value or Lipschitz for first-order, Taylor for higher-order precision, with computational cost increasing with the order of differentiation.[13]Computational Techniques
Rounded Interval Arithmetic
Rounded interval arithmetic extends standard interval arithmetic by incorporating directed rounding to account for finite-precision computations on digital computers, ensuring that the resulting intervals rigorously enclose the exact mathematical ranges despite rounding errors. This technique, also known as outward rounding, rounds the lower endpoint of an interval downward and the upper endpoint upward, guaranteeing inclusion of the true interval.[3] Rounding modes in rounded interval arithmetic utilize directed rounding provided by floating-point hardware standards, such as rounding downward (to the nearest representable number not exceeding the exact value) for lower bounds and upward (to the nearest representable number not less than the exact value) for upper bounds. These modes leverage the processor's ability to switch rounding directions on a per-operation basis, enabling precise control over enclosure accuracy.[14] The error introduced by rounding is bounded by the machine epsilon \varepsilon, the smallest relative spacing between floating-point numbers around 1, typically $2^{-52} for double precision. For a computed interval \hat{X} enclosing the exact interval X, outward rounding ensures X \subseteq \hat{X} with the width satisfying w(\hat{X}) \leq w(X) + 2\varepsilon \max(| \underline{x} |, | \overline{x} |), where \underline{x} and \overline{x} are the endpoints, limiting the excess width to at most two units in the last place (ulp) per bound.[3] Implementation relies on floating-point units supporting directed rounding, often integrated into processors like those compliant with IEEE 754, where lower and upper bounds are computed in parallel using dedicated rounding instructions. Software libraries, such as INTLAB, automate this process by enforcing outward rounding for all operations, minimizing overhead while preserving enclosure properties.[14][3] For basic operations like addition of intervals X = [\underline{x}, \overline{x}] and Y = [\underline{y}, \overline{y}], the rounded result is computed as: \hat{X} + \hat{Y} = \left[ \mathrm{fl}_\downarrow(\underline{x} + \underline{y}), \mathrm{fl}_\uparrow(\overline{x} + \overline{y}) \right], where \mathrm{fl}_\downarrow denotes downward rounding and \mathrm{fl}_\uparrow denotes upward rounding to the nearest floating-point number. This ensures the exact sum range is contained within the computed interval.[14] The importance of rounded interval arithmetic lies in its foundation for validated numerics, where it guarantees that computed enclosures contain all possible solutions, enabling reliable error analysis and computer-assisted proofs in scientific and engineering applications. By bounding rounding errors explicitly, it supports the development of trustworthy computational methods without underestimation risks.[15][3]Handling Dependencies
In interval arithmetic, the dependency problem arises when a function involves the same variable multiple times, but the arithmetic treats each occurrence as independent, leading to enclosures that are wider than necessary. For instance, consider the function f(x) = x - x, which evaluates exactly to 0 for any real x. If x is represented by the interval X = [a, b] with a < b, standard interval arithmetic computes f(X) = X - X = [a - b, b - a], an interval of width $2(b - a) that contains 0 but overestimates the true range \{0\}.[3] This overestimation stems from the fundamental design of interval operators, which compute bounds assuming no correlation between input intervals, thereby discarding information about dependencies between variables. In expressions where variables appear repeatedly, such as in subtraction or multiplication, the subadditivity and submultiplicativity properties of interval arithmetic ensure containment but fail to exploit the fact that correlated occurrences (e.g., the same x in x - x) constrain the result more tightly. The dependency effect is particularly evident in basic operations like subtraction: for an interval X, the width w(X - X) = 2w(X), whereas the true width of the range is 0, highlighting how multiple uses amplify uncertainty without reflecting actual functional behavior.[3] To address dependencies, alternative representations such as affine forms and centered forms have been developed, which track linear correlations or mean-value expansions to produce narrower enclosures while maintaining guaranteed bounds. Affine forms represent quantities as affine combinations of noise symbols to model dependencies explicitly, while centered forms evaluate functions around a midpoint to reduce wrapping effects from repeated variables. These approaches mitigate but do not fully eliminate the issue in nonlinear or higher-order contexts.[16][17]Widening and Overestimation
In interval arithmetic, overestimation occurs when the computed enclosure of a function's range over an input interval is wider than the true range, leading to a loss of sharpness in bounds. This widening is distinct from but can compound the dependency effects handled through variable correlation techniques. The excess width, defined as e(X) = w(F(X)) - w(f(X)), where F(X) is the interval extension and w(\cdot) denotes the width, measures the degree of overestimation for a given evaluation.[18] A fundamental metric for quantifying overestimation is the Hausdorff distance d_H(R(f; X), F(X)), which captures the maximum deviation between the true range R(f; X) and the enclosure F(X). For continuous functions, this distance converges linearly to zero as the width w(X) shrinks, with d_H \leq \gamma w(X) for some constant \gamma depending on the function's properties over a reference interval.[18] The wrapping effect represents a key source of overestimation, arising when the geometric shape of the function's image—often curved or non-axis-aligned in multiple dimensions—is projected onto an interval vector, inflating the enclosure to include unnecessary regions. For instance, the evaluation \sin([0, 2\pi]) = [-1, 1] is exact, but for a nonlinear mapping like f(x, y) = (x^2 - y^2, 2xy) over a square domain, the circular image wraps into a larger bounding box, exaggerating the width beyond the true range. This effect intensifies with dimensionality and curvature, as interval arithmetic assumes independent variation along each axis.[19] Beyond dependency issues, overestimation stems from function non-monotonicity, where interior extrema fragment the range into disconnected components that interval evaluations merge conservatively, and from multiple variable occurrences amplifying artificial correlations not captured in basic forms. These factors contribute to quadratic or higher-order excess width in higher-degree polynomials.[18] Overestimation can be bounded using the function's Lipschitz constant L, which satisfies w(f(X)) \leq L \, w(X) for the true range width, with interval extensions achieving w(F(X)) \leq (1 + \kappa) L \, w(X), where \kappa is a condition number reflecting derivative variation (e.g., \kappa = \sup |f'| / \inf |f'| - 1). This slope-based bound highlights how steep or varying gradients exacerbate widening, as in the mean-value form F(X) = f(c) + f'(X)(X - c), yielding w(F(X)) \leq \sup |f'| \cdot w(X).[1] To minimize the wrapping effect, subdivision techniques partition the input interval into smaller subdomains, where local linearity or alignment reduces geometric distortion in enclosures. While computationally intensive, this yields tighter overall bounds by unioning refined sub-enclosures, often achieving near-optimal sharpness for moderately complex functions.[20]Solution Methods
Linear Interval Systems
Linear interval systems concern the computation of enclosures for the solution set of equations A \mathbf{x} = \mathbf{b}, where A is an n \times n interval matrix and \mathbf{b} is an interval vector. The solution set is defined as S = \{ \mathbf{x} \in \mathbb{R}^n \mid \exists A \in A, \, b \in B \text{ s.t. } A \mathbf{x} = b \}, representing all possible solutions over the ranges of coefficients in A and B. This set is typically non-convex and computing its exact hull is NP-hard, so methods focus on outer approximations using interval arithmetic. Interval matrix arithmetic, which extends pointwise operations to matrices while accounting for dependencies, underpins these computations.[21] A fundamental technique for enclosing S is the interval adaptation of Gaussian elimination, which transforms the augmented interval matrix [A \mid B] into row echelon form via elementary row operations compatible with interval arithmetic. To mitigate excessive width growth from dependency ignorance and potential division by zero-containing pivots, partial pivoting selects the candidate pivot interval with the minimal width in the current column, thereby minimizing overestimation in subsequent elimination steps. Pivot tightening can further refine this by computing exact ranges for pivots using determinants of leading principal submatrices, ensuring nonsingularity for classes like inverse nonnegative matrices. The resulting upper triangular system is then solved via back-substitution, yielding a verified enclosure, though widths may still expand quadratically in the worst case.[22] The Hansen-Bliek method offers a preconditioning-based approach to achieve sharper enclosures. It first computes a preconditioner M \approx (\mathrm{mid}(A))^{-1}, the inverse of the midpoint matrix of A, and applies it to form the transformed system M A \mathbf{x} = M B. Assuming the preconditioned matrix M A is regular, the method then uses iterative refinement—often intersecting enclosures from the Hansen hull procedure and linear programming relaxations—to compute the tight interval hull of solutions. This yields an enclosure X satisfying X \subseteq A^{-1} B, with optimality in the sense of minimal width for certain inverse-positive systems. The approach reduces dependency effects but may introduce slight overestimation if M is inexact.[23] A important property concerns unique solvability, where S reduces to a singleton. The system has a unique solution if \mathrm{mid}(A) is nonsingular and \rho( |\mathrm{mid}(A)|^{-1} \mathrm{rad}(A) ) < 1, with \rho denoting the spectral radius, |\cdot| the entrywise absolute value, and \mathrm{rad}(A) the radius matrix (half-widths); this ensures all realizations of A and point B yield the same \mathbf{x} = \mathrm{mid}(A)^{-1} \mathrm{mid}(B). For general interval B, analogous bounds apply using the radius of B. Such conditions guarantee the absence of width propagation in the solution enclosure.[24]Interval Newton Method
The interval Newton method extends the classical Newton-Raphson iteration to interval arithmetic, providing a means to rigorously enclose the zeros of nonlinear functions f: \mathbb{R}^n \to \mathbb{R}^n within an initial interval vector X^0. For a differentiable function f, the interval Newton operator is defined as N(X) = \{ x - f'(X)^{-1} f(x) \mid x \in X \}, where f'(X) is an invertible interval extension of the Jacobian over X, ensuring that if a zero x^* \in X exists, then x^* \in N(X). In practice, this set-valued operator is often computed using the midpoint m(X) of X for efficiency, yielding N(X) = m(X) - f'(X)^{-1} f(m(X)), and the iteration proceeds as X^{k+1} = X^k \cap N(X^k). This approach guarantees that all zeros in the initial box remain enclosed throughout the process, with the method terminating when X^k is sufficiently narrow or empty (indicating no zeros). Under suitable conditions, such as f' satisfying a Lipschitz condition on X (i.e., \|f'(x_1) - f'(x_2)\| \leq L \|x_1 - x_2\| for some L > 0), the interval Newton method exhibits quadratic convergence, meaning the width w(X^{k+1}) satisfies w(X^{k+1}) \leq C [w(X^k)]^2 for some constant C > 0 once the iteration enters a neighborhood of the zero. A key convergence criterion is that the width reduces contractively: if w(N(X)) < \beta w(X) with $0 \leq \beta < 1, then the sequence of intervals nests and converges to the unique zero in X, provided $0 \notin f'(X). This ensures linear or superlinear width reduction per iteration, contrasting with the potentially slower linear convergence of simpler interval methods. A prominent variant is the Krawczyk method, which modifies the interval Newton operator to improve reliability and enclosure tightness: K(X) = x - f'(x)^{-1} f(x) + [I - f'(X)^{-1} f'(x)] (X - x) for some x \in X, where f'(x) is evaluated at the point x. If K(X) \subseteq \operatorname{int}(X), then X contains exactly one zero of f, and the method converges quadratically under the same Lipschitz assumptions on f'. This preconditioned form often requires fewer iterations than the basic interval Newton, especially for ill-conditioned problems, while maintaining guaranteed enclosures.[25] In applications, the interval Newton method is primarily used to enclose roots of nonlinear equations, such as in solving f(x) = 0 where point estimates from classical Newton may miss multiple or ill-behaved solutions due to rounding errors or dependencies. Unlike the point-based classical Newton method, which converges quadratically to a single approximation without enclosure guarantees, the interval version provides validated bounds on all solutions in the domain, making it essential for verified computing in fields like optimization and control systems. For linear systems, it reduces to a special case of interval Gaussian elimination, but its strength lies in handling nonlinearity iteratively.Bisection and Covering
Bisection methods in interval arithmetic provide a reliable means to enclose the roots of nonlinear equations or functions within specified regions by systematically refining enclosures through subdivision. The process begins with an initial interval or box X over which the function f is evaluated using interval arithmetic to compute the range f(X). Subintervals are discarded if f(X_i) \not\ni 0, indicating no root is present, while promising subintervals are further bisected, typically by halving along the longest dimension to maintain balanced refinement. This adaptive strategy prioritizes dimensions with the greatest width, reducing the overall enclosure more efficiently than uniform subdivision across all dimensions.[26] Algorithms for bisection vary in their splitting criteria: uniform bisection divides the enclosure equally in all directions, suitable for symmetric problems but potentially inefficient for elongated domains, whereas adaptive bisection selects the direction of maximum width w(X) = \max(b_j - a_j) for each split, where [a_j, b_j] are the bounds in coordinate j. This is implemented in packages like INTBIS, which combines bisection with root existence tests to isolate all solutions within a bounded region. Termination occurs when the width of all remaining subintervals satisfies w(X_i) < \epsilon for a user-specified tolerance \epsilon, or after a fixed number of iterations to bound computational effort.[26] The trade-offs in bisection involve balancing computational cost against enclosure tightness; while adaptive methods converge faster in practice for most nonlinear systems, they require more evaluations of the inclusion function, making them up to 200 times slower than point-based methods but guaranteed to find all roots without missing any.[26] Overestimation from interval arithmetic, which can inflate ranges due to dependency issues, motivates finer bisections to achieve tighter bounds. Covering techniques extend interval arithmetic to represent non-convex or disconnected sets that cannot be enclosed by a single interval or box, approximating them as unions of multiple intervals or boxes (often termed pavings or subpavings). For a non-convex set S, the covering C = \bigcup C_i satisfies S \subseteq C, where each C_i is a box computed via subdivision and validated using interval evaluations to ensure containment.[27] This is particularly useful in global optimization or viability analysis, where the feasible region may consist of disjoint components, and boxes are retained only if they intersect S based on tests like f(C_i) \ni 0. Algorithms for covering often integrate bisection by recursively partitioning the initial domain and selecting sub-boxes that cover viable portions, discarding inconsistent ones to minimize excess volume.[28] For instance, in set inversion problems, the union of surviving boxes forms an outer approximation, with inner approximations obtained by further refining to exclude boundary uncertainties.[27] Termination mirrors bisection, halting when the maximum box width falls below \epsilon or the covering achieves a desired volume ratio relative to the original domain. Trade-offs in covering methods include increased storage for the list of boxes, which grows with the complexity of the non-convex set, versus improved fidelity over single-box enclosures that suffer from excessive overestimation.[28] These approaches ensure rigorous guarantees for non-convex domains, though at higher computational expense, as demonstrated in applications like robust control where unions of boxes enclose basins of attraction.[27]Applications
Rounding Error Analysis
Interval arithmetic provides a rigorous framework for verifying and bounding rounding errors in floating-point computations by representing values as intervals that enclose all possible results due to roundoff. In this approach, arithmetic operations are performed with outward rounding, ensuring that the computed interval contains the exact mathematical result despite finite precision limitations. This method systematically tracks the propagation of uncertainties introduced by rounding at each step, offering guaranteed enclosures rather than probabilistic estimates.[29] A key application is backward error analysis, where the computed floating-point result \mathrm{fl}(f(x)) is interpreted as the exact evaluation of the function on a perturbed input, f(x + \delta x), with the perturbation \delta x bounded by an interval derived from the rounding errors. For instance, in floating-point arithmetic, each operation satisfies \mathrm{fl}(x \oplus y) = (x \oplus y) (1 + \delta) where |\delta| \leq u (machine epsilon), and interval arithmetic extends this to enclose \delta x within an interval such as [-u \cdot |x|, u \cdot |x|], providing a tight bound on the backward error. This allows assessment of an algorithm's stability by checking if small input perturbations lead to acceptable output changes, with widening intervals signaling potential instability.[30][29] Forward error propagation complements this by enclosing the accumulation of all possible rounding errors throughout a computation, often modeled as a directed graph of operations where intervals flow from inputs to outputs. For example, in computing the sum s = \sum_{i=1}^n x_i, the interval enclosure [\underline{s}, \overline{s}] includes the true sum plus an error term bounded by an interval representing cumulative roundoff, such as [s - e, s + e] where |e| \leq (n-1) u \max |x_i| for naive summation, revealing order-dependent error growth in alternating series like \sum (-1)^i / i. The relative error bound for a basic operation is given by |\mathrm{fl}(\mathrm{op}(x,y)) - \mathrm{op}(x,y)| \leq \varepsilon \cdot |\mathrm{op}(x,y)|, enclosed within an interval [-\varepsilon \cdot |\mathrm{op}(x,y)|, \varepsilon \cdot |\mathrm{op}(x,y)|] with \varepsilon typically the unit roundoff, ensuring the interval captures all feasible outcomes.[29][30] Compared to classical a posteriori error bounds, which require manual derivation and often yield loose estimates for nonlinear or complex codes, interval arithmetic automates the process and produces tighter enclosures, particularly for programs with dependencies or branches, by inherently accounting for worst-case roundoff without additional analysis. This makes it especially valuable for verifying numerical software reliability, as demonstrated in detecting summation instabilities where classical methods might overlook subtle accumulations.[29][31]Tolerance and Design Analysis
Interval arithmetic plays a crucial role in tolerance and design analysis by providing a rigorous framework for propagating uncertainties arising from manufacturing tolerances in engineering systems. In this context, dimensional variables are represented as intervals to capture nominal values along with their allowable deviations, enabling designers to compute guaranteed bounds on assembly performance without relying on probabilistic assumptions. This approach is particularly valuable in mechanical and electrical engineering, where component variations can accumulate and affect fit, function, or reliability.[32] Tolerance stack-up refers to the propagation of these interval uncertainties through sums, products, or other operations on dimensional variables. For instance, the total length of an assembly formed by two components with lengths l_1 \pm t_1 and l_2 \pm t_2 is computed as the interval sum [l_1 + l_2 - (t_1 + t_2), l_1 + l_2 + (t_1 + t_2)], yielding the worst-case range of possible outcomes. Similar interval operations apply to products or more complex geometric functions, ensuring that the enclosure of all feasible values is obtained deterministically. This method contrasts with statistical techniques like root-sum-square (RSS), which assume normal distributions and provide probabilistic estimates; interval arithmetic delivers conservative, guaranteed bounds suitable for safety-critical designs where overestimation is preferable to underestimation.[32][33] A key tool in this analysis is sensitivity propagation, which quantifies how tolerances in inputs affect the output through the first-order approximation: w(f(X_1, \dots, X_n)) \leq \sum_{i=1}^n \left| \frac{\partial f}{\partial x_i} \right| w(X_i) Here, w(\cdot) denotes the width of an interval, f is the design function (e.g., clearance or stress), and the partial derivatives represent sensitivities at nominal points. This inequality provides an upper bound on the total tolerance, facilitating optimization of component specifications to minimize variation while respecting constraints.[34] In mechanical assemblies, interval arithmetic is applied to evaluate fit tolerances, such as gap or interference in mating parts. Consider a piston-cylinder assembly where the gap g = d_c - d_p (cylinder diameter minus piston diameter) has tolerances leading to an interval gap [g_{\min}, g_{\max}]; if d_c \in [50, 50.1] mm and d_p \in [49.8, 49.9] mm, then g \in [0.1, 0.3] mm, ensuring no binding occurs across the tolerance zone. Modal interval extensions handle geometric deviations (e.g., form tolerances) by incorporating small degrees of freedom, providing tighter bounds than classical intervals for multidimensional effects. This deterministic analysis outperforms RSS in cases with non-normal distributions or unknown statistics, as demonstrated in tolerance charting for stack-up chains.[32][33] Interval-based tolerance analysis is often integrated into computer-aided design (CAD) software, where tools like tolerance zones and geometric dimensioning and tolerancing (GD&T) standards facilitate automated propagation. Libraries such as those implementing modal intervals allow seamless embedding in design workflows, supporting iterative optimization of tolerances to balance manufacturability and performance.[32]Computer-Assisted Proofs
Interval arithmetic facilitates computer-assisted proofs by delivering rigorous enclosures for solutions to equations and inequalities, thereby certifying the validity of mathematical theorems through verified numerical computations. These methods bound rounding errors and discretization uncertainties, ensuring that computed intervals contain all possible exact values, which is essential for proving existence, uniqueness, or nonexistence of solutions in complex systems.[35] In verified computations, interval arithmetic encloses zeros of nonlinear functions or definite integrals with guaranteed error bounds, transforming approximate numerical results into provable statements. For instance, the image of an interval domain under a function can be rigorously enclosed to confirm that no root lies within it, or to bound integral values such as \int_0^{1} e^x \, dx \in [1.71828, 1.718282], which contains the exact value e - 1 \approx 1.718281828. This approach underpins the certification of properties like fixed points or equilibria in partial differential equations.[35] A prominent application appears in the proof of the Kepler conjecture, where interval arithmetic verified hundreds of nonlinear inequalities in geometric optimization problems, establishing that the face-centered cubic packing achieves the maximum density for equal spheres in three dimensions. By computing lower bounds on functions like the energy E over interval domains, the method confirmed that no denser configuration exists, with each inequality checked via outward rounding to handle floating-point errors.[36] In dynamical systems, interval methods have rigorously verified chaotic behavior, such as the existence of transversal homoclinic points in discrete maps, which imply symbolic dynamics and sensitive dependence on initial conditions. For example, enclosures of orbits in the Henon map confirmed chaos by isolating invariant sets containing dense orbits, a feat requiring global coverage of phase space that manual analysis could not achieve.[37] To establish globality, domain covering techniques partition the search space into subintervals, applying local verifiers exhaustively to ensure complete analysis without gaps. Uniqueness is often certified using interval adaptations of the Kantorovich theorem, which provide existence and isolation balls around approximate solutions by bounding the Lipschitz constant and residual via interval derivatives.[35] A fundamental exclusion test in these proofs, particularly within the interval Newton method, states that if $0 \notin N(X) and w(N(X)) < w(X)—where X is an interval vector, N(X) is the interval Newton image, and w(\cdot) denotes width—then X contains no zero of the system. This criterion discards subdomains without solutions, accelerating branch-and-bound searches while maintaining rigor.[1] The impact of these techniques is profound, enabling proofs in analysis and geometry that surpass human computational limits, such as certifying stability in the Muskat problem or global regularity in the surface quasi-geostrophic equation, where traditional methods fail due to high dimensionality. Recent advances as of 2025 include computer-assisted proofs for monodromy in Picard-Fuchs equations and uniqueness in slowly oscillating solutions to differential equations, leveraging interval methods for rigorous bounds.[36][35][38][39]Uncertain and Fuzzy Reasoning
Fuzzy intervals extend the concept of interval arithmetic to handle gradual uncertainties through fuzzy set theory, where membership functions assign degrees of belonging to elements rather than binary inclusion. A fuzzy interval is defined by a membership function μ_X(x) that maps real numbers to [0,1], representing the degree to which x belongs to the fuzzy set X. Unlike crisp intervals with hard bounds, fuzzy intervals allow for smooth transitions in membership, enabling the modeling of linguistic variables such as "approximately 5" or "around 10 to 20."[40] The α-cut of a fuzzy interval X, denoted [X]^α, is the crisp interval {x | μ_X(x) ≥ α} for α ∈ (0,1], forming a family of nested intervals that fully represent the fuzzy set. This decomposition theorem allows fuzzy arithmetic to leverage interval operations: for a function f, the α-cut of the result is [f(X)]^α = f([X]^α), where f is applied using standard interval arithmetic. This approach ensures the fuzzy output membership is reconstructed from the union of these α-cuts.[41] Operations on fuzzy intervals follow Zadeh's extension principle, which generalizes crisp functions to fuzzy arguments by maximizing membership over preimages: for fuzzy sets A and B, the membership of z in A ⊕ B (e.g., addition) is sup_{x+y=z} min(μ_A(x), μ_B(y)), often computed efficiently via α-cuts and sup-min composition to avoid direct optimization. This method preserves the convexity and normality of fuzzy numbers under arithmetic operations like addition, multiplication, and inversion, though it can introduce overestimation similar to interval arithmetic. In contrast to crisp intervals, which provide guaranteed bounds but no gradation, fuzzy operations yield results with varying confidence levels across the support.[41] Type-2 fuzzy intervals address higher-order uncertainties by allowing membership degrees themselves to be fuzzy, forming intervals of possible membership values rather than single points. Introduced to model vagueness in membership functions, such as inter-expert disagreements on "high temperature," an interval type-2 fuzzy set has a footprint of uncertainty bounded by upper and lower membership functions. Arithmetic on type-2 fuzzy intervals extends the α-cut method to secondary memberships, using the extension principle on both primary and secondary levels, often simplified via interval type-2 representations for computational tractability. This provides finer granularity for imprecise parameters compared to type-1 fuzzy intervals. These extensions find applications in decision-making under uncertainty, where fuzzy intervals rank alternatives with partial preferences, and in control systems, such as adaptive fuzzy controllers that adjust gains based on gradual sensor imprecision. Recent developments in semi-type-2 fuzzy structures and hybrid interval type-2 methods, blending type-1 and type-2 elements for imprecise parameters, have enhanced performance in multi-criteria optimization and precision agriculture as of 2025.[42][43]Historical and Practical Aspects
Development History
The development of interval arithmetic emerged from efforts to rigorously bound numerical errors in early digital computing. Contemporaneous advancements in error analysis, such as James H. Wilkinson's pioneering work on backward error analysis in the 1960s—which provided insights into how floating-point computations perturb problems to nearby ones with exact solutions, as detailed in his 1963 monograph Rounding Errors in Algebraic Processes []—complemented these efforts. However, the formal foundations of interval arithmetic were laid earlier by Teruo Sunaga in his 1958 paper on inclusion theory [], and further developed by Ramon E. Moore in his 1959 technical report "Automatic Error Analysis in Digital Computation," where he introduced interval representations to enclose all possible rounding errors in arithmetic operations []. This work, stemming from Moore's PhD dissertation at Stanford University completed in 1962, shifted focus from statistical error estimates to deterministic enclosures []. Moore's seminal 1966 book Interval Analysis established the theoretical framework, defining interval operations and demonstrating their use in automatic error bounding for computational problems, including applications to ordinary differential equations (ODEs) via enclosure methods for initial value problems []. In the 1970s, the field evolved from manual error analysis to computational implementations, with significant attention to mitigating the dependency problem—where multiple occurrences of a variable in an expression lead to overly wide intervals—through techniques like the mean value extension and Hansen's forms []. Key contributors during this period included Götz Alefeld and Jürgen Herzberger, whose 1983 book Introduction to Interval Computations advanced the algebraic theory and practical algorithms for interval methods []. The 1980s marked a milestone in software development, with early packages implemented in languages like FORTRAN and ALGOL to support verified computations, as showcased in international symposia such as the 1980 Interval Mathematics conference []. Innovations like E. Kaucher's extended interval arithmetic, introduced in 1980, incorporated improper intervals to enhance enclosure precision and address certain dependency issues []. More recently, incremental advances have focused on efficient methods for linear systems, such as the generalized interval accelerated overrelaxation (GIAOR) solver proposed in 2023, which improves convergence for interval linear equations while maintaining enclosure guarantees []. Ongoing research through 2025 continues to refine these solvers for applications in verified numerics, emphasizing tighter bounds and integration with modern computing paradigms [].IEEE 1788 Standard
The IEEE 1788-2015 standard specifies basic interval arithmetic operations for floating-point numbers, adhering to one of the commonly used mathematical interval models while supporting IEEE 754 floating-point formats. It establishes a framework that serves as an intermediary layer between hardware implementations and programming languages, without requiring dedicated hardware support. Published on June 30, 2015, the standard emphasizes portability and reliability in verified numerical computations.[44][45] Key features of the standard include a defined set of required operations—such as addition, subtraction, multiplication, division, square root, and mixed-type comparisons—along with support for multiple rounding modes (inward and outward directed rounding) to ensure enclosure properties. Exception handling is managed through a decoration mechanism rather than global flags, allowing for exception-free computations that track reliability without interrupting execution. The standard is flavor-independent, accommodating different interval models like set-based (standard intervals) or modal (including infinite or signed zero endpoints) variants, provided they meet core compliance criteria.[44][45][46] Decorated intervals extend basic intervals by attaching a decoration—a metadata tag indicating the status and reliability of the computation—to each interval result. The five possible decorations, ordered by increasing reliability, are:ill (ill-formed, indicating undefined operations), trv (trivial, empty or whole real line), def (defined, non-empty interior), dac (defined and continuous range), and com (common, bounded continuous range with finite endpoints). This system enhances trustworthiness in applications like rigorous error analysis by propagating decoration information through operations, enabling users to assess result validity without additional checks.[44][45][47]
Compliance with the standard requires that for input intervals X and Y, the computed result \operatorname{op}(X, Y) satisfies X \subseteq \operatorname{op}(X, Y) \subseteq \hat{X}, where X represents the true range of the operation and \hat{X} is an enclosing interval with bounded excess width to control overestimation. This enclosure property, combined with directed rounding, guarantees that the result contains all possible values while limiting unnecessary expansion.[44][45]
As of November 2025, no major revisions to IEEE 1788-2015 have been published beyond the related IEEE 1788.1-2017 simplified subset for binary64 floating-point intervals, though a full revision is mandated before the end of 2025 to address evolving needs in verified computing. The standard continues to influence the development of libraries for reliable numerical software.[44][48][49]