Contraction mapping explained
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 mapping
A non-expansive mapping with
can be generalized to a
firmly non-expansive mapping in a
Hilbert space
if the following holds for all
x and
y in
:
\|f(x)-f(y)\|2\leq\langlex-y,f(x)-f(y)\rangle.
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
Fixf:=\{x\inl{H} | f(x)=x\} ≠ \varnothing
, then for any initial point
, iterating
(\foralln\inN) xn+1=f(xn)
yields convergence to a fixed point
. 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
d(f(f(x)),f(x))<d(f(x),x) unless x=f(x).
If the image of a subcontractor f is compact, then f has a fixed point.[7]
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 kp < 1 such that ≤ . 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 xn+1 = f(xn), and if (E, P) is Hausdorff, then the fixed point is unique.[8]
See also
Further reading
- Book: Istratescu, Vasile I. . Fixed Point Theory: An Introduction . D.Reidel . Holland . 1981 . 978-90-277-1224-0 . provides an undergraduate level introduction.
- Book: Andrzej . Granas . James . Dugundji . James Dugundji . Fixed Point Theory . 2003 . Springer-Verlag . New York . 978-0-387-00173-9 .
- Book: William A. . Kirk . Brailey . Sims . Handbook of Metric Fixed Point Theory . 2001 . Kluwer Academic . London . Brailey Sims . 978-0-7923-7073-4.
- Book: Arch W. . Naylor . George R. . Sell . Linear Operator Theory in Engineering and Science . Applied Mathematical Sciences . 40 . New York . Springer . 1982 . Second . 978-0-387-90748-2 . 125 - 134 .
- Book: Francesco . Bullo. Contraction Theory for Dynamical Systems . 2022 . Kindle Direct Publishing . 979-8-8366-4680-6 .
Notes and References
- Book: Shifrin, Theodore . Multivariable Mathematics . Wiley . 2005 . 978-0-471-52638-4 . 244–260 .
- Eric V. . Denardo . Contraction Mappings in the Theory Underlying Dynamic Programming . SIAM Review . 9 . 2 . 165–177 . 1967 . 10.1137/1009030 . 1967SIAMR...9..165D .
- Book: Nancy L. . Stokey . Nancy Stokey . Robert E. . Lucas . 1989 . Robert Lucas Jr. . Recursive Methods in Economic Dynamics . Cambridge . Harvard University Press . 49–55 . 978-0-674-75096-8 .
- Solving monotone inclusions via compositions of nonexpansive averaged operators . Patrick L. . Combettes . 2004 . . 53 . 5–6 . 475–504 . 10.1080/02331930412331327157 . 219698493 .
- Book: Bauschke, Heinz H.. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer. 2017. New York.
- Combettes. Patrick L.. July 2018. Monotone operator theory in convex optimization. Mathematical Programming. B170. 177–206. 1802.02694. 10.1007/s10107-018-1303-3. 2018arXiv180202694C. 49409638.
- Book: Goldstein, A.A. . Constructive real analysis . 0189.49703 . Harper's Series in Modern Mathematics . New York-Evanston-London . Harper and Row . 1967 . 17 .
- G. L. Jr. . Cain . M. Z. . Nashed . Zuhair Nashed . Fixed Points and Stability for a Sum of Two Operators in Locally Convex Spaces . Pacific Journal of Mathematics . 39 . 3 . 1971 . 581–592 . 10.2140/pjm.1971.39.581 . free .
