Definitions

# 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 : XX be a contraction mapping on X, i.e: there is a nonnegative real number q < 1 such that

$d\left(Tx,Ty\right) le qcdot d\left(x,y\right)$
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 x0 in X and define an iterative sequence by xn = Txn-1 for n = 1, 2, 3, ... This sequence converges, and its limit is x*. The following inequality describes the speed of convergence:

$d\left(x^*, x_n\right) leq frac\left\{q^n\right\}\left\{1-q\right\} d\left(x_1,x_0\right).$

Equivalently,

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

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 $x_0 in \left(X, d\right)$. For each $n in \left\{1, 2, ldots\right\}$, define $x_n = Tx_\left\{n-1\right\},!$. We claim that for all $n in \left\{1, 2, dots\right\}$, the following is true:

$d\left(x_\left\{n+1\right\}, x_n\right) leq q^n d\left(x_1, x_0\right)$.

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

$d\left(x_\left\{1+1\right\}, x_1\right) = d\left(x_2, x_1\right) = d\left(Tx_1, Tx_0\right) leq qd\left(x_1, x_0\right)$.

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

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

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

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

$q^N < frac\left\{epsilon\left(1-q\right)\right\}\left\{d\left(x_1, x_0\right)\right\}$.

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

$dleft\left(x_m, x_nright\right)$ $leq d\left(x_m, x_\left\{m-1\right\}\right) + d\left(x_\left\{m-1\right\}, x_\left\{m-2\right\}\right) + cdots + d\left(x_\left\{n+1\right\}, x_n\right)$
$leq q^\left\{m-1\right\}d\left(x_1, x_0\right) + q^\left\{m-2\right\}d\left(x_1, x_0\right) + cdots + q^nd\left(x_1, x_0\right)$
$= d\left(x_1, x_0\right)q^n cdot sum_\left\{k=0\right\}^\left\{m-n-1\right\} q^k$
$< d\left(x_1, x_0\right)q^n cdot sum_\left\{k=0\right\}^infty q^k$
$= d\left(x_1, x_0\right)q^n frac\left\{1\right\}\left\{1-q\right\}$
$= q^n frac\left\{d\left(x_1, x_0\right)\right\}\left\{1-q\right\}$
$< frac\left\{epsilon\left(1-q\right)\right\}\left\{d\left(x_1, x_0\right)\right\}cdotfrac\left\{d\left(x_1, x_0\right)\right\}\left\{1-q\right\}$
$= 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 $\left\{x_n\right\}_\left\{ngeq 0\right\}$ is a Cauchy sequence in $\left(X, d\right),!$ and hence convergent by completeness. So let $x^* = lim_\left\{ntoinfty\right\} 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 $\left(X, d\right),!$.

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

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

Since $qd\left(x_n, x^*\right) to 0$ as $n to infty$, the squeeze theorem shows that $lim_\left\{ntoinfty\right\} d\left(x_\left\{n+1\right\}, Tx^*\right) = 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\left(x^*, y\right) = d\left(Tx^*, Ty\right) leq q d\left(x^*, y\right)$.

Remembering that $0 leq q < 1$, the above implies that $0 leq \left(1-q\right) d\left(x^*, y\right) leq 0$, which shows that $d\left(x^*, y\right) = 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:Xrightarrow 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 < 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.

## 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