Banach fixed point theorem

Banach fixed point theorem

The Banach fixed point theorem (also known as the contraction mapping theorem or contraction mapping principle) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certain self maps of metric spaces, and provides a constructive method to find those fixed points. The theorem is named after Stefan Banach (1892–1945), and was first stated by him in 1922.

The theorem

Let ("X", "d") be a non-empty complete metric space. Let "T" : "X" → "X" be a "contraction mapping" on "X", i.e: there is a nonnegative real number "q" < 1 such that:d(Tx,Ty) le qcdot d(x,y)for all "x", "y" in "X". Then the map "T" admits one and only one fixed point "x"* in "X" (this means "Tx"* = "x"*). Furthermore, this fixed point can be found as follows: start with an arbitrary element "x"0 in "X" and define an iterative sequence by "x""n" = "Tx""n"-1 for "n" = 1, 2, 3, ... This sequence converges, and its limit is "x"*. The following inequality describes the speed of convergence:

:d(x^*, x_n) leq frac{q^n}{1-q} d(x_1,x_0).

Equivalently,

:d(x^*, x_{n+1}) leq frac{q}{1-q} d(x_{n+1},x_n) and:d(x^*, x_{n+1}) leq q d(x_n,x^*).

The smallest such value of "q" is sometimes called the "Lipschitz constant".

Note that the requirement d("Tx", "Ty") < d("x", "y") for all unequal "x" and "y" is in general not enough to ensure the existence of a fixed point, as is shown by the map "T" : [1,&infin;) &rarr; [1,&infin;) with "T"("x") = "x" + 1/"x", which lacks a fixed point. However, if the space "X" is compact, then this weaker assumption does imply all the statements of the theorem.

When using the theorem in practice, the most difficult part is typically to define "X" properly so that "T" actually maps elements from "X" to "X", i.e. that "Tx" is always an element of "X".

Proof

Choose any x_0 in (X, d). For each n in {1, 2, ldots}, define x_n = Tx_{n-1},!. We claim that for all n in {1, 2, dots}, the following is true:

::d(x_{n+1}, x_n) leq q^n d(x_1, x_0).

To show this, we will proceed using induction. The above statement is true for the case n = 1,!, for

::d(x_{1+1}, x_1) = d(x_2, x_1) = d(Tx_1, Tx_0) leq qd(x_1, x_0).

Suppose the above statement holds for some k in {1, 2, ldots}. Then we have

::

The inductive assumption is used going from line three to line four. By the principle of mathematical induction, for all n in {1, 2, ldots}, the above claim is true.

Let epsilon > 0,!. Since 0 leq q < 1, we can find a large N in {1, 2, ldots} so that

::q^N < frac{epsilon(1-q)}{d(x_1, x_0)}.

Using the claim above, we have that for any m,!, n in {0, 1, ldots} with m > n geq N,

::

The inequality in line one follows from repeated applications of the triangle inequality; the series in line four is a geometric series with 0 leq q < 1 and hence it converges. The above shows that {x_n}_{ngeq 0} is a Cauchy sequence in (X, d),! and hence convergent by completeness. So let x^* = lim_{n oinfty} x_n. We make two claims: (1) x^*,! is a fixed point of T,!. That is, Tx^* = x^*,!; (2) x^*,! is the only fixed point of T,! in (X, d),!.

To see (1), we note that for any n in {0, 1, ldots},

::0 leq d(x_{n+1}, Tx^*) = d(Tx_n, Tx^*) leq q d(x_n, x^*).

Since qd(x_n, x^*) o 0 as n o infty, the squeeze theorem shows that lim_{n oinfty} d(x_{n+1}, Tx^*) = 0. This shows that x_n o Tx^* as n o infty. But x_n o x^* as n o infty, and limits are unique; hence it must be the case that x^* = Tx^*,!.

To show (2), we suppose that y,! also satisfies Ty = y,!. Then

::0 leq d(x^*, y) = d(Tx^*, Ty) leq q d(x^*, y).

Remembering that 0 leq q < 1, the above implies that 0 leq (1-q) d(x^*, y) leq 0, which shows that d(x^*, y) = 0,!, whence by positive definiteness, x^* = y,! and the proof is complete.

Applications

A standard application is the proof of the Picard-Lindelöf theorem about the existence and uniqueness of solutions to certain ordinary differential equations. The sought solution of the differential equation is expressed as a fixed point of a suitable integral operator which transforms continuous functions into continuous functions. The Banach fixed point theorem is then used to show that this integral operator has a unique fixed point.

Another application is the proof of the inverse function theorem.

Converses

Several converses of the Banach contraction principle exist. The following is due to Czesław Bessaga, from 1959:

Let f:X ightarrow X be a map of an abstract set such that each iterate "f" n has a unique fixed point. Let "q" be a real number, 0 &lt; q &lt; 1. Then there exists a complete metric on "X" such that "f" is contractive, and "q" is the contraction constant.

Generalizations

See the article on fixed point theorems in infinite-dimensional spaces for generalizations.

Limerick

The Banach fixed point theorem can be remembered by the following tongue-in-cheek limerick:

If "M"'s a complete metric space,
And non-empty, it's always the case,
If "f"'s a contraction,
Then under its action,
Exactly one point stays in place!

References

* Vasile I. Istratescu, "Fixed Point Theory, An Introduction", D.Reidel, the Netherlands (1981). ISBN 90-277-1224-7 See chapter 7.
* Andrzej Granas and James Dugundji, "Fixed Point Theory" (2003) Springer-Verlag, New York, ISBN 0-387-00173-5.
*cite book
author = Kirk, William A.; Khamsi, Mohamed A.
title = An Introduction to Metric Spaces and Fixed Point Theory
year = 2001
publisher = John Wiley, New York.
id = ISBN 978-0-471-41825-2

* William A. Kirk and Brailey Sims, "Handbook of Metric Fixed Point Theory" (2001), Kluwer Academic, London ISBN 0-7923-7073-2.
* [http://nfist.ist.utl.pt/~edgarc/wiki/index.php/Banach_fixed_point_theorem Proof of Banach fixed point theorem] on [http://bourbawiki.no-ip.org Bourbawiki] ----An earlier version of this article was posted on [http://planetmath.org/encyclopedia/BanachFixedPointTheorem.html Planet Math] . This article is open content.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Banach fixed-point theorem — In mathematics, the Banach fixed point theorem (also known as the contraction mapping theorem or contraction mapping principle) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of… …   Wikipedia

  • Fixed point theorem — In mathematics, a fixed point theorem is a result saying that a function F will have at least one fixed point (a point x for which F ( x ) = x ), under some conditions on F that can be stated in general terms. Results of this kind are amongst the …   Wikipedia

  • Brouwer fixed point theorem — In mathematics, the Brouwer fixed point theorem is an important fixed point theorem that applies to finite dimensional spaces and which forms the basis for several general fixed point theorems. It is named after Dutch mathematician L. E. J.… …   Wikipedia

  • Caristi fixed point theorem — In mathematics, the Caristi fixed point theorem (also known as the Caristi Kirk fixed point theorem) generalizes the Banach fixed point theorem for maps of a complete metric space into itself. Caristi s fixed point theorem is a variation of the… …   Wikipedia

  • Schauder fixed point theorem — The Schauder fixed point theorem is an extension of the Brouwer fixed point theorem to topological vector spaces such as Banach spaces. It asserts that if K is a compact, convex subset of a topological vector space and T is a continuous mapping… …   Wikipedia

  • Fixed point iteration — In numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions.More specifically, given a function f defined on the real numbers with real values and given a point x 0 in the domain of f, the fixed point… …   Wikipedia

  • Fixed point (mathematics) — Not to be confused with a stationary point where f (x) = 0. A function with three fixed points In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is a point[1] that is …   Wikipedia

  • Fixed point theorems in infinite-dimensional spaces — In mathematics, a number of fixed point theorems in infinite dimensional spaces generalise the Brouwer fixed point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations. The first… …   Wikipedia

  • Fixed-point theorems in infinite-dimensional spaces — In mathematics, a number of fixed point theorems in infinite dimensional spaces generalise the Brouwer fixed point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations. The first… …   Wikipedia

  • Inverse function theorem — In mathematics, specifically differential calculus, the inverse function theorem gives sufficient conditions for a function to be invertible in a neighborhood of a point in its domain. The theorem also gives a formula for the derivative of the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”