Banach fixed-point theorem: Difference between revisions

Revision as of 05:39, 20 February 2023

Revision as of 21:27, 18 March 2023

Line 1:

{{Short description|Theorem about metric spaces}}

In [[mathematics]], the '''Banach [[fixed-point theorem]]''' (also known as the '''contraction mapping theorem''' or '''contractive mapping theorem''') is an important [[Convergence proof techniques#contraction mapping|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 |firstfirst1=David |lastlast1=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://wwwbooks.google.com/books/edition/_/eCDnoB3Np5oC?hlid=en&gbpv=1eCDnoB3Np5oC&pg=PA7 }}</ref> The theorem is named after [[Stefan Banach]] (1892–1945) who first stated it 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 |archive-url=https://web.archive.org/web/20110607002842/http://matwbn.icm.edu.pl/ksiazki/or/or2/or215.pdf |archive-date=2011-06-07 |url-status=live |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 |archive-url=https://web.archive.org/web/20090530012258/http://www.emis.de/journals/BJMA/tex_v1_n1_a1.pdf |archive-date=2009-05-30 |url-status=live |doi=10.15352/bjma/1240321550 |doi-access=free }}</ref>

==Statement==

Line 68:

*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]].<ref>{{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}}</ref>

*It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of [[reinforcement learning]].<ref>{{cite book |firstfirst1=Frank L. |lastlast1=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://wwwbooks.google.com/books/edition/_/U3Gtlot_hYEC?hlid=en&gbpv=1U3Gtlot_hYEC&pg=PA474 }}</ref>

*It can be used to prove existence and uniqueness of an equilibrium in [[Cournot competition]],<ref>{{cite journal |firstfirst1=Ngo Van |lastlast1=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 }}</ref> and other dynamic economic models.<ref>{{cite book |firstfirst1=Nancy L. |lastlast1=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://wwwbooks.google.com/books/edition/_/BgQ3AwAAQBAJ?hlid=en&gbpv=1BgQ3AwAAQBAJ&pg=PA508 }}</ref>

==Converses==

Line 76:

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 |firstfirst1=Pascal |lastlast1=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==

Line 88:

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.

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 |firstfirst1=Pascal |lastlast1=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 |firstfirst1=Anthony K. |lastlast1=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>

==See also==

Line 106:

==References==

*{{cite book |firstfirst1=Praveen |lastlast1=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://wwwbooks.google.com/books/edition/_/yfY2uGROVrUC?hlid=en&gbpv=1yfY2uGROVrUC&pg=PA121 |pages=121–135 }}

*{{cite book |firstfirst1=Andrzej |lastlast1=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 }}