Interval Arithmetic

by Cassio • 2011/09/19 • Research

Continuing the series on interval methods, this post will give us more details about interval arithmetic, the most popular interval formalism. In interval arithmetic each quantity (think of it as a scalar variable, or a floating point number in your favorite programming language x is represented as an interval $\bar{x} = [x_L, x_U]$ , where $x_L \leq x_U, x \in \Re$ .

Most operations in interval arithmetic are simple and intuitive. Some examples are:

$\bar{x} + \bar{y} = [x_L + y_L, x_U + y_U]$ ;
$\bar{x} - \bar{y} = [x_L - y_U, x_U + y_L]$ ;
$\bar{x} \times \bar{y} = [min(x_L y_L,x_L y_U,x_U y_L,x_U y_U), max(x_L y_L,x_L y_U,x_U y_L,x_U y_U)]$ ;
$1 / \bar{x} = [min(1/x_L,1/x_U), max(1/x_L,1/x_U)],\; \mbox{if}\;0 \notin \bar{x}$ ;
$\bar{x} / \bar{y} = \bar{x} \times 1/\bar{y}$ ;
$e^{\bar{x}} = [e^{x_L}, e^{x_U}]$ .

Intervals don’t have to be finite. There’s an empty interval, represented by $[]$ , and an one or both interval limites can be infinite: $[-\infty, \infty]$ . Interval arithmetic implementations typically handle invalid domain inputs (such as being asked to compute the square root of $[-2, 2]$ ) by operating only on the valid range (this is a design choice, and perhaps it would be preferred to “fail early” with an error).

There are numerous open source implementations of interval arithmetic in various languages, including C++ (part of Boost), MATLAB, Python, and others. There is also an online interval calculator you can play with.

Let’s work through a simple expression using intervals and the above operations. Say $\bar{x} = [2, 4]$ and $\bar{y} = [1, 2]$ . Let’s compute $e^{\bar{y}} \times \frac{\bar{x} -\bar{y}}{\bar{x} + \bar{y}}$ , in steps:

$e1 = e^{\bar{x}} = [e^1, e^2] \simeq [2.718, 7.389]$
$e2 = \bar{x} -\bar{y} = [2-2, 4-1] = [0, 3]$ ;
$e3 = \bar{x} + \bar{y} = [2+1,4+2] = [3, 6]$ ;
$e4 = 1/e3 = [min(1/3,1/6),max(1/3,1/6)] = [1/6,1/3]$ ;
$e5 = e2/e3 = e2 \times e4 = [min(0, 0, 1/2, 1), max(0, 0, 1/2, 1)] = [0,1]$ ;
$e6 = e1 \times e5 = [min(0, 2.718, 0, 7.389), max(0, 2.718, 0, 7.389)] = [0, 7.389]$ .

While interval arithmetic operations are simple (and therefore fast implementations can be written) and mostly intuitive, they suffer from some issues. First, if an interval appears multiple times in the same computation, IA doesn’t know it represents the same quantity. This leads to some results that, from a real arithmetic perspective, are non-sensical. For instance, consider $\bar{x}$ above. $\bar{x} - \bar{x} = [-2, 2]$ , while clearly the correct answer is 0.

This leads to an error explosion problem when the same quantity is repeatedly used in a chain of operations such as evaluating and polynomial. The end result is likely to bee too conservative (i.e., too wide) to be practical. For instance, still considering $\bar{x}$ above, the simple expression $\bar{x} \times (6 - \bar{x})$ leads to $[4, 16]$ , which is 12 times wider than the real result, $[8, 9]$ (just iterate through a few values for x and you’ll get there).

Several extensions and improvements to interval arithmetic have been proposed to handle these issues. The one I use in my PhD work is affine arithmetic, and I’ll talk about it next in this series.