Banach fixed-point theorem

Definition. Let $(X,\; d)$ be a metric space. Then a map $T\; :\; X\; \backslash to\; X$ is called a contraction mapping on X if there exists $q\; \backslash in\; [0,\; 1)$ such that

:$d(T(x),T(y))\; \backslash le\; q\; d(x,y)$

for all $x,\; y\; \backslash in\; X.$

Banach fixed-point theorem. Let $(X,\; d)$ be a non-empty complete metric space with a contraction mapping $T\; :\; X\; \backslash to\; X.$ Then T admits a unique fixed-point $x^*$ in X (i.e. $T(x^*)\; =\; x^*$). Furthermore, $x^*$ can be found as follows: start with an arbitrary element $x\_0\; \backslash in\; X$ and define a sequence $(x\_n)\_\{n\backslash in\backslash mathbb\; N\}$ by $x\_n\; =\; T(x\_\{n-1\})$ for $n\; \backslash geq\; 1.$ Then $\backslash lim\_\{n\; \backslash to\; \backslash infty\}\; x\_n\; =\; x^*$.

Remark 1. The following inequalities are equivalent and describe the speed of convergence:

:$$

\begin{align}

d(x^*, x_n) & \leq \frac{q^n}{1-q} d(x_1,x_0), \\[5pt]

d(x^*, x_{n+1}) & \leq \frac{q}{1-q} d(x_{n+1},x_n), \\[5pt]

d(x^*, x_{n+1}) & \leq q d(x^*,x_n).

\end{align}

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

Remark 2.

:$T\; :\; [1,\backslash infty)\; \backslash to\; [1,\backslash infty),\; \backslash ,\backslash ,\; T(x)=x+\backslash tfrac\{1\}\{x\}\backslash ,,$

which lacks a fixed point. However, if $X$ is compact, then this weaker assumption does imply the existence and uniqueness of a fixed point, that can be easily found as a minimizer of $d(x,T(x))$, indeed, a minimizer exists by compactness, and has to be a fixed point of $T.$ It then easily follows that the fixed point is the limit of any sequence of iterations of $T.$

Remark 3. When using the theorem in practice, the most difficult part is typically to define $X$ properly so that $T(X)\; \backslash subseteq\; X.$

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

:$d(x\_\{n+1\},\; x\_n)\; \backslash le\; q^n\; d(x\_1,\; x\_0).$

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

: $\backslash begin\{align\}$

d(x_m, x_n) & \leq d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + \cdots + d(x_{n+1}, x_n) \\[5pt]

& \leq q^{m-1}d(x_1, x_0) + q^{m-2}d(x_1, x_0) + \cdots + q^nd(x_1, x_0) \\[5pt]

& = q^n d(x_1, x_0) \sum_{k=0}^{m-n-1} q^k \\[5pt]

& \leq q^n d(x_1, x_0) \sum_{k=0}^\infty q^k \\[5pt]

& = q^n d(x_1, x_0) \left ( \frac{1}{1-q} \right ).

\end{align}

Let $\backslash varepsilon\; >\; 0$ be arbitrary. Since $q\; \backslash in\; [0,1)$, we can find a large $N\; \backslash in\; \backslash N$ so that

:

Therefore, by choosing $m$ and $n$ greater than $N$ we may write:

:

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

:$x^*=\backslash lim\_\{n\backslash to\backslash infty\}\; x\_n\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; T(x\_\{n-1\})\; =\; T\backslash left(\backslash lim\_\{n\backslash to\backslash infty\}\; x\_\{n-1\}\; \backslash right)\; =\; T(x^*).$

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

:$d(T(p\_1),T(p\_2))\; =\; d(p\_1,p\_2)\; >\; q\; d(p\_1,\; p\_2).$

• 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 Ω be an open set of a Banach space E; let {{nobr|I : Ω → E}} denote the identity (inclusion) map and let g : Ω → E be a Lipschitz map of constant k < 1. Then

1. Ω′ := (I + g)(Ω) is an open subset of E: precisely, for any x in Ω such that {{nobr|B(x, r) ⊂ Ω}} one has {{nobr|B((I + g)(x), r(1 − k)) ⊂ Ω′;}}
2. I + g : Ω → Ω′ is a bi-Lipschitz homeomorphism;

: precisely, (I + g)⁻¹ is still of the form {{nobr|I + h : Ω → Ω′}} with h a Lipschitz map of constant 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.{{cite journal |first=Matthias|last=Günther|title=Zum Einbettungssatz von J. Nash | trans-title=On the embedding theorem of J. Nash | language=de | journal=Mathematische Nachrichten|volume= 144 |year=1989|pages= 165–187|doi=10.1002/mana.19891440113 | mr=1037168}}
• It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of reinforcement learning.{{cite book |first1=Frank L. |last1=Lewis |first2=Draguna |last2=Vrabie |first3=Vassilis L. |last3=Syrmos |title=Optimal Control |chapter=Reinforcement Learning and Optimal Adaptive Control |location=New York |publisher=John Wiley & Sons |year=2012 |isbn=978-1-118-12272-3 |pages=461–517 [p. 474] |chapter-url=https://books.google.com/books?id=U3Gtlot_hYEC&pg=PA474 }}
• It can be used to prove existence and uniqueness of an equilibrium in Cournot competition,{{cite journal |first1=Ngo Van |last1=Long |first2=Antoine |last2=Soubeyran |title=Existence and Uniqueness of Cournot Equilibrium: A Contraction Mapping Approach |journal=Economics Letters |volume=67 |issue=3 |year=2000 |pages=345–348 |doi=10.1016/S0165-1765(00)00211-1 |url=https://www.cirano.qc.ca/pdf/publication/99s-22.pdf |archive-url=https://web.archive.org/web/20041230225125/http://www.cirano.qc.ca/pdf/publication/99s-22.pdf |archive-date=2004-12-30 |url-status=live }} and other dynamic economic models.{{cite book |first1=Nancy L. |last1=Stokey|author1-link=Nancy Stokey |first2=Robert E. Jr. |last2=Lucas |author-link2=Robert Lucas Jr. |title=Recursive Methods in Economic Dynamics |location=Cambridge |publisher=Harvard University Press |year=1989 |isbn=0-674-75096-9 |pages=508–516 |url=https://books.google.com/books?id=BgQ3AwAAQBAJ&pg=PA508 }}

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

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

Indeed, very weak assumptions suffice to obtain such a kind of converse. For example if $f\; :\; X\; \backslash to\; X$ is a map on a T₁ topological space with a unique fixed point a, such that for each $x\; \backslash in\; X$ we have fⁿ(x) → a, then there already exists a metric on X with respect to which f satisfies the conditions of the Banach contraction principle with contraction constant 1/2.{{cite journal |first1=Pascal |last1=Hitzler | author-link1=Pascal Hitzler|first2=Anthony K. |last2=Seda |title=A 'Converse' of the Banach Contraction Mapping Theorem |journal=Journal of Electrical Engineering |volume=52 |issue=10/s |year=2001 |pages=3–6 }} In this case the metric is in fact an ultrametric.

There are a number of generalizations (some of which are immediate corollaries).{{cite book |first=Abdul |last=Latif |title=Topics in Fixed Point Theory |pages=33–64 |chapter=Banach Contraction Principle and its Generalizations |publisher=Springer |year=2014 |doi=10.1007/978-3-319-01586-6_2 |isbn=978-3-319-01585-9 }}

Let T : X → 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 Tⁿ of T is a contraction. Then T has a unique fixed point.
• Assume that for each n, there exist c_n such that d(Tⁿ(x), Tⁿ(y)) ≤ c_nd(x, y) for all x and y, and that

::

:Then 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 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 $T$ satisfying

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.{{cite book |first1=Pascal |last1=Hitzler | author-link1=Pascal Hitzler|first2=Anthony |last2=Seda |title=Mathematical Aspects of Logic Programming Semantics |publisher=Chapman and Hall/CRC |year=2010 |isbn=978-1-4398-2961-5 }} Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science.{{cite journal |first1=Anthony K. |last1=Seda |first2=Pascal |last2=Hitzler | author-link2=Pascal Hitzler|title=Generalized Distance Functions in the Theory of Computation |journal=The Computer Journal |volume=53 |issue=4 |pages=443–464 |year=2010 |doi=10.1093/comjnl/bxm108 }}

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

:

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

For example, the value 3 may be chosen to start the fixed-point iteration, as $3\backslash pi/4\backslash leq3\backslash leq5\backslash pi/4$. The Banach fixed-point theorem may be used to conclude that

: $\backslash pi=f(f(f(\backslash cdots\; f(3)\backslash cdots)))).$

Applying f to 3 only three times already yields an expansion of {{pi}} accurate to 33 digits:

: $f(f(f(3)))=3.141592653589793238462643383279502\backslash ldots\backslash ,.$

{{Div col|colwidth=30em}}

• Brouwer fixed-point theorem
• Caristi fixed-point theorem
• Contraction mapping
• Fichera's existence principle
• Fixed-point iteration
• Fixed-point theorems
• Infinite compositions of analytic functions
• Kantorovich theorem

{{Div col end}}

• {{cite book |first1=Praveen |last1=Agarwal |first2=Mohamed |last2=Jleli |first3=Bessem |last3=Samet |chapter=Banach Contraction Principle and Applications |title=Fixed Point Theory in Metric Spaces |publisher=Springer |location=Singapore |year=2018 |isbn=978-981-13-2912-8 |pages=1–23 |doi=10.1007/978-981-13-2913-5_1 }}
• {{cite book |first=Carmen |last=Chicone |title=Ordinary Differential Equations with Applications |location=New York |publisher=Springer |edition=2nd |year=2006 |isbn=0-387-30769-9 |chapter=Contraction |chapter-url=https://books.google.com/books?id=yfY2uGROVrUC&pg=PA121 |pages=121–135 }}
• {{cite book |first1=Andrzej |last1=Granas |first2=James |last2=Dugundji |author-link2=James Dugundji |title=Fixed Point Theory |year=2003 |publisher=Springer-Verlag |location=New York |isbn=0-387-00173-5 }}
• {{cite book |first=Vasile I. |last=Istrăţescu |title=Fixed Point Theory: An Introduction |publisher=D. Reidel |location=The Netherlands |year=1981 |isbn=90-277-1224-7 }} See chapter 7.
• {{cite book |last1=Kirk |first1=William A. |last2=Khamsi |first2=Mohamed A. |title=An Introduction to Metric Spaces and Fixed Point Theory |year=2001 |publisher=John Wiley |location=New York |isbn=0-471-41825-0 }}

{{PlanetMath attribution |urlname=banachfixedpointtheorem |title=Banach fixed point theorem }}

{{Metric spaces}}

{{Topology}}

{{DEFAULTSORT:Banach Fixed-Point Theorem}}

Category:Articles containing proofs

Category:Eponymous theorems of mathematics

Category:Fixed-point theorems

Category:Metric geometry

Category:Topology