Banach fixed-point theorem

The Banach fixed point theorem 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 Banach 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

${\displaystyle d(Tx,Ty)\leq 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:

${\displaystyle d(x^{*},x_{n})\leq {\frac {q^{n}}{1-q}}d(x_{1},x_{0})}$ .

Equivalently,

${\displaystyle d(x^{*},x_{n+1})\leq {\frac {q}{1-q}}d(x_{n+1},x_{n})}$ 

and

${\displaystyle d(x^{*},x_{n+1})\leq qd(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,∞) → [1,∞) 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 ${\displaystyle x_{0}\in (X,d)}$ . For each ${\displaystyle n\in \{1,2,\ldots \}}$ , define ${\displaystyle x_{n}=Tx_{n-1}\,}$ . We claim that for all ${\displaystyle n\in \{1,2,\dots \}}$ , the following is true:

${\displaystyle 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 ${\displaystyle n=1\,}$ , for

${\displaystyle 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 ${\displaystyle k\in \{1,2,\ldots \}}$ . Then we have

${\displaystyle d(x_{(k+1)+1},x_{k+1})\,}$	${\displaystyle =d(x_{k+2},x_{k+1})\,}$
	${\displaystyle =d(Tx_{k+1},Tx_{k})\,}$
	${\displaystyle \leq qd(x_{k+1},x_{k})}$
	${\displaystyle \leq q\cdot q^{k}d(x_{1},x_{0})}$
	${\displaystyle =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 ${\displaystyle n\in \{1,2,\ldots \}}$ , the above claim is true.

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

${\displaystyle q^{N}<{\frac {\epsilon (1-q)}{d(x_{1},x_{0})}}}$ .

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

${\displaystyle d\left(x_{m},x_{n}\right)}$	${\displaystyle \leq d(x_{m},x_{m-1})+d(x_{m-1},x_{m-2})+\cdots +d(x_{n+1},x_{n})}$
	${\displaystyle \leq q^{m-1}d(x_{1},x_{0})+q^{m-2}d(x_{1},x_{0})+\cdots +q^{n}d(x_{1},x_{0})}$
	${\displaystyle =d(x_{1},x_{0})q^{n}\cdot \sum _{k=0}^{m-n-1}q^{k}}$
	${\displaystyle <d(x_{1},x_{0})q^{n}\cdot \sum _{k=0}^{\infty }q^{k}}$
	${\displaystyle =d(x_{1},x_{0})q^{n}{\frac {1}{1-q}}}$
	${\displaystyle =q^{n}{\frac {d(x_{1},x_{0})}{1-q}}}$
	${\displaystyle <{\frac {\epsilon (1-q)}{d(x_{1},x_{0})}}\cdot {\frac {d(x_{1},x_{0})}{1-q}}}$
	${\displaystyle =\epsilon \,}$ .

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

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

${\displaystyle 0\leq d(x_{n+1},Tx^{*})=d(Tx_{n},Tx^{*})\leq qd(x_{n},x^{*})}$ .

Since ${\displaystyle qd(x_{n},x^{*})\to 0}$  as ${\displaystyle n\to \infty }$ , the squeeze theorem shows that ${\displaystyle \lim _{n\to \infty }d(x_{n+1},Tx^{*})=0}$ . This shows that ${\displaystyle x_{n}\to Tx^{*}}$  as ${\displaystyle n\to \infty }$ . But ${\displaystyle x_{n}\to x^{*}}$  as ${\displaystyle n\to \infty }$ , and limits are unique; hence it must be the case that ${\displaystyle x^{*}=Tx^{*}\,}$ .

To show (2), we suppose that ${\displaystyle y\,}$  also satisfies ${\displaystyle Ty=y\,}$ . Then

${\displaystyle 0\leq d(x^{*},y)=d(Tx^{*},Ty)\leq qd(x^{*},y)}$ .

Remembering that ${\displaystyle 0\leq q<1}$ , the above implies that ${\displaystyle 0\leq (1-q)d(x^{*},y)\leq 0}$ , which shows that ${\displaystyle d(x^{*},y)=0\,}$ , whence by positive definiteness, ${\displaystyle 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.

Converses

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

Let ${\displaystyle f:X\rightarrow X}$  be a map of an abstract set such that each iterate f ⁿ has a unique fixed point. Let q be a real number, 0 < q < 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.

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.
• William A. Kirk and Brailey Sims, Handbook of Metric Fixed Point Theory (2001), Kluwer Academic, London ISBN 0-7923-7073-2.

---

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