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]:

(4.35)

Two intervals
and
are said to be equal if

(4.36)

The intersection of two intervals is empty
or
, if either

(4.37)

otherwise,

(4.38)

The union
of the two intersecting intervals is

(4.39)

An order of intervals is defined by

(4.40)

The width of an interval
is
.
The absolute value is

(4.41)

Example 4.7.1.

Interval arithmetic operations are defined by

(4.42)

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

(4.43)

provided
in the division operation.

Example 4.7.2.

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

(4.44)

(4.45)

and associative

(4.46)

(4.47)

But it is not distributive; however, it is subdistributive

(4.48)

Example 4.7.3.

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