Banach fixed-point theorem

Proof

Let ${\displaystyle x_0\in X}$ be arbitrary and define a sequence ${\displaystyle (x_n{)}_{n\in \mathbb{N}}}$ by setting ${\displaystyle x_n=T(x_{n-1})}$. We first note that for all ${\displaystyle n\in \mathbb{N},}$ we have the inequality

${\displaystyle d(x_{n+1},x_n)\le q^{n}d(x_1,x_0).}$

This follows by induction on ${\displaystyle n}$, using the fact that ${\displaystyle T}$ is a contraction mapping. Then we can show that ${\displaystyle (x_n{)}_{n\in \mathbb{N}}}$ is a Cauchy sequence. In particular, let ${\displaystyle m,n\in \mathbb{N}}$ such that ${\displaystyle m>n}$:

${\displaystyle \begin{array}{cc}d(x_m,x_n)& \le d(x_m,x_{m-1})+d(x_{m-1},x_{m-2})+\cdots +d(x_{n+1},x_n)\\ & \le q^{m-1}d(x_1,x_0)+q^{m-2}d(x_1,x_0)+\cdots +q^{n}d(x_1,x_0)\\ & =q^{n}d(x_1,x_0)\sum _{k=0}^{m-n-1}{q}^k\\ & \le q^{n}d(x_1,x_0)\sum _{k=0}^{\mathrm{\infty }}{q}^k\\ & =q^{n}d(x_1,x_0)\left(\frac{1}{1-q}\right).\end{array}}$

Let ${\displaystyle \epsilon >0}$ be arbitrary. Since ${\displaystyle q\in [0,1)}$, we can find a large ${\displaystyle N\in \mathbb{N}}$ so that

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

Therefore, by choosing ${\displaystyle m}$ and ${\displaystyle n}$ greater than ${\displaystyle N}$ we may write:

${\displaystyle d(x_m,x_n)\le q^{n}d(x_1,x_0)\left(\frac{1}{1-q}\right)<\left(\frac{\epsilon (1-q)}{d(x_1,x_0)}\right)d(x_1,x_0)\left(\frac{1}{1-q}\right)=\epsilon .}$

This proves that the sequence ${\displaystyle (x_n{)}_{n\in \mathbb{N}}}$ is Cauchy. By completeness of ${\displaystyle (X,d)}$, the sequence has a limit ${\displaystyle x^{\ast }\in X.}$ Furthermore, ${\displaystyle x^{\ast }}$ must be a fixed point of ${\displaystyle T}$:

${\displaystyle x^{\ast }=\underset{n\to \mathrm{\infty }}{lim}{x}_n=\underset{n\to \mathrm{\infty }}{lim}T(x_{n-1})=T\left(\underset{n\to \mathrm{\infty }}{lim}{x}_{n-1}\right)=T(x^{\ast }).}$

As a contraction mapping, ${\displaystyle T}$ is continuous, so bringing the limit inside ${\displaystyle T}$ was justified. Lastly, ${\displaystyle T}$ cannot have more than one fixed point in ${\displaystyle (X,d)}$, since any pair of distinct fixed points ${\displaystyle p_1}$ and ${\displaystyle p_2}$ would contradict the contraction of ${\displaystyle T}$:

$${\displaystyle d(p_1,p_2)=d(T(p_1),T(p_2))\le qd(p_1,p_2)<d(p_1,p_2),}$$

where the equality is due to ${\displaystyle p_1,p_2}$ being fixed points of ${\displaystyle T}$, the first inequality is due to ${\displaystyle T}$ being a contraction mapping, and the last inequality is due to ${\displaystyle q<1}$ and ${\displaystyle d(p_1,p_2)>0}$ as ${\displaystyle p_1\ne p_2}$.

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 on the space of continuous functions under the uniform norm. 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 perturbations of the identity are bi-lipschitz homeomorphisms. Let ${\displaystyle \mathrm{\Omega }}$ be an open set of a Banach space ${\displaystyle E}$; let ${\displaystyle I:\mathrm{\Omega }\to E}$ denote the identity (inclusion) map and let ${\displaystyle g:\mathrm{\Omega }\to E}$ be a Lipschitz map of constant ${\displaystyle k<1}$. Then

1. ${\displaystyle {\mathrm{\Omega }}^{\prime }:=(I+g)\mathrm{\Omega }}$ is an open subset of ${\displaystyle E}$: precisely, for any ${\displaystyle x}$ in ${\displaystyle \mathrm{\Omega }}$ such that ${\displaystyle B(x,r)\subset \mathrm{\Omega }}$ one has ${\displaystyle B((I+g)(x),r(1-k))\subset {\mathrm{\Omega }}^{\prime }}$;
2. ${\displaystyle I+g:\mathrm{\Omega }\to {\mathrm{\Omega }}^{\prime }}$ is a bi-Lipschitz homeomorphism;

precisely, ${\displaystyle (I+g{)}^{-1}}$ is still of the form ${\displaystyle I+h:\mathrm{\Omega }\to {\mathrm{\Omega }}^{\prime }}$ with ${\displaystyle h}$ a Lipschitz map of constant ${\displaystyle k/(1-k)}$. A direct consequence of this result yields the proof of the inverse function theorem.

• It can be used to give sufficient conditions under which Newton's method of successive approximations is guaranteed to work, and similarly for Chebyshev's third-order method.
• It can be used to prove existence and uniqueness of solutions to integral equations.
• It can be used to give a proof to the Nash embedding theorem.
• It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of reinforcement learning.
• It can be used to prove existence and uniqueness of an equilibrium in Cournot competition, and other dynamic economic models.
• If X is a vector space, an alternative method for iteratively approximating the fixed point is to apply Newton's method to solve ${\displaystyle f(x)-x=0}$.
• One real world illustration of the theorem is the following demonstration that can often be understood with little formal mathematics background. Suppose a person holds a sheet of paper on which is printed a map of the city they are in (or a map of their country, or a blueprint of the building they are in, etc.). The person then places the map on the floor. This can be considered to represent a continuous function from the city to itself and is clearly a contraction. Therefore, there is exactly one point in the map that lies directly above the point that it represents. The accuracy of the map and projection method do not matter as long as the map is complete and all points represented are moved closer together in the projection. What's more, should the person scrunch the map up into a ball and flatten it on the floor, as long as the paper does not tear, this will still be a contraction and the same conclusion can be reached.

Converses

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

Let ${\displaystyle f:X\to X}$ be a map of an abstract set such that each iterate ${\displaystyle f^n}$ has a unique fixed point. Let ${\displaystyle q\in (0,1)}$, then there exists a complete metric on ${\displaystyle X}$ such that ${\displaystyle f}$ is contractive, and ${\displaystyle q}$ is the contraction constant.

Indeed, very weak assumptions suffice to obtain such a kind of converse. For example if ${\displaystyle f:X\to X}$ is a map on a T₁ topological space with a unique fixed point ${\displaystyle a}$, such that for each ${\displaystyle x\in X}$ we have ${\displaystyle f^n(x)\to a}$, then there already exists a metric on ${\displaystyle X}$ with respect to which ${\displaystyle f}$ satisfies the conditions of the Banach contraction principle with contraction constant ${\displaystyle 1/2}$. In this case the metric is in fact an ultrametric.

Generalizations

There are a number of generalizations (some of which are immediate corollaries).

Let ${\displaystyle T:X\to X}$ be a map on a complete non-empty metric space. Then, for example, some generalizations of the Banach fixed-point theorem are:

• Assume that some iterate ${\displaystyle T^n}$ of ${\displaystyle T}$ is a contraction. Then ${\displaystyle T}$ has a unique fixed point.
• Assume that for each ${\displaystyle n}$, there exist ${\displaystyle c_n}$ such that ${\displaystyle d(T^n(x),T^n(y))\le c_{n}d(x,y)}$ for all ${\displaystyle x}$ and ${\displaystyle y}$, and that

${\displaystyle {\sum }_n{c}_n<\mathrm{\infty }.}$

Then ${\displaystyle T}$ has a unique fixed point.

In applications, the existence and uniqueness of a fixed point often can be shown directly with the standard Banach fixed point theorem, by a suitable choice of the metric that makes the map ${\displaystyle 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.

In a non-empty compact metric space, any function ${\displaystyle T}$ satisfying ${\displaystyle d(T(x),T(y))<d(x,y)}$ for all distinct ${\displaystyle x,y}$, has a unique fixed point. The proof is simpler than the Banach theorem, because the function ${\displaystyle d(T(x),x)}$ is continuous, and therefore assumes a minimum, which is easily shown to be zero.

A different class of generalizations arise from suitable generalizations of the notion of metric space, e.g. by weakening the defining axioms for the notion of metric. Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science.

Example

An application of the Banach fixed-point theorem and fixed-point iteration can be used to quickly obtain an approximation of ${\displaystyle \pi }$ with high accuracy. Consider the function ${\displaystyle f(x)=x+\sin (x)}$. It can be verified that ${\displaystyle \pi }$ is a fixed point of ${\displaystyle f}$, and that ${\displaystyle f}$ maps the interval ${\displaystyle \left[\frac{3\pi }{4},\frac{5\pi }{4}\right]}$ to itself. Moreover, ${\displaystyle f^{\mathrm{\prime }}(x)=1+\cos (x)}$, and it can be verified that

${\displaystyle 0⩽1+\cos (x)⩽1-\frac{1}{\sqrt{2}}\approx 0.292893<1}$

on this interval. Therefore, by an application of the mean value theorem, ${\displaystyle f}$ has a Lipschitz constant less than ${\displaystyle 1}$ (namely ${\displaystyle 1-1/\sqrt{2}}$). Applying the Banach fixed-point theorem shows that the fixed point ${\displaystyle \pi }$ is the unique fixed point on the interval, allowing for fixed-point iteration to be used.

For example, the value ${\displaystyle 3}$ may be chosen to start the fixed-point iteration, as ${\displaystyle \frac{3\pi }{4}⩽3⩽\frac{5\pi }{4}}$. The Banach fixed-point theorem may be used to conclude that

${\displaystyle \pi =f(f(f(\cdots f(3)\cdots )))=(f\circ \cdots \circ f)(3).}$

Applying ${\displaystyle f}$ to ${\displaystyle 3}$ only thrice already yields an expansion of ${\displaystyle \pi }$ accurate up to ${\displaystyle 33}$ digits:

${\displaystyle \begin{array}{ccccc}\mathrm{id}(3)& =& f^{[0]}(3)& =& \mathbf{3.}0000000000000000000000000000000000\cdots \\ f(3)& =& f^{[1]}(3)& =& \mathbf{3.141}1200080598672221007448028081103\cdots \\ f(f(3))& =& f^{[2]}(3)& =& \mathbf{3.1415926535}721955587348885681408797\cdots \\ f(f(f(3)))& =& f^{[3]}(3)& =& \mathbf{3.14159265358979323846264338327950}20\cdots \end{array}}$