In
mathematics, a contraction mapping, or contraction or contractor, on a
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
(''M'', ''d'') is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
''f'' from ''M'' to itself, with the property that there is some
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
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there ex ...
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
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certa ...
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
In mathematics, an iterated function is a function (that is, a function from some set to itself) which is obtained by composing another function with itself a certain number of times. The process of repeatedly applying the same 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
In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. They were introduced in 1981.
IFS fractals, ...
where
contraction mappings are often used. Banach's fixed-point theorem is also applied in proving the existence of solutions of
ordinary differential equation
In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast ...
s, and is used in one proof of the
inverse function theorem.
Contraction mappings play an important role in
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
...
problems.
Firmly non-expansive mapping
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
. A firmly non-expansive mapping is always non-expansive, via the
Cauchy–Schwarz inequality
The Cauchy–Schwarz inequality (also called Cauchy–Bunyakovsky–Schwarz inequality) is considered one of the most important and widely used inequalities in mathematics.
The inequality for sums was published by . The corresponding inequality fo ...
.
The class of firmly non-expansive maps is closed under
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other wor ...
s, 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
, then for any initial point
, iterating
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
:
:
If the
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
of a subcontractor ''f'' is
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in Britis ...
, then ''f'' has a fixed point.
Locally convex spaces
In a
locally convex space
In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological ve ...
(''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 ≤ . 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 In the mathematical theory of metric spaces, a metric map is a function between metric spaces that does not increase any distance (such functions are always continuous).
These maps are the morphisms in the category of metric spaces, Met (Isbell 1 ...
*
Contraction (operator theory)
In operator theory, a bounded operator ''T'': ''X'' → ''Y'' between normed vector spaces ''X'' and ''Y'' is said to be a contraction if its operator norm , , ''T'' , , ≤ 1. This notion is a special case of the concept of a contractio ...
*
Transformation
Transformation may refer to:
Science and mathematics
In biology and medicine
* Metamorphosis, the biological process of changing physical form after birth or hatching
* Malignant transformation, the process of cells becoming cancerous
* Trans ...
References
Further reading
* provides an undergraduate level introduction.
*
*
*
{{DEFAULTSORT:Contraction Mapping
Metric geometry
Fixed points (mathematics)