Editing Contraction mapping (section)

{{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>