Interval computing

A great challenge in numerical computation is coming up with algorithms that are stable for a wide range of inputs. This leads to creative approaches like partial pivoting in gaussian elimination, or accurate floating point summation which is important in inner products. Unfortunately, all of these solutions are problem specific.

Enter interval computing.

Interval computing attempts to solve rounding errors on computers. It does this by placing brackets around the error. It’s almost like the uncertaininty we place on observables in physical experiments. For example, a reading A with a standard deviation $\partial A$ can be written using intervals:

$A \pm \partial A \sim [A - \partial A, A + \partial A] \sim [a, b] = \bar{A}$

In general, $\bar{A} = [a, b]$ defines an interval which bounds the floating point number. Four of our primitve operations add, subtract, multiply and divide on two intervals $\bar{A} = [a,b]$ and $\bar{B} = [c,d]$ are:

$\bar{A} + \bar{B} = [a+c,b+d]$

$\bar{A} – \bar{B} = [a-d,b-c]$

$\bar{A} \times \bar{B} = [min(ac,ad, bc,bd), max(ac,ad,bc,bd)]$

$\frac {1}{\bar{A}} = [1/b, 1/a]$

$\bar{A} \div \bar{B} = \bar{A} \times \frac{1}{\bar{B}}$

(where the interval $\bar{B}$ does not contain zero.)

Interval computation can also be used for transcendental functions such as log or sin. The Taylor expansion for sin for example is:

$\sin(x) = x – \frac {x ^ 3} { 3 !} + \cdots$

which is a composition of the primitive operations defined above. Interval computation is very useful in determining the robustness of a numerical procedure.

This entry was posted on Friday, August 11th, 2006 at 3:11 pm and is filed under Physics. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.