Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Contraction mapping
Summary
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 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.
Contraction mappings play an important role in dynamic programming problems.
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 :
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 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (8)
Banach fixed-point theorem
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem or Banach-Caccioppoli theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certain self-maps of metric spaces, and provides a constructive method to find those fixed points. It can be understood as an abstract formulation of Picard's method of successive approximations. The theorem is named after Stefan Banach (1892–1945) who first stated it in 1922.
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 setting for studying many of the concepts of mathematical analysis and geometry. The most familiar example of a metric space is 3-dimensional Euclidean space with its usual notion of distance. Other well-known examples are a sphere equipped with the angular distance and the hyperbolic plane.
Contraction mapping
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 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.
Related courses (3)
EE-735: Online learning in games
This course provides an overview of recent developments in online learning, game theory, and variational inequalities and their point of intersection with a focus on algorithmic development. The prima
MATH-105(a): Advanced analysis II
Etudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs variables.
MATH-301: Ordinary differential equations
Le cours donne une introduction à la théorie des EDO, y compris existence de solutions locales/globales, comportement asymptotique, étude de la stabilité de points stationnaires et applications, en pa
Related lectures (40)
Fixed Point Method: Global Convergence
Explores the fixed point method for global convergence in solving nonlinear equations.
Local Inverse Theorems
Covers the local inverse theorem, diffeomorphisms, contraction mappings, and the Jacobian determinant.
The Banach Fixed Point Theorem
Explores the Banach Fixed Point Theorem, showing the uniqueness of fixed points in contraction mappings.