4.7.5 Hansen's Linear Interval Arithmetic

Linear interval arithmetic and Hansen's linear interval arithmetic share a common motivation. Hansen's linear interval arithmetic is, however, a closer relative of the derivative-based methods.

In , each interval is represented as a sampled value v, and a slope d:

the bounds on must also be stored. It seems reasonable to assume that c is fixed, as d may be adjusted to account for an arbitrary value of c. Intervals of may be graphically depicted, as follows:

Bounds produced using Hansen's linear interval arithmetic are generally superior to bounds produced using a derivative-based method, as the relationship(s) between the free variable(s) and derivative(s) may be taken into account, as with linear interval arithmetic. An example evaluation is appropriate; let us bound the range of g(x) for , by evaluating g([0,1]). Let ; with Hansen's linear interval arithmetic,

while with linear interval arithmetic,

Evaluation rules for Hansen's linear interval arithmetic are given in [28], although sufficient rules are easily determined. A squaring operator is needed for the above result with ; using a general multiplication operator produces a sub-optimal bound. The two bounds are seen to be identical, as the following diagrams illustrate:

Although the diagram gives v a slight width, in actuality the two bounds are identical. We may extend the previous evaluations by bounding the range of for . With Hansen's linear interval arithmetic,

with linear interval arithmetic,

Linear interval arithmetic has produced a superior bound; illustrations of the two bounds follow:

The following diagram depicts renderings of

over using Hansen's two-dimensional linear interval arithmetic and two-dimensional linear interval arithmetic. As before, the two methods do not perform a similar amount of work per stage; the diagram does not indicate the relative efficiencies of the two methods.

The following diagram depicts the efficiency of the methods when rendering the aforementioned equation:

The following diagrams illustrate the information gained, using each method, after 20 interval evaluations:

and after 40 interval evaluations:

Hansen's linear interval arithmetic and our linear interval arithmetic perform a similar amount of work computing bounds for any given operator. Consider the operator , which has the following evaluation rule:

Evaluation may be simplified by assuming c=1, so varies from -1 to 1. With that assumption, evaluation proceeds by the following rule:

Evaluation efficiency may be improved considerably by expanding the interval operations, as was done with the evaluation of our interval operators. The evaluation breaks into a number of cases, depending on the relationship between a and zero, and b and zero. A portion of the evaluation rule, for our example g, follows:

The above portion is taken from an evaluation rule with 16 cases; a greater number of cases could have been used, in the aim of reducing the likelihood of computing a large number of floating-point operations. The evaluation rule for g using linear interval arithmetic follows:

where , , , and . With Hansen's method, most evaluations employ seven multiplications and one addition; with our method, most evaluations employ six multiplications and six additions. Our evaluation rule falls into fewer cases, and removal of conditionals occurs earlier. Changing the domain of influences the efficiency of our method as well.

It is not completely clear why Hansen chose to evaluate using

instead of

as

Many evaluation rules are possible: what is needed is a methodology for choosing rules. With Hansen's intervals, there is a choice between minimizing the width of the resulting v or minimizing the width of the resulting d, where . Both methods are computationally identical for linear operators. Hansen's methods outlined in [28] require more floating-point operations for division and multiplication.

With either approach, fewer floating-point operations may be used to compute bounds, if looser bounds are acceptable. Derivative methods are easily implemented and produce slightly larger bounds at a slightly higher evaluation cost. The efficiency graphs illustrate that each approach differs, in computational efficiency, by a constant factor.

With a modern language, such as C++, Hansen's intervals may be built using an underlying interval arithmetic class. Our methods may be modularly constructed by using an underlying linear bound class, which observes the current rounding mode.

It is unreasonable to expect a common optimizing compiler to produce code comparable to a direct implementation, as symbolic reasoning is employed when producing an efficient implementation. The author advocates the implementation of a program which employs sophisticated symbolic reasoning to automatically produce ``direct'' implementations, for any of a variety of interval arithmetics. Such a program would be given a description of an operator's properties, and produce a code fragment which implements the corresponding interval operator. Such routines may be folded into an optimizing compiler, but it is unclear what algorithms would benefit, other than interval arithmetic classes.

The chief advantage of our approach to generalized interval arithmetic is its mathematical simplicity, which allows for properties to be naturally tracked. This simplicity also provides for a superior handling of discontinuous functions, and multi-functions.

The chief advantage of Hansen's approach is that is easily implemented, given an implementation of . Of course, is implemented with even less work. With a naive implementation, both and return sub-optimal bounds. Regardless, as j shrinks, the relative differences between , , and approach zero. With effort, better bounds may be returned, although this mitigates the cheif advantage of the two methods.

Our generalized interval arithmetic may be implemented using Hansen's methods, or using derivative-based methods. Temporary recourse to the methods outlined in this thesis is possible when considering non-differentiable operators.

Finally, it should be noted that with several minor changes to Hansen's fundamental definition of intervals, we may produce our fundamental definition of intervals. With , and , this proceeds as follows: for an interval , let vary from 0 to 1, rather than from -c to c; let b be a member of , rather than a member of .

Jeff Tupper

March 1996