# Contraction mapping

In mathematics, a **contraction mapping**, or **contraction** or **contractor**, on a metric space (*M*, *d*) is a function *f* from *M* to itself, with the property that there is some nonnegative real number such that for all *x* and *y* in *M*,

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* ≤ 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*, *d*) and (*N*, *d'*) are two metric spaces, then is a contractive mapping if there is a constant such that

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. Moreover, the Banach fixed-point theorem states that every contraction mapping on a non-empty complete metric space has a unique fixed point, and that for any *x* in *M* the iterated function sequence *x*, *f* (*x*), *f* (*f* (*x*)), *f* (*f* (*f* (*x*))), ... converges to the fixed point. This concept is very useful for iterated function systems where contraction mappings are often used. Banach's fixed-point theorem is also applied in proving the existence of solutions of ordinary differential equations, and is used in one proof of the inverse function theorem.^{[1]}

Contraction mappings play an important role in dynamic programming problems.^{[2]}^{[3]}

## Firmly non-expansive mappingEdit

A non-expansive mapping with can be strengthened to a **firmly non-expansive mapping** in a Hilbert space if the following holds for all *x* and *y* in :

where

- .

This is a special case of averaged nonexpansive operators with .^{[4]} 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 combinations, but not compositions.^{[5]} This class includes proximal mappings of proper, convex, lower-semicontinuous functions, hence it also includes orthogonal projections onto non-empty closed convex sets. The class of firmly nonexpansive operators is equal to the set of resolvents of maximally monotone operators^{[6]}. 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 guarantee global convergence to a fixed point, provided a fixed point exists. More precisely, if , then for any initial point , iterating

yields convergence to a fixed point . This convergence might be weak in an infinite-dimensional setting.^{[5]}

## Subcontraction mapEdit

A **subcontraction map** or **subcontractor** is a map *f* on a metric space (*M*, *d*) such that

If the image of a subcontractor *f* is compact, then *f* has a fixed point.^{[7]}

## Locally convex spacesEdit

In a locally convex space (*E*, *P*) with topology given by a set *P* of seminorms, one can define for any *p* ∈ *P* a *p*-contraction as a map *f* such that there is some *k*_{p} < 1 such that *p*(*f*(*x*) − *f*(*y*)) ≤ *k _{p} p*(

*x*−

*y*). If

*f*is a

*p*-contraction for all

*p*∈

*P*and (

*E*,

*P*) is sequentially complete, then

*f*has a fixed point, given as limit of any sequence

*x*

_{n+1}=

*f*(

*x*

_{n}), and if (

*E*,

*P*) is Hausdorff, then the fixed point is unique.

^{[8]}

## See alsoEdit

## ReferencesEdit

**^**Shifrin, Theodore (2005).*Multivariable Mathematics*. Wiley. pp. 244–260. ISBN 978-0-471-52638-4.**^**Denardo, Eric V. (1967). "Contraction Mappings in the Theory Underlying Dynamic Programming".*SIAM Review*.**9**(2): 165–177. Bibcode:1967SIAMR...9..165D. doi:10.1137/1009030.**^**Stokey, Nancy L.; Lucas, Robert E. (1989).*Recursive Methods in Economic Dynamics*. Cambridge: Harvard University Press. pp. 49–55. ISBN 978-0-674-75096-8.**^**Combettes, Patrick L. (2004). "Solving monotone inclusions via compositions of nonexpansive averaged operators".*Optimization*.**53**(5–6): 475–504. doi:10.1080/02331930412331327157.- ^
^{a}^{b}Bauschke, Heinz H. (2017).*Convex Analysis and Monotone Operator Theory in Hilbert Spaces*. New York: Springer. **^**Combettes, Patrick L. (July 2018). "Monotone operator theory in convex optimization".*Mathematical Programming*.**B170**: 177–206. arXiv:1802.02694. Bibcode:2018arXiv180202694C. doi:10.1007/s10107-018-1303-3.**^**Goldstein, A.A. (1967).*Constructive real analysis*. Harper’s Series in Modern Mathematics. New York-Evanston-London: Harper and Row. p. 17. Zbl 0189.49703.**^**Cain, G. L., Jr.; Nashed, M. Z. (1971). "Fixed Points and Stability for a Sum of Two Operators in Locally Convex Spaces".*Pacific Journal of Mathematics*.**39**(3): 581–592. doi:10.2140/pjm.1971.39.581.

## Further readingEdit

- Istratescu, Vasile I. (1981).
*Fixed Point Theory : An Introduction*. Holland: D.Reidel. ISBN 978-90-277-1224-0. provides an undergraduate level introduction. - Granas, Andrzej; Dugundji, James (2003).
*Fixed Point Theory*. New York: Springer-Verlag. ISBN 978-0-387-00173-9. - Kirk, William A.; Sims, Brailey (2001).
*Handbook of Metric Fixed Point Theory*. London: Kluwer Academic. ISBN 978-0-7923-7073-4. - Naylor, Arch W.; Sell, George R. (1982).
*Linear Operator Theory in Engineering and Science*. Applied Mathematical Sciences.**40**(Second ed.). New York: Springer. pp. 125–134. ISBN 978-0-387-90748-2.