Banach fixed point theorem: Definition from Answers.com

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 The theorem
2 Proof
3 Applications
4 Converses
5 Generalizations
6 Limerick
7 References

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 q\cdot 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₀ 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^*).$

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(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,∞) → [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 unicity 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 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

$d(x_{(k + 1) + 1}, x_{k + 1})\,\!$	$= d(x_{k + 2}, x_{k + 1})\,\!$
	$= d(Tx_{k + 1}, Tx_k)\,\!$
	$\leq q d(x_{k + 1}, x_k)$
	$\leq q \cdot q^kd(x_1, x_0)$
	$= q^{k + 1}d(x_1, x_0).\,\!$

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$ ,

$d\left(x_m, x_n\right)$	$\leq d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + \cdots + d(x_{n+1}, x_n)$
	$\leq q^{m-1}d(x_1, x_0) + q^{m-2}d(x_1, x_0) + \cdots + q^nd(x_1, x_0)$
	$= d(x_1, x_0)q^n \cdot \sum_{k=0}^{m-n-1} q^k$
	$< d(x_1, x_0)q^n \cdot \sum_{k=0}^\infty q^k$
	$= d(x_1, x_0)q^n \frac{1}{1-q}$
	$= q^n \frac{d(x_1, x_0)}{1-q}$
	$< \frac{\epsilon(1-q)}{d(x_1, x_0)}\cdot\frac{d(x_1, x_0)}{1-q}$
	$= \epsilon.\,\!$

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\}_{n\geq 0}$ is a Cauchy sequence in $(X, d)\,\!$ and hence convergent by completeness. So let $x^* = \lim_{n\to\infty} 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^*) \to 0$ as $n \to \infty$ , the squeeze theorem shows that $\lim_{n\to\infty} d(x_{n+1}, Tx^*) = 0$ . This shows that $x_n \to Tx^*$ as $n \to \infty$ . But $x_n \to x^*$ as $n \to \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.

One consequence of the Banach fixed point theorem is that small Lipschitz perturbation of the identity are bi-lipshitz homeomorphisms. Let $Ω$ an open set of a Banach space $E$ ; let $I:\Omega\to E$ denote the identity (inclusion) map and let $g:\Omega\to E$ be a Lipschitz map of constant k<1. Then (i) $Ω': = (I + g)(Ω)$ is an open subset of $E$ :precisely, for any $x\in\Omega$ such that $B(x,r)\subset\Omega$ one has $\textstyle B\left((I+g)(x),\, r(1-k)\right)\subset\Omega'$ ; (ii) $I+g:\Omega\to\Omega'$ is a bi-lipschitz homeomorphism; precisely, $(I + g) - 1$ is still of the form $I+h:\Omega'\to\Omega$ , with $h$ a Lipshitz map of constant $k / (1 - k).$

A refinement of this argument yields 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\colon X \to X$ be a map of an abstract set such that each iterate ƒⁿ has a unique fixed point. Let q be a real number, 0 < q < 1. Then there exists a complete metric on X such that ƒ is contractive, and q is the contraction constant.

Generalizations

There are a number of generalizations as immediate corollaries , which are of some interest for the sake of applications. Let $T:X\to X$ a map on a complete non-empty metric space.

Assume that some iterate $T n$ of T is a contraction. Then T has a unique fixed point.
Assume that for all $x$ and $y$ in $X$ , $\sum_n d(T^n(x),T^n(y))<\infty.$ Then T has a unique fixed point.

However, in most applications the existence and unicity of a fixed point can be shown directly with the standard Banach fixed point theorem, by a suitable choice of the metric that makes the map T a contraction. Indeed, the above result by Bessaga strongly suggests to look for such a metric. See also 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.
Kirk, William A.; Khamsi, Mohamed A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. John Wiley, New York.. 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.
Proof of Banach fixed point theorem on Bourbawiki

An earlier version of this article was posted on Planet Math. This article is open content.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Contraction principle
	Fixed point iteration
	Contraction mapping

	Using krasnoselskii fixed point theorem prove fixed point of a operator in a banach space? Read answer...
	When were fixed point telephones invented? Read answer...
	What is fixed point chart in television? Read answer...

	Illustrate with an example that in banach fixd point theorem completeness is essential and can not be omitted?
	What is the history of mid point theorem?
	What is an example of a corner point theorem?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Banach fixed point theorem". Read more

Banach fixed point theorem

Contents