Misplaced Pages

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 real number ${\displaystyle 0\leq k<1}$ such that for all x and y in M,

${\displaystyle d(f(x),f(y))\leq k\,d(x,y).}$

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 ${\displaystyle f:M\rightarrow N}$ is a contractive mapping if there is a constant ${\displaystyle 0\leq k<1}$ such that

${\displaystyle d'(f(x),f(y))\leq k\,d(x,y)}$

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.

Contraction mappings play an important role in dynamic programming problems.

Firmly non-expansive mapping

A non-expansive mapping with ${\displaystyle k=1}$ can be generalized to a firmly non-expansive mapping in a Hilbert space ${\displaystyle {\mathcal {H}}}$ if the following holds for all x and y in ${\displaystyle {\mathcal {H}}}$:

${\displaystyle \|f(x)-f(y)\|^{2}\leq \,\langle x-y,f(x)-f(y)\rangle .}$

where

${\displaystyle d(x,y)=\|x-y\|}$.

This is a special case of ${\displaystyle \alpha }$ averaged nonexpansive operators with ${\displaystyle \alpha =1/2}$. 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. 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. 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 ${\displaystyle {\text{Fix}}f:=\{x\in {\mathcal {H}}\ |\ f(x)=x\}\neq \varnothing }$, then for any initial point ${\displaystyle x_{0}\in {\mathcal {H}}}$, iterating

${\displaystyle (\forall n\in \mathbb {N} )\quad x_{n+1}=f(x_{n})}$

yields convergence to a fixed point ${\displaystyle x_{n}\to z\in {\text{Fix}}f}$. This convergence might be weak in an infinite-dimensional setting.

Subcontraction map

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

${\displaystyle d(f(x),f(y))\leq d(x,y);}$

${\displaystyle d(f(f(x)),f(x))<d(f(x),x)\quad {\text{unless}}\quad x=f(x).}$

If the image of a subcontractor f is compact, then f has a fixed point.

Locally convex spaces

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.

See also

• Short map
• Contraction (operator theory)
• Transformation
• Comparametric equation
• Blackwell's contraction mapping theorem
• CLRg property

References

1. Shifrin, Theodore (2005). Multivariable Mathematics. Wiley. pp. 244–260. ISBN 978-0-471-52638-4.
2. 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.
3. 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.
4. Combettes, Patrick L. (2004). "Solving monotone inclusions via compositions of nonexpansive averaged operators". Optimization. 53 (5–6): 475–504. doi:10.1080/02331930412331327157. S2CID 219698493.
5. ^ Bauschke, Heinz H. (2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. New York: Springer.
6. 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. S2CID 49409638.
7. 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.
8. 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 reading

• 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. Vol. 40 (Second ed.). New York: Springer. pp. 125–134. ISBN 978-0-387-90748-2.

• Bullo, Francesco (2022). Contraction Theory for Dynamical Systems. Kindle Direct Publishing. ISBN 979-8-8366-4680-6.

• Metric geometry
• Fixed points (mathematics)