Contraction mapping

related topics
{math, number, function}

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 real number k < 1 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 satisfied for k \leq 1, then the mapping is said to be non-expansive.

In non-technical terms, a contraction mapping brings every two points x and y in M closer together.

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 one looks for the constant k 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.

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]

See also



  • 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

Full article ▸

related documents
LALR parser
Blum Blum Shub
Normal morphism
Best-first search
Nearest neighbour algorithm
Complete measure
Lyapunov fractal
Axiom of union
Sophie Germain prime
Baire category theorem
Group homomorphism
Composite number
Partition of unity
Mutual recursion
Linear congruence theorem
Characteristic subgroup
Up to
Multiple inheritance
Hamiltonian path problem
Permutation group
Complete category
Category of sets
Tree structure
Zhu Shijie
AVL tree
Elias delta coding
Brun's constant
Abelian category