Banach fixed-point theorem: Difference between revisions

Revision as of 14:27, 4 September 2024

Latest revision as of 19:58, 29 January 2025

(3 intermediate revisions by 2 users not shown)

Line 34:

:<math>d(x_{n+1}, x_n) \le q^n d(x_1, x_0).</math>

This follows by [[Principle of mathematical induction|induction]] on ''<math>n''</math>, using the fact that ''<math>T''</math> is a contraction mapping. Then we can show that <math>(x_n)_{n\in\mathbb N}</math> is a [[Cauchy sequence]]. In particular, let <math>m, n \in \N</math> such that <math>m > n </math>:

: <math>\begin{align}

Line 44:

\end{align}</math>

Let ''ε''<math>\varepsilon > 0</math> be arbitrary. Since <math>q \in [0,1)</math>, we can find a large <math>N \in \N</math> so that

:<math>q^N < \frac{\varepsilon(1-q)}{d(x_1, x_0)}.</math>

Line 52:

:<math>d(x_m, x_n) \leq q^n d(x_1, x_0) \left ( \frac{1}{1-q} \right ) < \left (\frac{\varepsilon(1-q)}{d(x_1, x_0)} \right ) d(x_1, x_0) \left ( \frac{1}{1-q} \right ) = \varepsilon.</math>

This proves that the sequence <math>(x_n)_{n\in\mathbb N}</math> is Cauchy. By completeness of <math>(''X'','' d'')</math>, the sequence has a limit <math>x^* \in X.</math> Furthermore, <math>x^*</math> must be a [[Fixed point (mathematics)|fixed point]] of ''<math>T''</math>:

:<math>x^*=\lim_{n\to\infty} x_n = \lim_{n\to\infty} T(x_{n-1}) = T\left(\lim_{n\to\infty} x_{n-1} \right) = T(x^*). </math>

As a contraction mapping, ''<math>T''</math> is continuous, so bringing the limit inside ''<math>T''</math> was justified. Lastly, ''<math>T''</math> cannot have more than one fixed point in <math>(''X'','' d'')</math>, since any pair of distinct fixed points ''p''<submath>1p_1</submath> and ''p''<submath>2p_2</submath> would contradict the contraction of ''<math>T''</math>:

:<math> d(T(p_1),T(p_2)) = d(p_1,p_2) > q d(p_1, p_2).</math>

Line 88:

: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 <math>T</math> satisfying <math>d(T(x),T(y))<d(x,y)</math> for all distinct <math>x,y</math>, has a unique fixed point. The proof is simpler than the Banach theorem, because the function <math>d(T(x),x)</math> 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.<ref>{{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 }}</ref> Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science.<ref>{{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 }}</ref>

Line 131 ⟶ 133:

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

{{Metric spaces}}

{{Topology}}