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 ${\displaystyle 0\leq k<1}$ such that for all x and y in M,

${\displaystyle d(f(x),f(y))\leq k\,d(x,y).}$

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 ${\displaystyle f:M\rightarrow N}$ is a contractive mapping if there is a constant ${\displaystyle 0\leq k<1}$ such that

${\displaystyle 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 (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]