Contraction mapping: Difference between revisions
Jump to navigation
Jump to search
en>David Eppstein m authorlink James Dugundji |
just made the "nonnegativeness" of k symbolically explicit. |
||
| Line 1: | Line 1: | ||
In [[mathematics]], a '''contraction mapping''', or '''contraction''', on a [[metric space]] ''(M,d)'' is a [[function (mathematics)|function]] ''f'' from ''M'' to itself, with the property that there is some nonnegative [[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'' ≤ 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 <math>f:M \mapsto N</math>, then there is a constant <math>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 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]].<ref name="shifrin">Theodore Shifrin, ''Multivariable Mathematics'', Wiley, 2005, ISBN 0-471-52638-X, pp. 244–260.</ref> | |||
==Firmly non-expansive mapping== | |||
A non-expansive mapping with <math>k=1</math> 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'': | |||
:<math>\|f(x)-f(y) \|^2 \leq \, \langle x-y, f(x) - f(y) \rangle.</math> | |||
where | |||
:<math>d(x,y) = \|x-y\|</math> | |||
This is a special case of <math>\alpha</math> averaged nonexpansive operators with <math>\alpha = 1/2</math>.<ref>''Solving monotone inclusions via compositions of nonexpansive averaged operators'', Patrick L. Combettes, 2004</ref> A firmly non-expansive mapping is always non-expansive, via the [[Cauchy–Schwarz inequality]]. | |||
==See also== | |||
* [[Short map]] | |||
* [[Contraction (operator theory)]] | |||
==Notes== | |||
{{reflist}} | |||
==References== | |||
* Vasile I. Istratescu, ''Fixed Point Theory, An Introduction'', D.Reidel, Holland (1981). ISBN 90-277-1224-7 provides an undergraduate level introduction. | |||
* Andrzej Granas and [[James Dugundji]], ''Fixed Point Theory'' (2003) Springer-Verlag, New York, ISBN 0-387-00173-5 | |||
* William A. Kirk and Brailey Sims, ''Handbook of Metric Fixed Point Theory'' (2001), Kluwer Academic, London ISBN 0-7923-7073-2 | |||
{{DEFAULTSORT:Contraction Mapping}} | |||
[[Category:Metric geometry]] | |||
[[Category:Fixed points (mathematics)]] | |||
Revision as of 06:53, 18 November 2013
In mathematics, a contraction mapping, or contraction, 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, and , then 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 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]
Firmly non-expansive mapping
A non-expansive mapping with 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:
where
This is a special case of averaged nonexpansive operators with .[2] A firmly non-expansive mapping is always non-expansive, via the Cauchy–Schwarz inequality.
See also
Notes
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
References
- Vasile I. Istratescu, Fixed Point Theory, An Introduction, D.Reidel, Holland (1981). ISBN 90-277-1224-7 provides an undergraduate level introduction.
- Andrzej Granas and James Dugundji, Fixed Point Theory (2003) Springer-Verlag, New York, ISBN 0-387-00173-5
- William A. Kirk and Brailey Sims, Handbook of Metric Fixed Point Theory (2001), Kluwer Academic, London ISBN 0-7923-7073-2