INTERVAL NEWTON METHODS

Introduction.

Interval Newton methods combine the classical Newton method, the mean value theorem, and interval analysis. The result is an iterative method that can be used both to refine enclosures to solutions of nonlinear systems of equations, to prove existence and uniqueness of such solutions, and to provide rigorous bounds on such solutions, including tight and rigorous bounds on critical points of constrained optimization problems. Interval Newton methods can also prove non-existence of solutions within regions. Such capabilities can be used in isolation, for example, to provide rigorous error bounds for an approximate solution obtained with floating point computations, or as an integral part of global branch and bound algorithms. Univariate interval Newton methods.

For the fundamental concepts used throughout this explanation, see Interval analysis : Introduction, interval numbers and basic properties of interval arithmetic.

Suppose f : x = [\underline{x}, \overline{x}] → R has a continuous first derivative on x, suppose that there exists x^{∗} ∈ x such that f(x^{∗}) = 0, and suppose that x̌ ∈ x. Then, since the mean value theorem implies

0 = f(x^{∗}) = f(x̌) + f′(ξ)(x^{∗} − x̌),
we have x^{∗} = x̌ − f(x̌)/f′(ξ)

for some ξ ∈ x. If f′(x) is any interval extension of the derivative of f over x, then

x^{∗} ∈ x̌ − f(x̌)/f′(x) for any x̌ ∈ x. (1)

(Note that, in certain contexts, a slope set for f centered at x̌ may be substituted for f′(x); see Interval analysis: The slope interval Newton method or [1] for further references.) Equation (1) forms the basis of the univariate interval Newton operator:

N(f, x, x̌) = x̌ − f(x̌)/f′(x).  (2)

Because of (1), any solutions of f(x) = 0 that are in x must also be in N(f, x, x̌). Furthermore, local convergence of iteration of the interval Newton method (2) is quadratic in the sense that the width of N(f, x, x̌) is roughly proportional to the square of the width of x. Furthermore, if an interval derivative extension (in contrast to an interval slope) is used for f′(x), then

N(f, x, x̌) ⊂ int(x),

where int(x) represents the interior of x, implies that there is a unique solution of f(x) = 0 within N(f, x, x̌), and hence within x. Multivariate interval Newton methods. Multivariate interval Newton methods are analogous to univariate ones in the sense that they obey an iteration equation similar to equation (2), and in the sense that they have quadratic convergence properties and can be used to prove existence and uniqueness. However, multivariate interval Newton methods are complicated by the necessity to bound the solution set of a linear system of equations with interval coefficients.

Suppose now that f : R^{n} → R^{n}, suppose x is an interval vector (i.e. a box), and suppose that x̌ ∈ R^{n}. (If interval derivatives, rather than slope sets, are to be used, then further suppose that x̌ ∈ x.) Then a general form for multivariate interval Newton methods is

N(f, x, x̌) = x̌ + v,  (3)

Interval Newton methods mean value theorem interval analysis nonlinear systems existence uniqueness rigorous bounds error bounds branch and bound algorithms Interval analysis : Introduction, interval numbers and basic properties of interval arithmetic slope set Interval analysis: The slope interval Newton method univariate interval Newton operator

where v is an interval vector that contains all solutions v to point systems Av = −f(x̌), for A ∈ f′(x), where f′(x) is an interval extension to the Jacobi matrix of f over x. (Under certain conditions, f′ may be replaced by an interval slope matrix.) As with the univariate interval Newton method, under certain natural smoothness conditions,

• N(f, x, x̌) must contain all solutions x^{∗} ∈ x with f(x^{∗}) = 0. (Consequently, if N(f, x, x̌) ∩ x = ∅, then there are no solutions of f(x) = 0 in x.)

• For x containing a solution of f(x) = 0 and the widths of the components of x sufficiently small, the width of N(f, x, x̌) is roughly proportional to the square of the widths of the components of x.

• If N(f, x, x̌) ⊂ int(x), where int(x) represents the interior of x, then there is a unique solution of f(x) = 0 within N(f, x, x̌), and hence within x.

For details and further references, see [1, §1.5].

Finding the interval vector v in the iteration formula (3), that is, bounding the solution set to the interval linear system

f′(x)v = −f(x̌),

is a major aspect of the multivariate interval Newton method. Finding the narrowest possible intervals for the components of v is, in general, an NP-hard problem. (See Interval analysis: Linear equalities and inequalities and Interval analysis: Complexity analysis in interval problems.) However, procedures that are asymptotically good in the sense that the overestimation in v decreases as the square of the widths of the elements of f′ can be based on first preconditioning the interval matrix f′(x) by the inverse of its matrix of midpoints or by other special preconditioners (see [1, Ch. 3]), then applying the interval Gauss–Seidel method or interval Gaussian elimination. On existence-proving properties.

The existence-proving properties of interval Newton methods can be analyzed in the framework of classical fixed-point theory. See Interval analysis: Fixed point theorem, or [1, §1.5.2]. Of particular interest in this context is a variant interval Newton method, not fitting directly into the framework of formula (3), that is derived directly by considering the classical chord method (Newton method with fixed iteration matrix) as a fixed point iteration. Called the Krawczyk method, this method has various nice theoretical properties, but its image is usually not as narrow as other interval Newton methods. See Interval analysis: The Krawczyk method and [1, p. 56].

Uniqueness-proving properties of interval Newton methods are based on proving that each point matrix formed elementwise from the interval matrix f′(x) is non-singular. An example.

For an exampe of a multivariate interval Newton method, take

f_{1}(x) = x_{1}^{2} − x_{2}^{2} − 1
f_{2}(x) = 2x_{1}x_{2},

with

x = ( \begin{matrix}[0.9, 1.2] \\ [−0.1, 0.1] \end{matrix} ) ,  x̌ = ( \begin{matrix}1.05 \\ 0 \end{matrix} ) .

An interval extension of the Jacobi matrix for f is

f′(x) = ( \begin{matrix}2x_{1} & −2x_{2} \\ 2x_{2} & 2x_{1} \end{matrix} ) ,

and its value at x is

( \begin{matrix}[1.8, 2.4] & [−0.2, 0.2] \\ [−0.2, 0.2] & [1.8, 2.4] \end{matrix} ) .

The usual procedure (although not required in this special case) is to precondition the system

f′(x)v = −f(x̌),

say, by the inverse of the midpoint matrix

Y = ( \begin{matrix}1.05 & 0 \\ 0 & 1.05 \end{matrix} )^{−1} = ( \begin{matrix}0.95 & 0 \\ 0 & 0.95 \end{matrix} )

Interval analysis: Linear equalities and inequalities Interval analysis: Complexity analysis in interval problems preconditioning Interval analysis: Fixed point theorem Krawczyk method Interval analysis: The Krawczyk method

to obtain

Y f′(x)v = −Y f(x̌),

i.e.

( \begin{matrix}[1.71, 2.28] & [−.19, .19] \\ [−.19, .19] & [1.71, 2.28] \end{matrix} ) v = ( \begin{matrix}−.095 \\ 0 \end{matrix} ) .

The interval Gauss–Seidel method can then be used to compute sharper bounds on v = x − x̌,

beginning with v = ( \begin{matrix}[−0.15, 0.15] \\ [−0.1, 0.1] \end{matrix} ). That is,

ṽ_{1} = ( − 0.095 − [−0.19, 0.19]v_{2})/[1.71, 2.28]
⊂ [−0.06667, −0.03333].

Thus, the first component of N(f, x, x̌) is

x̌ + v ⊂ [0.9833, 1.0167].

In the second step of the interval Gauss–Seidel method,

ṽ_{2} = (0 − [−0.19, 0.19]ṽ_{1})/[1.71, 2.28]
⊂ [−0.007408, 0.007408],

so, rounded out to four digits, N(f, x, x̌) is computed to be

( \begin{matrix}[0.9833, 1.0167] \\ [−0.007408, 0.007408] \end{matrix} ) ⊂ ( \begin{matrix}[0.9, 1.2] \\ [−0.1, 0.1] \end{matrix} ) .

This last inclusion proves that there exists a unique solution to f(x) = 0 within x, and hence, within N(f, x, x̌). Furthermore, iteration of the procedure will result in bounds on the exact solution that become narrow quadratically. References

[1] Kearfott, R. B.: Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, Netherlands, 1996.

R. Baker Kearfott

Department of Mathematics University of Southwestern Louisiana

U.S.L. Box 4-1010, Lafayette, LA 70504-1010 USA

E-mail address: rbk@usl.edu

AMS1991SubjectClassification: 65G10, 65H20, 65K99. Key words and phrases: nonlinear systems of equations, automatic result verification, interval computations, global optimization.