Banach fixed point theorem

related topics
{math, number, function}

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[1].

Contents

The theorem

Let (X, d) be a non-empty complete metric space. Let T : XX be a contraction mapping on X, i.e.: there is a nonnegative real number q < 1 such that

for all x, y in X. Then the map T admits one and only one fixed point x* in X (this means T(x*) = x*). Furthermore, this fixed point can be found as follows: start with an arbitrary element x0 in X and define an iterative sequence by xn = T(xn−1) for n = 1, 2, 3, ... This sequence converges, and its limit is x*. The following inequality describes the speed of convergence:

Equivalently,

and

Any such value of q is called a Lipschitz constant for T, and the smallest one is sometimes called "the best Lipschitz constant" of T.

Note that the requirement d(T(x), T(y)) < 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,∞) → [1,∞) with T(x) = x + 1/x, which lacks a fixed point. However, if the metric space X is compact, then this weaker assumption does imply the existence and uniqueness of a fixed point, that can be easily found as the limit of any sequence of iterations of T, as in the fixed point theorem for contractions, or also variationally, as a minimizer of d(x,T(x)) : indeed, a minimizer exists by compactness, and has to be a fixed point of T.

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 T(x) is always an element of X.

Proof

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

Full article ▸

related documents
Separable space
Cardinality
Probability space
Exact sequence
Mersenne prime
Division algebra
Constant of integration
Tychonoff space
Search algorithm
Linear equation
Separation axiom
Gamma function
Golomb coding
Symmetric group
Heapsort
Topological group
Analytic geometry
Julia set
Quine (computing)
Polytope
Blackboard bold
Euler's totient function
Antiderivative
Kruskal's algorithm
Mersenne twister
Automated theorem proving
Convex set
Power set
Local ring
Controllability