Next: 4.8 Rounded interval arithmetic Up: 4. Nonlinear Polynomial Solvers Previous: 4.6 Robustness issues   Contents   Index

4.7 Interval arithmetic

Interval techniques, primarily interval Newton's methods combined with bisection to ensure convergence, have been the focus of significant attention, see for example Kearfott [192], Neumaier [284]. Interval methods have been applied in geometric modeling and CAD. For example, Mudur and Koparkar [277], Toth [422], Enger [90], Duff [80] and Snyder [400,399] applied interval algorithms to geometry processing, whereas Sederberg and Farouki [377], Sederberg and Buehler [375] and Tuohy et al. [425] applied interval methods in approximation problems. In [377] Sederberg and Farouki introduced the concept of interval Bézier curve. Tuohy and Patrikalakis [426] applied interval methods in the representation of functions with uncertainty, such as geophysical property maps. Tuohy et al. [424] and Hager [147] applied interval methods in robotics. Bliek [27] studied interval Newton methods for design automation and inclusion monotonicity properties in interval arithmetic for solving the consistency problem associated with a hierarchical design methodology. Interval methods are also applied in the context of solving systems of nonlinear polynomial equations [178,179,254,255], which we will briefly review in Sect. 4.8. More recently, Hu et al. [180,181] extended the concept of interval Bézier curves [377] to interval non-uniform rational B-splines (INURBS) curves and surfaces. INURBS differ from classical NURBS in that the real numbers representing control point coordinates are replaced by interval numbers. In other words, the control point vectors are replaced by rectangular boxes. This implies that in 3-D space an INURBS curve represents a slender tube and an INURBS surface patch represents a thin shell, if the intervals are chosen sufficiently small. The numerical and geometric properties of interval B-spline curves and surfaces are analyzed in Shen and Patrikalakis [387], while their use in solid modeling is presented in Hu et al. [179,178,180,181], and boundary representation model rectification in Shen [386], Shen et al. [389], Patrikalakis et al. [303] and Sakkalis et al. [360].

An interval is a set of real numbers defined below [273]:


Two intervals and are said to be equal if

The intersection of two intervals is empty or , if either


The union of the two intersecting intervals is

An order of intervals is defined by

The width of an interval is .
The absolute value is

Example 4.7.1.


Interval arithmetic operations are defined by


where represents an arithmetic operation . Using the end points of the two intervals, we can rewrite equation (4.42) as follows:

provided in the division operation.

Example 4.7.2.


Now let us introduce the algebraic properties of interval arithmetic. Interval arithmetic is commutative,


and associative

But it is not distributive; however, it is subdistributive

Example 4.7.3.


Next: 4.8 Rounded interval arithmetic Up: 4. Nonlinear Polynomial Solvers Previous: 4.6 Robustness issues   Contents   Index
December 2009