next up previous notation contents
Next: 4.7.5 Hansen's Linear Interval Arithmetic Up: 4.7 Other Work Previous: 4.7.3 Extended Interval Arithmetic

4.7.4 Derivative-Based Methods

When working with interval methods, computed bounds on derivatives often supplement computed bounds on values. A simple example problem will illustrate the core technique: consider bounding the range of g(x), for tex2html_wrap_inline38615 . In chapter two, we bounded the range of g(x) by evaluating

math29640

or

math29647

another approach is to evaluate

math29654

with tex2html_wrap_inline38621 . Usually, j is taken to be the midpoint of the domain: tex2html_wrap_inline38625 , so

math29668

bounds g(x) for tex2html_wrap_inline38615 . The midpoint is chosen, as it often produces the best bounds possible with this approach.

This approach, based on the first derivative, may be graphically depicted, as follows:

figure29682

The linear interval approach may be similarly depicted, as follows:

figure29795

The following diagram depicts renderings of

math28385

over tex2html_wrap_inline38409 using linear interval arithmetic, and two derivative-based methods. The linear interval arithmetic method uses four-way cutting, the simplest progressive method discussed. The two derivative-based methods both use the first derivative only, but differ in their placement of the sample tex2html_wrap_inline33497 . One places tex2html_wrap_inline33497 at the center of the cluster; the other places tex2html_wrap_inline33497 at the bottom left corner of the cluster. As each method uses a different number of interval evaluations per stage, the following diagram does not indicate the relative efficiencies of the different methods.

figure29873

Clearly, the linear interval arithmetic produces superior intervening renderings, as fewer spurious visual artifacts are present in the renderings produced using linear interval arithmetic. The following diagram illustrates the efficiency of the various methods when rendering the aforementioned equation:

figure29906

Of course, the derivative methods are not competitive when the underlying functions are not differentiable. The following diagram illustrates the information gained, using each method, after 45 interval evaluations:

figure29913

An interval arithmetic similar to tex2html_wrap_inline32891 may be implemented using derivative-based methods.   tex2html_wrap_inline38671 denotes such an arithmetic, which bounds both the value and first derivative of evaluated functions. Each element of tex2html_wrap_inline38671 is given by a first component tex2html_wrap_inline38675 , which bounds the value at tex2html_wrap_inline33027 , and a second component tex2html_wrap_inline38679 , which bounds the derivative for tex2html_wrap_inline38681 . Domains other than [0,1] are possible; as are other sample locations. Further discussion of this approach can be found in the next subsection.


next up previous notation contents
Next: 4.7.5 Hansen's Linear Interval Arithmetic Up: 4.7 Other Work Previous: 4.7.3 Extended Interval Arithmetic
Jeff TupperMarch 1996