Interval arithmetic ($X=[a,b]$)

Interval arithmetic calculates with closed intervals that contain the possible values of a quantity. If all we know is $x\in X=[a,b]$, an interval enclosure for a function $f$ must contain $f(x)$ for every allowed $x$. The result says what is guaranteed, including uncertainty in the input and, with outward rounding, roundoff error in the calculation. A wide answer can still be correct; a narrow answer is useful only if it contains every possible value.

The attraction is that a finite calculation can make a statement about infinitely many real numbers at once. An interval enclosure can certify that a function stays positive throughout a whole closed interval, or bound its maximum for mathematical optimization. For example, on $X=[0,1]$, the actual image of a function for $f(x)=x(1-x)$ is $[0,1/4]$, but direct interval arithmetic gives the wider $[0,1]$. Interval subdivision and the interval square range improve this answer in different ways.

Historically, Ramon E. Moore's 1962 Stanford dissertation studied interval arithmetic and automatic error analysis in digital computing; his book Interval Analysis followed in 1966. Eldon Hansen's account documents earlier reports as well: these dates describe important steps in developing and disseminating the subject, rather than a claim of sole invention in a particular year.^[ref] Moore, R. Baker Kearfott and Michael J. Cloud later wrote Introduction to Interval Analysis (2009).^[ref]

An interval enclosure $F(X)=[L,U]$ for a real-valued function $f$ on a closed interval $X$ satisfiesHere $f(X)$ means the actual image of a function, also called its pointwise range on $X$; $F(X)$ denotes a calculated interval enclosure. They need not agree. Sampling a few inputs can suggest a bound, but does not establish an interval enclosure between those inputs. Kearfott and coauthors explicitly distinguish the image of a function from evaluating an expression with interval arithmetic, because different expressions for the same function can give different bounds.^[ref]

For closed intervals $X=[a,b]$ and $Y=[c,d]$, exact addition, subtraction and multiplication giveThese interval arithmetic operations describe all results $u\circ v$ for $(u,v)$ in the Cartesian product $X\times Y$: the two inputs are allowed to vary independently. Independence here means freedom to choose either input anywhere in its closed interval; it does not assert anything about probability. For example, $[1,2]+[3,5]=[4,7]$ and $[1,2]-[3,5]=[-4,-1]$.

All four endpoint products matter when signs change. For $X=[-2,3]$ and $Y=[-4,1]$, the endpoint products are $8,-2,-12,3$, so $XY=[-12,8]$. Taking just $ac$ and $bd$, even after sorting them, would give $[3,8]$ and lose valid negative products.

For division, if $0\notin Y$, the multiplicative inverse gives $1/Y=[1/d,1/c]$ and $X/Y=X(1/Y)$. Thus $[1,2]/[3,4]=[1/4,2/3]$. This ordinary finite-closed interval rule requires a denominator that excludes zero. When the denominator contains zero, division is undefined for some pairs and can become unbounded near zero; these formulas cannot supply a finite interval enclosure of all quotients. The operations above use exact endpoints; a computer implementation must also apply outward rounding.

A natural interval extension evaluates a chosen expression by replacing its arithmetic operations with interval arithmetic operations, its constants with enclosing closed intervals, and any additional functions with valid interval enclosures. Each intermediate result must remain defined on its inputs. The resulting $F(X)$ encloses the actual image of a function $f(X)$, but its width depends on the expression used. Rump's INTLAB tutorial describes this inclusion principle and warns that repeated inputs can produce severe overestimation.^[ref]

The interval dependency problem is the loss of relationships between repeated occurrences of the same input. For $X=[0,1]$, interval subtraction gives $X-X=[-1,1]$: it permits $u-v$ with independent choices $u,v\in X$. But the function $x\mapsto x-x$ has actual image of a function $\{0\}=[0,0]$. Giving both operands the name $X$ does not tell an interval arithmetic calculation to enforce $u=v$.

For the polynomial $f(x)=x(1-x)$ on $X=[0,1]$, the natural interval extension isThis allows the impossible combination $x=1$ in the first factor and $x=0$ in the second, producing the spurious upper bound $1$. In the actual function, both occurrences use the same $x$. Completing the square gives $x(1-x)=1/4-(x-1/2{)}^2$, which lies between $0$ and $1/4$ on $[0,1]$; every value between these bounds occurs, by continuity and the intermediate value theorem. The maximum $1/4$ occurs at $x=1/2$, while either endpoint gives the minimum $0$.

Interval subdivision covers $X$ by smaller closed intervals $X_j$, computes a valid interval enclosure $F(X_j)$ on each, and takes their union. Every allowed input belongs to a piece, so its output belongs to that union. If one closed interval is wanted, take the smallest one containing the union; gaps between separate output pieces can then be lost. Splitting narrows the freedom given to repeated inputs, while increasing the number of evaluations.

For $f(x)=x(1-x)$, split $[0,1]$ at $1/2$. The natural interval extensions areTheir union is $[0,1/2]$. Four equal pieces sharpen the upper bound again:The union is now $[0,3/8]=[0,0.375]$, still wider than the actual image of a function $[0,1/4]$. These are exact rational number bounds: the excess width comes from the interval dependency problem, rather than roundoff error.

The interval square range treats squaring as one function of one input. For $X=[a,b]$ it is exactlyIt retains the relationship that ordinary interval multiplication loses: for $Z=[-1/2,1/2]$, the interval square range is $[0,1/4]$, whereas the independent-input product $ZZ$ is $[-1/4,1/4]$.

Consequently, completing the square for $x(1-x)$ and using the interval square range givesThis is the exact image of a function on $X=[0,1]$. Merely rewriting the expression and evaluating $[1/4,1/4]-ZZ$ gives $[0,1/2]$, so it does not achieve the same sharpening. A mathematical $Z^2$ must be interpreted explicitly here: a square range operation and an independent-input interval product have different meanings. Choosing an operation that preserves known structure can save many steps of interval subdivision.

Outward rounding replaces an exact lower endpoint by a representable value no larger than it, and an exact upper endpoint by a representable value no smaller than it. This preserves an interval enclosure under floating-point arithmetic. In the binary numeral system, most rational numbers cannot be represented exactly with finitely many digits, so the rounding direction is essential even for elementary calculations. Rump explains directed rounding and its use in interval bounds in §§4 and 5.3 of his survey.^[ref]

To see the issue without long binary digit strings, use an illustrative decimal grid with step $0.001$. Exact interval division gives $[1,1]/[3,3]=[1/3,1/3]$. Rounding both endpoints to the nearest grid value gives $[0.333,0.333]$, which excludes the true answer because $0.333<1/3$. Outward rounding instead givesThis decimal toy illustrates the rule; its displayed endpoints are not the results of binary directed rounding. Real implementations need valid outward rounding throughout the calculation, including input conversion and intermediate interval arithmetic operations; rounding only the final output cannot repair an earlier lost bound. INTLAB's tutorial demonstrates why decimal input strings and previously rounded intermediate values need care.^[ref]

Interval root exclusion certifies that a function has no zero of a function on $X$ when a valid interval enclosure $F(X)$ excludes zero. For $g(x)=x(1-x)-1/3$ on $[0,1]$, the interval square range yields $G(X)=[-1/3,-1/12]$, which excludes zero. Direct interval arithmetic yields $[-1/3,2/3]$ and is inconclusive, even though the function has no zero of a function there.

Knowing only that a calculated interval enclosure contains zero does not certify a zero of a function: it may contain unattainable values. Even the positive constant function $f(x)=1$ has a valid, loose interval enclosure $[-1,2]$. A separate existence argument, such as reliable opposite endpoint signs together with continuity in the intermediate value theorem, is required; see root bracket and bisection method. Interval subdivision can resolve some inconclusive pieces, but remaining pieces must be reported as unresolved unless an existence argument succeeds. This makes interval root exclusion useful for systematically discarding regions in a search.

// Target: analysis.bigb