INTERVAL FIXED POINT THEORY

Introduction.

Interval methods (interval Newton methods and the Krawczyk method) can be used to prove existence and uniqueness of solutions to linear and nonlinear finite-dimensional and infinitedimensional systems, given floating-point approximations to such solutions. (See Interval analysis: The Krawczyk method, Interval analysis: Interval Newton methods, Interval analysis: The slope interval Newton method, and [6, 8].) In turn, these existenceproving interval operators have a close relationship with the classic theory of fixed-point iteration. This relationship is sketched here.

Classical fixed point theory and interval arithmetic.

Various fixed point theorems, applicable in finite or infinite dimensional spaces, state roughly that, if a mapping maps a set into itself, then that mapping has a fixed point within that set. For example, the Brouwer fixed point theorem states that, if D is homeomorphic to the closed unit ball in R^{n} and P is a continuous mapping such that P maps D into D, then P has a fixed point in D, that is, there is an x ∈ D with x = P (x).

Interval arithmetic can be naturally used to test the hypotheses of the Brouwer fixed point theorem. An interval extension P of P has the property that, if x is an interval vector with x ⊆ D, then P (x) contains the range {P (x) | x ∈ x}, and an interval extension P can be obtained simply by evaluating P with interval arithmetic. Furthermore, with outward roundings, this evaluation can be carried out so that the floating point intervals (whose end points are machine numbers) rigorously contain the actual range of P. (See Interval analysis: Introduction, interval numbers, and basic properties of interval arithmetic.) Thus, if P (x) ⊂ x, one can conclude that P has a fixed point within x.

Another fixed point theorem, Miranda’s theorem, follows from the Brouwer fixed point theorem, and is directly useful in theoretical studies of several interval methods. Miranda’s theorem is most easily stated with the notation of interval computations: Suppose x ⊂ R^{n} is an interval vector, and for each i, look at the lower i-th face x\underline{i} of x, defined to be the interval vector all of whose components except the i-th component are those of x, and whose i-th component is the lower bound \underline{x}_{i} of the i-th component x_{i} of x. Define the upper i-th face x\overline{i} of x similarly. Let P : x → R^{n}, P (x) = (P_{1}(x), P_{2}(x), …, P_{n}(x)) be continuous, and let P = (P_{1}, P_{2}, …, P_{n}) be any interval extension of P. Miranda’s theorem states that, if

P_{i}(x\underline{i})P_{i}(x\overline{i}) ≤ 0,  (1)

then P has a fixed point within x.

The Krawczyk method and fixed point theory.

Moore provided one of the earlier careful analyses of interval Newton methods in [5]. There, the Krawczyk method was analyzed as follows: The chord method is defined as

P (x) = x − Y f(x)  (2)

where the iteration matrix is normally taken to be Y = (f′(x̃))^{−1} for some Jacobi matrix f′(x̃) with x̃ ∈ x, where solutions of f(x) = 0, f : D ⊆ R^{n} → R^{n} are sought. A mean value extension (see Interval analysis : Interval functions and their enclosures) is then used:

Interval analysis: The Krawczyk method Interval analysis: Interval Newton methods Interval analysis: The slope interval Newton method Brouwer fixed point theorem outward roundings Interval analysis: Introduction, interval numbers, and basic properties of interval arithmetic Miranda’s theorem Krawczyk method mean value extension

P (x) ∈ P (x̌) + P′(x)(x − x̌),  whence
K(x, x̌) = P (x) (3)
= P (x̌) +  P′(x) (x − x̌)
= x̌ − Y f(x̌) + (I − Y f′(x))(x − x̌)

is an interval extension of P. Thus, the fact that the range of P obeys

{P (x) | x ∈ x} ⊆ P (x) = K(x, x̌)

coupled with the Brouwer fixed point theorem implies that, if

K(x, x̌) ⊆ x,

then there exists a fixed point of P, and hence solution x^{∗} ∈ K(x, x̌), f(x^{∗}) = 0.

By analyzing the norm ∥I − Y f′(x)∥, Moore further concludes, basically, that if

∥I − Y f′(x)∥ < 1,

then any solution x^{∗} ∈ x must be unique; for an exact statement and details, see [5]. Interval Newton methods and fixed point theory.

Traditional interval Newton methods are of the form

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

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 either an interval extension to the Jacobi matrix of f over x or an interval slope matrix; see Interval analysis: Interval Newton methods and Interval analysis: The slope interval Newton method. Theorem 5.1.7 in [7] asserts that, if N(f, x, x̌) ⊂ int(x), then there is a solution of f(x) = 0 within N(f, x, x̌), and this solution is unique within x. Classical fixed point theory is used in the succinct proof of this general theorem.

When the interval Gauss–Seidel method is used to find the solution set bounds v, a very clear correspondence to Miranda’s theorem can be set up. This is done in [3].

On uniqueness.

In classical fixed point theory, the contractive mapping theorem (a non-generic property) is often used to prove uniqueness. For example, suppose P is Lipschitz with Lipschitz constant L < 1, that is,

∥P (x) − P (y)∥ ≤ L ∥x − y∥ , for some L < 1. (5)

Then x = P (x) and y = P (y) implies ∥x − y∥ = ∥P (x) − P (y)∥ ≤ L ∥x − y∥ , which can only happen if x = y. (This argument appears in many elementary numerical analysis texts, such as [4].)

An alternate proof of uniqueness involves nonsingularity (i.e., regularity) of the map f for which we seek x with f(x) = 0. In particular if f(x) = Ax is linear, corresponding to a nonsingular matrix A, then f(x) = 0 and f(y) = 0 implies

0 = f(x) − f(y) = Ax − Ay = A(x − y), (6)

whence non-singularity of A implies x−y=0, i.e. x = y.

Without interval arithmetic, the argument in equation (6) cannot be generalized easily to nonlinear systems. Basically, invertibility implies uniqueness, and one must somehow prove invertibility. However, with interval arithmetic, uniqueness follows directly from an equation similar to (6), and regularity can be proven directly with an interval Newton method. In particular, if the image under the interval Newton method (4) is bounded, then every point matrix A ∈ f′(x) must be non-singular. (This is because the bounds on the solution set to the linear system f′(x)v = −f(x̌) must contain the set solutions to all systems of the form Av = −f(x̌), A ∈ f′(x).) Then, the mean value theorem implies that, for every x ∈ x, y ∈ x,

f(x) − f(y) = A(x − y) for some A ∈ f′(x). (7)

This is in spite of the fact that, in equation (7), A is in general not equal to any f′(x) for some x ∈ x. In fact, (7) follows from considering f componentwise:

Interval analysis : Interval functions and their enclosures Interval analysis: Interval Newton methods Interval analysis: The slope interval Newton method regularity

f_{i}(y) = f_{i}(x) + (∇f_{i}(c_{i}))^{T} (y − x),

for some c_{i}, different for each i, on the line connecting x and y; the matrix A ∈ f′(x) can be taken to have its i-th row equal to (∇f_{i}(c_{i}))^{T}. Thus, because of the non-singularity of A in (7), f(x) = 0, f(y) = 0 implies 0 = A(x − y) and x = y.

Summarizing the actual results,

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

where N(f, x, x̌) is as in equation (4) and int(x) represents the interior of x, then classical fixedpoint theory combined with properties of interval arithmetic implies that there is a unique solution to f(x) = 0 in N(f, x, x̌), and hence in x.

If slope matrices are used in place of an interval Jacobi matrix f′(x), then equation (7) no longer holds, and condition (8) no longer implies uniqueness. However, a two-stage process, involving evaluation of an interval derivative over a small box containing the solution and evaluation of a slope matrix over a large box containing the small box, leads to an even more powerful existence and uniqueness test than using interval Jacobi matrices alone. This technique perhaps originally appeared in [9]. An statement and proof of the main theorem can also be found in [3, Theorem 1.23, p. 64]. On infinite-dimensional problems.

Many problems in infinite-dimensional spaces (e.g. certain variational optimization problems) can be written in the form of a compact operator fixed point equation, x = P (x), where P : S → S is some compact operator operating on some normed linear space S. In many such cases, P is approximated numerically from a finitedimensional space of basis functions {ϕ_{i}}_{i=1}^{n} (e.g. splines or finite element basis functions ϕ_{i}), and the approximation error can be computed. That is, P (x) = P_{n}(y) + R_{n}(y), where y ∈ R^{n} is an approximation to x ∈ S, and R_{n}(y) is the error that is computable as a function of y. Thus, a fixed point iteration can be set up of the form

y ← P̃_{n}(y) ≡ P_{n}(y) + R_{n}(y),  (9)

where y ∈ R^{n}. (The dimension n can be increased as iteration proceeds.)

For equation (9), the Schauder fixed point theorem is an analogue of the Brouwer fixed point theorem; see [1, p. 154]. Furthermore, interval extensions can be provided to both P_{n} and R_{n}, so that an analogue to finite-dimensional computational fixed point theory exists. In particular, if

P̃_{n}(y) ⊂ int(y),  (10)

then there exists a fixed point of P within the ball in S centered at the midpoint of y and with radius equal to the radius of y. (For these purposes,

y = ∑_{i=1}^{n} a_{i}ϕ_{i}

can be identified with the interval vector (a_{1}, …, a_{n})^{T} corresponding to the coefficients in the expansion.) For details, see [6, Chapter 15]. Also see [2] for a theoretical development and various examples worked out in detail. References

[1] Istrăţescu, V. I.: Fixed Point Theory: An Introduction, Reidel, Hingham, MA, 1981.

[2] Kaucher, E. W., and Miranker, W. L.: Self-Validating Numerics for Function Space Problems, Academic Press, Orlando, 1984.

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

[4] Kincaid, D., and Cheney, W.: Numerical Analysis, Brooks/Cole, Monterey, California, 1991.

[5] Moore, R. E.: ‘A Test for Existence of Solutions to Nonlinear Systems’, SIAM J. Numer. Anal. 14, no. 4 (September 1977), 611–615.

[6] Moore, R. E.: Computational Functional Analysis, Horwood, Chichester, England, 1985.

[7] Neumaier, A.: Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, England, 1990.

[8] Plum, M.: ‘Inclusion Methods for Elliptic Boundary Value Problems’, in J. Herzberger (ed.): Topics in Validated Computations, Studies in Computational Mathematics, North-Holland, 1994, pp. 323–380.

[9] Rump, S. M.: ‘Verification Methods for Dense and Sparse Systems of Equations’, in J. Herzberger (ed.): Topics in Validated Computations, Elsevier Science Publishers, 1994, pp. 63–135.

Schauder fixed point theorem

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. Key words and phrases: fixed point iteration, automatic result verification, interval computations, global optimization.