What is Interval Arithmetic?

Interval arithmetic is based on defining the four elementary arithmetic operations on intervals. Let a = [a_{l}, a_{u}] and b = [b_{l}, b_{u}] be intervals. Then, if op ∈ {+, −, ∗, /}, we define

a op b = {x op y | x ∈ a and y ∈ b} .

For example, a + b = [a_{l} + b_{l}, a_{u} + b_{u}]. In fact, all four operations can be defined in terms of addition, subtraction, multiplication, and division of the endpoints of the intervals, although multiplication and division may require comparison of several results. The result of these operations is an interval except when we compute a/b and 0 ∈ b.

Why Interval Arithmetic?

• With directed roundings, we can bound roundoff error in the computations. We can combine interval arithmetic with tools such as fixed-point iteration theorems to

– automatically verify rigorous bounds, from approximate solutions.

– automatic theorem proving.

• Interval arithmetic provides rigorous bounds on the ranges of functions. Posession of such bounds can be powerful, especially in rigorous global optimization.

An Example of Interval Arithmetic

[−1, 2] ([3, 4] + [−5, 6])) = [−1, 2] ([−2, 10])
= [−10, 20],

whereas

[−1, 2][3, 4] + [−1, 2][−5, 6] = [−4, 8] + [−10, 12]
= [−14, 20]

Here,

[−14, 20] = {x | x = x_{1} + x_{2}, x_{1} ∈ [−4, 8],
x_{2} ∈ [−10, 12]},

and [−14, 20] contains the range of xy + xz for x ∈ [−1, 2], y ∈ [3, 4], and z ∈ [−5, 6].

Inclusion Monotonic Interval Extensions of Functions

Definition. If f is a continuous function of a real variable, then an inclusion monotonic interval extension f is a function from the set of intervals to the set of intervals, such that, if x is an interval in the domain of f,

{f(x) | x ∈ x} ⊂ f(x)

and such that

x ⊂ y⇒f(x) ⊂ f(y).

• We may obtain such interval extensions of a polynomial by replacing real operations by corresponding interval operations. For example, if p(x) = x^{2} − 4, then p([1, 2]) may be defined by

p([1, 2]) = ([1, 2])^{2} − 4 = ([1, 4]) − [4, 4]
= [−3, 0].

Interval Extensions of Transcendental Functions

• We may use the mean value theorem or Taylor’s theorem with remainder formula. For example, suppose x is an interval and a ∈ x. Then, for any y ∈ x, we have

sin(y) = sin(a) + (y − a) cos(a) − (y − a)^{2}/2 sin(c)

for some c between a and y. If a and y are both within a range where the sine function is non-negative, then we obtain

sin(y) ∈ sin(a) + (x − a) cos(a) − \frac{(x − a)^{2}}{2} .

Specifically, if x = [.1, .3] and we use a = .2, we would obtain the “value”

sin([.1, .3]) ⊆ sin(.2) + [−.1, .1] cos(.1)

− \frac{([−.1, .1]^{2})}{2}

⊆ [.0998, .0999]
+ [−.1, .1][.995, .996] + [−.005, 0]
= [−.0048, .1995]

• Sharper interval extensions may be obtained in specific cases by using e.g. monotonicity of the original function.

Pitfalls to Naive Interval Arithmetic

• For rigorous bounds on roundoff error, one may be tempted to translate floating-point computer codes by merely changing the data types.

• Due to interval dependencies, such naive development often is unsuccessful.

• Interval arithmetic is successful if it is applied to appropriate tasks and with appropriate algorithms.

– It provides rigorous results from the computer arithmetic.

– It can actually result in faster algorithms, even if the actual arithmetic is in software and 20 to 30 times slower than floating point arithmetic.

• Researchers continue to make advances to enlargen the domain in which interval analysis can make computations rigorous and reliable.

Interval Newton Methods

A Simple Example

If n = 1 and

f(x) = x^{2} − 4,

then the linear interval system becomes

2x_{i}(x̃_{i} − x_{i}) = −f(x_{i}).

The interval Newton iteration equation becomes

x̃_{i} = x̃ = x_{i} − \frac{f(x_{i})}{2x_{i}} = x − \frac{f(x)}{2x}.

If we choose initial interval and point

X_{k} = x_{i} = x = [1, 2.5], x_{i} = x = 1.75,

then

x̃ = 1.75 − \frac{−.9375}{[2, 5]} = 1.75 − [.1875, .46875]  (1)
= [1.9375, 2.21875] ⊂ x,  (2)

so we may conclude that there is a unique root of f in x.

Finding All Roots

• In univariate problems, interval Newton methods can be iterated with extended interval arithmetic to always find all roots.

• In multivariate problems, interval Newton methods can be combined with generalized bisection and binary search to always find all roots.

• In both instances, failure modes are benign:

– Failure can only occur by exceeding the computer’s resources or because of the limited resolution of the floating-point numbers.

– When failure occurs, the algorithms still print a list of boxes within which all roots must lie.

An Example

As before, let f(x) = x^{2} − 4, but now let X_{k} = x_{i} = x = [−2, 2] and x_{i} = x = 0. The first iteration of the interval Newton method thus becomes

x̃ = 0 − \frac{−4}{[−4, 4]} = 0 − ([−∞, −1] ∪ [1, ∞])  (3)
= ([−∞, −1] ∪ [1, ∞])  (4)

Thus,

x̃ ∩ X_{k} = [−2, −1] ∪ [1, 2].  (5)

• One of the intervals in Equation 5 is put on a list for further processing, and the interval Newton method is iterated on the other.

• The interval Newton method will converge to zero-width intervals for each startin interval from Equation 5.

• Hansen has proven that this behavior is true in general.