Banach fixed-point theorem: Difference between revisions

Revision as of 21:33, 6 May 2021

Revision as of 01:32, 8 July 2021

Line 1:

In [[mathematics]], the '''Banach–CaccioppoliBanach [[fixed-point theorem]]''' (also known as the '''contraction mapping theorem''' or '''contractive mapping theorem''') is an important tool in the theory of [[metric space]]s; it guarantees the existence and uniqueness of [[fixed point (mathematics)|fixed points]] of certain self-maps of metric spaces, and provides a constructive method to find those fixed points. It can be understood as an abstract formulation of [[Fixed-point iteration|Picard's method of successive approximations]].<ref>{{cite book |first=David |last=Kinderlehrer |author-link=David Kinderlehrer |first2=Guido |last2=Stampacchia |author-link2=Guido Stampacchia |chapter=Variational Inequalities in '''R'''^N |title=An Introduction to Variational Inequalities and Their Applications |___location=New York |publisher=Academic Press |year=1980 |isbn=0-12-407350-6 |pages=7–22 |chapter-url=https://www.google.com/books/edition/_/eCDnoB3Np5oC?hl=en&gbpv=1&pg=PA7 }}</ref> The theorem is named after [[Stefan Banach]] (1892–1945) and [[Renato Caccioppoli]] (1904–1959), and waswho first stated by Banachit in 1922.<ref>{{cite journal |last=Banach|first= Stefan|author-link=Stefan Banach| title=Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales|journal=[[Fundamenta Mathematicae]]|volume= 3|year=1922|pages= 133–181 |url=http://matwbn.icm.edu.pl/ksiazki/or/or2/or215.pdf |doi=10.4064/fm-3-1-133-181}}</ref><ref>{{cite journal |first=Krzysztof |last=Ciesielski |title=On Stefan Banach and some of his results |journal=Banach J. Math. Anal. |volume=1 |year=2007 |issue=1 |pages=1–10 |url=http://www.emis.de/journals/BJMA/tex_v1_n1_a1.pdf |doi=10.15352/bjma/1240321550 |doi-access=free }}</ref> Caccioppoli independently proved the theorem in 1931.<ref>{{cite web |title=Renato Caccioppoli Bibliografy |url=http://mathshistory.st-andrews.ac.uk/Biographies/Caccioppoli.html |access-date=23 May 2020}}</ref>

==Statement==

''Definition.'' Let <math>(''X'','' d'')</math> be a [[complete metric space]]. Then a map ''<math>T'' : ''X'' →\to ''X''</math> is called a [[contraction mapping]] on ''X'' if there exists ''<math>q'' ∈\in [0, 1)</math> such that

:<math>d(T(x),T(y)) \le q d(x,y)</math>

for all ''<math>x'', ''y'' \in ''X''.</math>

<blockquote>'''Banach Fixed Point Theorem.''' Let ''<math>(X, d)''</math> be a [[Empty set|non-empty]] [[complete metric space]] with a contraction mapping ''<math>T'' : ''X'' →\to ''X''.</math> Then ''T'' admits a unique [[Fixed point (mathematics)|fixed-point]] ''x*'' in ''X'' (i.e. ''T''(''x*'') = ''x*''). Furthermore, ''x*'' can be found as follows: start with an arbitrary element ''x''<sub>0</submath>x_0 \in ''X''</math> and define a [[sequence]] {''x_n''} by ''x_n'' = ''T''(''x''_''n''−1) for ''<math>n'' ≥\geq 1.</math> Then {{nowrap|''x_n'' → ''x*''}}.</blockquote>

''Remark 1.'' The following inequalities are equivalent and describe the [[Rate of convergence|speed of convergence]]:

Line 22:

''Remark 2.'' ''d''(''T''(''x''),&nbsp;''T''(''y''))&nbsp;<&nbsp;''d''(''x'',&nbsp;''y'') for all ''x'' ≠ ''y'' is in general not enough to ensure the existence of a fixed point, as is shown by the map ''T'' : [1, ∞) → [1, ∞), ''T''(''x'')&nbsp;=&nbsp;''x''&nbsp;+&nbsp;1/''x'', which lacks a fixed point. However, if ''X'' is [[Compact space|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'',&nbsp;''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 ''<math>T''(''X'') ⊆\subseteq ''X''.</math>

==Proof==

Let ''x''<submath>0x_0 \in X</submath> ∈ ''X'' be arbitrary and define a sequence {''x_n''} by setting ''x_n'' = ''T''(''x''_''n''−1). We first note that for all ''<math>n'' ∈\in '''\N''',</math> we have the inequality

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

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

: <math>\begin{align}

Line 40:

\end{align}</math>

Let ε > 0 be arbitrary, since ''q'' ∈ [0, 1), 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 48:

:<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 {''x_n''} is Cauchy. By completeness of (''X'',''d''), the sequence has a limit ''<math>x^*'' ∈\in ''X''.</math> Furthermore, ''x*'' must be a [[Fixed point (mathematics)|fixed point]] of ''T'':

:<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, ''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₁'' and ''p₂'' would contradict the contraction of ''T'':

Line 71:

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 (mathematics)|set]] such that each [[iterated function|iterate]] ''fⁿ'' has a unique fixed point. Let ''<math>q'' ∈\in (0, 1),</math> 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 ''<math>f'' : ''X'' →\to ''X''</math> is a map on a [[T1 space|''T''₁ topological space]] with a unique [[fixed point (mathematics)|fixed point]] ''a'', such that for each ''<math>x'' \in ''X''</math> 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.<ref>{{cite journal |first=Pascal |last=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 }}</ref> In this case the metric is in fact an [[ultrametric]].

==Generalizations==