Contraction mapping

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

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, and $f:M\rightarrow N$ , then there is a constant $k<1$ such that

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 nonempty 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 mapping plays an important role in dynamic programming problems.^[2]^[3]

Firmly non-expansive mapping

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

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

where

d(x,y)=\|x-y\|

This is a special case of $\alpha$ averaged nonexpansive operators with $\alpha =1/2$ .^[4] A firmly non-expansive mapping is always non-expansive, via the Cauchy–Schwarz inequality.

Subcontraction map

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

d(f(x),f(y))\leq d(x,y)\ ;

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.^[5]

References

^ Shifrin, Theodore (2005). Multivariable Mathematics. Wiley. pp. 244–260. ISBN 0-471-52638-X.
^ Denardo, Eric V. (1967). "Contraction Mappings in the Theory Underlying Dynamic Programming". SIAM Review. 9 (2): 165–177. doi:10.1137/1009030.
^ Stokey, Nancy L.; Lucas, Robert E. (1989). Recursive Methods in Economic Dynamics. Cambridge: Harvard University Press. pp. 49–55. ISBN 0-674-75096-9.
^ Combettes, Patrick L. (2004). "Solving monotone inclusions via compositions of nonexpansive averaged operators". Optimization. 53 (5–6): 475–504. doi:10.1080/02331930412331327157.
^ 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.

Contraction mapping

Firmly non-expansive mapping

Subcontraction map

See also

References

Further reading