Editing Contraction mapping

{{Short description|Function reducing distance between all points}} In [[mathematics]], a '''contraction mapping''', or '''contraction''' or '''contractor''', on a [[metric space]] (''M'',&thinsp;''d'') is a [[Function (mathematics)|function]] ''f'' from ''M'' to itself, with the property that there is some [[real number]] <math>0 \leq k < 1</math> such that for all ''x'' and ''y'' in ''M'',

:<math>d(f(x),f(y)) \leq k\,d(x,y).</math>
The smallest such value of ''k'' is called the '''Lipschitz constant''' of ''f''.  Contractive maps are sometimes called '''Lipschitzian maps'''.  If the above condition is instead satisfied for
''k''&nbsp;≤&nbsp;1, then the mapping is said to be a [[non-expansive map]].

More generally, the idea of a contractive mapping can be defined for maps between metric spaces. Thus, if (''M'',&thinsp;''d'') and (''N'',&thinsp;''d''') are two metric spaces, then <math>f:M \rightarrow N</math> is a contractive mapping if there is a constant <math>0 \leq k < 1</math> such that
:<math>d'(f(x),f(y)) \leq k\,d(x,y)</math>
for all ''x'' and ''y'' in ''M''.

Every contraction mapping is [[Lipschitz continuous]] and hence [[uniformly continuous]] (for a Lipschitz continuous function, the constant ''k'' is no longer necessarily less than 1).

A contraction mapping has at most one [[Fixed point (mathematics)|fixed point]]. Moreover, the [[Banach fixed-point theorem]] states that every contraction mapping on a [[Empty set|non-empty]] [[complete metric space]] has a unique fixed point, and that for any ''x'' in ''M'' the [[iterated function]] sequence ''x'', ''f''&thinsp;(''x''), ''f''&thinsp;(''f''&thinsp;(''x'')), ''f''&thinsp;(''f''&thinsp;(''f''&thinsp;(''x''))), ... converges to the fixed point. This concept is very useful for [[iterated function systems]] where [[convergence proof techniques#contraction mapping|contraction mappings are often used]]. Banach's fixed-point theorem is also applied in proving the existence of solutions of [[ordinary differential equation]]s, and is used in one proof of the [[inverse function theorem]].<ref name="shifrin">{{cite book |first=Theodore |last=Shifrin |title=Multivariable Mathematics |publisher=Wiley |year=2005 |isbn=978-0-471-52638-4 |pages=244–260 }}</ref>

Contraction mappings play an important role in [[dynamic programming]] problems.<ref>{{cite journal |first=Eric V. |last=Denardo |title=Contraction Mappings in the Theory Underlying Dynamic Programming |journal=SIAM Review |volume=9 |issue=2 |pages=165–177 |year=1967 |doi=10.1137/1009030 |bibcode=1967SIAMR...9..165D }}</ref><ref>{{cite book |first1=Nancy L. |last1=Stokey |author1-link=Nancy Stokey | first2=Robert E. |last2=Lucas |year=1989 |author-link2=Robert Lucas Jr. |title=Recursive Methods in Economic Dynamics |location=Cambridge |publisher=Harvard University Press |pages=49–55 |isbn=978-0-674-75096-8 |url=https://books.google.com/books?id=BgQ3AwAAQBAJ&pg=PA49 }}</ref>

==Firmly non-expansive mapping==
A non-expansive mapping with <math>k=1</math> can be generalized to a '''firmly non-expansive mapping''' in a [[Hilbert space]] <math>\mathcal{H}</math> if the following holds for all ''x'' and ''y'' in <math>\mathcal{H}</math>:
:<math>\|f(x)-f(y) \|^2 \leq \, \langle x-y, f(x) - f(y) \rangle.</math>
where
:<math>d(x,y) = \|x-y\|</math>.

This is a special case of <math>\alpha</math> averaged nonexpansive operators with <math>\alpha = 1/2</math>.<ref>{{cite journal |title=Solving monotone inclusions via compositions of nonexpansive averaged operators |first=Patrick L. |last=Combettes |year=2004 |journal=[[Optimization (journal)|Optimization]] |volume=53 |issue=5–6 |pages=475–504 |doi=10.1080/02331930412331327157 |s2cid=219698493 }}</ref> A firmly non-expansive mapping is always non-expansive, via the [[Cauchy–Schwarz inequality]].

The class of firmly non-expansive maps is closed under [[convex combination]]s, but not compositions.<ref name=":0">{{Cite book|title=Convex Analysis and Monotone Operator Theory in Hilbert Spaces|last=Bauschke|first=Heinz H.|publisher=Springer|year=2017|location=New York}}</ref> This class includes [[Proximal operator|proximal mappings]] of proper, convex, lower-semicontinuous functions, hence it also includes orthogonal [[Projection (mathematics)|projections]] onto non-empty closed [[convex set]]s. The class of firmly nonexpansive operators is equal to the set of resolvents of maximally [[Monotonic function#Monotonicity in functional analysis|monotone operators]].<ref>{{Cite journal|last=Combettes|first=Patrick L.|date=July 2018|title=Monotone operator theory in convex optimization|journal=Mathematical Programming|volume=B170|pages=177–206|arxiv=1802.02694|doi=10.1007/s10107-018-1303-3|bibcode=2018arXiv180202694C|s2cid=49409638}}</ref> Surprisingly, while iterating non-expansive maps has no guarantee to find a fixed point (e.g. multiplication by -1), firm non-expansiveness is sufficient to [[convergence proof techniques|guarantee global convergence]] to a fixed point, provided a fixed point exists. More precisely, if <math>\operatorname{Fix}f := \{x \in \mathcal{H} \ | \ f(x) = x\} \neq \varnothing</math>, then for any initial point <math>x_0 \in \mathcal{H}</math>, iterating

<math> (\forall n \in \mathbb{N})\quad x_{n+1} = f(x_n) </math>

yields convergence to a fixed point <math> x_n \to z \in \operatorname{Fix} f</math>. This convergence might be [[Weak convergence (Hilbert space)|weak]] in an infinite-dimensional setting.<ref name=":0" />

==Subcontraction map==
A '''subcontraction map''' or '''subcontractor''' is a map ''f'' on a metric space (''M'',&thinsp;''d'') such that

:<math> d(f(x), f(y)) \leq d(x,y);</math>
:<math> d(f(f(x)),f(x)) < d(f(x),x) \quad \text{unless} \quad x = f(x).</math>

If the [[Image (mathematics)|image]] of a subcontractor ''f'' is [[Compact space|compact]], then ''f'' has a fixed point.<ref name=Gold17>{{cite book | last=Goldstein | first=A.A. | title=Constructive real analysis | zbl=0189.49703 | series=Harper's Series in Modern Mathematics | location=New York-Evanston-London | publisher=Harper and Row | year=1967 |page=17 }}</ref>

==Locally convex spaces==
In a [[locally convex space]] (''E'',&thinsp;''P'') with [[Topological space|topology]] given by a set ''P'' of [[seminorm]]s, one can define for any ''p''&thinsp;&isin;&thinsp;''P'' a ''p''-contraction as a map ''f'' such that there is some ''k''<sub>''p''</sub> < 1 such that {{nowrap|''p''(''f''(''x'') − ''f''(''y''))}} ≤ {{nowrap|''k<sub>p</sub> p''(''x'' − ''y'')}}. If ''f'' is a ''p''-contraction for all ''p''&thinsp;&isin;&thinsp;''P'' and (''E'',&thinsp;''P'') is sequentially complete, then ''f'' has a fixed point, given as limit of any sequence ''x''<sub>''n''+1</sub> = ''f''(''x''<sub>''n''</sub>), and if (''E'',&thinsp;''P'') is [[Hausdorff space|Hausdorff]], then the fixed point is unique.<ref>{{cite journal |first1=G. L. Jr. |last1=Cain |first2=M. Z. |last2=Nashed |author-link2=Zuhair Nashed |title=Fixed Points and Stability for a Sum of Two Operators in Locally Convex Spaces |journal=Pacific Journal of Mathematics |volume=39 |issue=3 |year=1971 |pages=581–592 |doi=10.2140/pjm.1971.39.581 |doi-access=free }}</ref>

==See also==
* [[Short map]]
* [[Contraction (operator theory)]]
* [[Transformation (function)|Transformation]]
* [[Comparametric equation]]
* [[Blackwell's contraction mapping theorem]]
* [[CLRg property]]

==References==
{{reflist}}

==Further reading==
* {{cite book |first=Vasile I. |last=Istratescu |title=Fixed Point Theory: An Introduction |publisher=D.Reidel |location=Holland |year=1981 |isbn=978-90-277-1224-0 }} provides an undergraduate level introduction.
* {{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=978-0-387-00173-9 }}
* {{cite book |first1=William A. |last1=Kirk |first2=Brailey |last2=Sims |title=Handbook of Metric Fixed Point Theory |year=2001 |publisher=Kluwer Academic |location=London |author-link2=Brailey Sims |isbn=978-0-7923-7073-4}}
* {{cite book |first1=Arch W. |last1=Naylor |first2=George R. |last2=Sell |title=Linear Operator Theory in Engineering and Science |series=Applied Mathematical Sciences |volume=40 |location=New York |publisher=Springer |year=1982 |edition=Second |isbn=978-0-387-90748-2 |pages=125&ndash;134 |url=https://books.google.com/books?id=t3SXs4-KrE0C&pg=PA125 }}

* {{cite book |first1=Francesco |last1=Bullo|title=Contraction Theory for Dynamical Systems |year=2022 |publisher=Kindle Direct Publishing |isbn=979-8-8366-4680-6 }}

{{Metric spaces}}
{{DEFAULTSORT:Contraction Mapping}}

[[Category:Fixed points (mathematics)]]
[[Category:Metric geometry]]