next up previous notation contents
Next: 4.8 Example Renderings Up: 4.7 Other Work Previous: 4.7.4 Derivative-Based Methods

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 tex2html_wrap_inline38685 , each interval is represented as a sampled value v, and a slope d:

math29941

the bounds on tex2html_wrap_inline32761 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 tex2html_wrap_inline38685 may be graphically depicted, as follows:

figure29946

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 tex2html_wrap_inline38615 , by evaluating g([0,1]). Let tex2html_wrap_inline38721 ; with Hansen's linear interval arithmetic,

math30055

while with linear interval arithmetic,

math30086

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 tex2html_wrap_inline38685 ; using a general multiplication operator produces a sub-optimal bound. The two bounds are seen to be identical, as the following diagrams illustrate:

figure30107

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 tex2html_wrap_inline38773 for tex2html_wrap_inline38615 . With Hansen's linear interval arithmetic,

math30353

with linear interval arithmetic,

math30372

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

figure30387

The following diagram depicts renderings of

math30589

over tex2html_wrap_inline38409 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.

figure30593

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

figure30633

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

figure30640

and after 40 interval evaluations:

figure30655

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

math30678

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

math30686

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:

math30694

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:

math30719

where tex2html_wrap_inline38841 , tex2html_wrap_inline38843 , tex2html_wrap_inline38845 , and tex2html_wrap_inline38847 . 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 tex2html_wrap_inline32761 influences the efficiency of our method as well.

It is not completely clear why Hansen chose to evaluate tex2html_wrap_inline38851 using

math30737

instead of

math30745

as

math30753

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 tex2html_wrap_inline38857 . 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 tex2html_wrap_inline38685 is easily implemented, given an implementation of tex2html_wrap_inline32517 . Of course, tex2html_wrap_inline38671 is implemented with even less work. With a naive implementation, both tex2html_wrap_inline38671 and tex2html_wrap_inline38685 return sub-optimal bounds. Regardless, as j shrinks, the relative differences between tex2html_wrap_inline38871 , tex2html_wrap_inline38873 , and tex2html_wrap_inline38875 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 tex2html_wrap_inline38685 , and tex2html_wrap_inline32891 , this proceeds as follows: for an interval tex2html_wrap_inline38881 , let tex2html_wrap_inline32761 vary from 0 to 1, rather than from -c to c; let b be a member of tex2html_wrap_inline38895 , rather than a member of tex2html_wrap_inline32653 .


next up previous notation contents
Next: 4.8 Example Renderings Up: 4.7 Other Work Previous: 4.7.4 Derivative-Based Methods
Jeff TupperMarch 1996