The Contraction Mapping Theorem

Many equations can be written as $x = g(x)$, and the simplest way to try to solve one is to iterate: $x_{n+1} = g(x_n)$. The mean value inequality tells you when the iterates shrink their gaps, and completeness of the metric space supplies the limit.

Key idea

Contraction mapping theorem. Let $(X, d)$ be a complete metric space and $g : X \to X$ a contraction: $d(g(x), g(y)) \le k\,d(x, y)$ for all $x, y$, with one constant $k < 1$. Then $g$ has exactly one fixed point $x^{*}$, and for any $x_0$ the iterates converge to it with $d(x_n, x^{*}) \le \frac{k^{n}}{1 - k}\,d(x_1, x_0)$.

Why it works

Each step shrinks the gap: $d(x_{j+1}, x_j) \le k^{j} d(x_1, x_0)$. For $m > n$, by the triangle inequality and the geometric series, $$d(x_m, x_n) \le \sum_{j=n}^{m-1} k^{j} d(x_1, x_0) \le \frac{k^{n}}{1 - k}\,d(x_1, x_0).$$ This goes to $0$, so $(x_n)$ is Cauchy and converges to some $x^{*} \in X$ (completeness). A contraction is continuous, so $x^{*} = \lim x_{n+1} = \lim g(x_n) = g(x^{*})$. Letting $m \to \infty$ in the display gives the error bound. If $y^{*}$ is another fixed point, $d(x^{*}, y^{*}) = d(g(x^{*}), g(y^{*})) \le k\,d(x^{*}, y^{*})$, which forces $d(x^{*}, y^{*}) = 0$. $\blacksquare$

On a closed interval $I$ of $\mathbb{R}$ (which is complete), the mean value theorem gives a practical test: if $g$ maps $I$ into $I$ and $|g'(x)| \le k < 1$ on all of $I$, then $|g(x) - g(y)| = |g'(c)||x - y| \le k|x - y|$.

Iterating $g(x) = \sqrt{2 + x}$: from $x_0$, go up to the graph, across to the line $y = x$, and repeat. On $[0, 2]$, $|g'| \le \frac{1}{2\sqrt{2}}$, and the path climbs in steps to the fixed point $2$. Drag $x_0$ or press Step.

Worked examples

Worked example: Checking the hypotheses

Show that $g(x) = \cos x$ is a contraction on $[0, 1]$.

$g$ is decreasing there, so $g([0, 1]) = [\cos 1, 1] \approx [0.54, 1] \subseteq [0, 1]$.
$|g'(x)| = \sin x \le \sin 1 \approx 0.84$ on $[0, 1]$.

Answer: It is a contraction with $k = \sin 1 < 1$. So $\cos x = x$ has exactly one solution there, about $0.739$.

Worked example: The a priori bound

For $g(x) = \frac{1}{3}x + 5$ and $x_0 = 1$, how many iterations does the bound guarantee for an error below $0.001$?

$x_1 = \frac{16}{3}$, so $d(x_1, x_0) = \frac{13}{3}$, and $k = \frac{1}{3}$.
The bound is $\frac{(1/3)^{n}}{2/3}\cdot\frac{13}{3} = \frac{13}{2}\cdot\frac{1}{3^{n}} < 0.001$ when $3^{n} > 6500$.

Answer: $n = 8$ (since $3^{8} = 6561$). The fixed point is $\frac{15}{2}$.

Worked example: Close to $1$ is not enough

$g(x) = x + \frac{1}{x}$ on $[1, \infty)$ satisfies $|g(x) - g(y)| < |x - y|$ for $x \ne y$. Does it have a fixed point?

$x + \frac{1}{x} = x$ has no solution.
The ratio $|g'(x)| = 1 - \frac{1}{x^{2}}$ approaches $1$, so no single $k < 1$ works.

Answer: No: the theorem needs one constant $k < 1$.

Common mistake

Checking at one point, or forgetting "into itself." $|g'(x_0)| < 1$ at the fixed point gives convergence only for starting points close enough; the theorem needs $|g'| \le k$ on the whole set. And $g$ must map the set into itself: $g(x) = \frac{x}{2} + 3$ shrinks distances on $[0, 1]$, but sends $0$ to $3$, outside, and its fixed point $6$ is not in $[0, 1]$.

The Contraction Mapping Theorem

Worked examples

Practice

Builds on

Leads to

Sources and further reading