Fixed Points and Contraction Mappings

Fixed point

A fixed point of a function $f$ is a point that $f$ does not move:

$$f(c) = c$$

Graphically, it is an intersection point of the graph of $f$ with the line $y = x$. Solving an equation $g(x) = 0$ can always be turned into a fixed-point search, for instance by setting $f(x) = x + g(x)$ or $f(x) = x - \dfrac{g(x)}{\lambda}$: this change of viewpoint is what makes iteration possible.

Contraction mappings

A function $f$ defined on a subset $X$ of $\mathbb{R}$ is a contraction — also called $k$-contracting — if there exists a constant $k$ with $0 \leq k < 1$ such that

$$\forall (x, y) \in X^2,\quad \lvert f(x) - f(y) \rvert \leq k\,\lvert x - y \rvert$$

This is exactly the definition of a $k$-Lipschitz function, with the additional and decisive requirement $k < 1$: the function brings points closer together, by a factor of at least $k$ each time it is applied.

The mean value inequality gives the practical criterion: if $f$ is differentiable on an interval $I$ with $\lvert f'(x) \rvert \leq k < 1$, then $f$ is $k$-contracting on $I$.

Examples and counterexamples

Function	Domain	Contraction?
$f(x) = \cos x$	$[0 \,;\, 1]$	yes, $k = \sin 1 \approx 0.841$
$f(x) = \dfrac{x + 5}{3}$	$\mathbb{R}$	yes, $k = \dfrac{1}{3}$
$f(x) = \dfrac{1}{2}\left(x + \dfrac{2}{x}\right)$	$[1 \,;\, 2]$	yes, $k = \dfrac{1}{2}$
$f(x) = x + 1$	$\mathbb{R}$	no, $k = 1$
$f(x) = x^2$	$[0 \,;\, 2]$	no, $\lvert f' \rvert$ reaches $4$

Let us detail the first row: on $[0 \,;\, 1]$, $\lvert \cos'(x) \rvert = \lvert \sin x \rvert \leq \sin 1 \approx 0.841 < 1$, since sine is increasing on this interval. The cosine function is therefore a contraction there.

Classic pitfall

Confusing "contraction" with "strictly brings points closer". The condition

$$\forall x \neq y,\quad \lvert f(x) - f(y) \rvert < \lvert x - y \rvert$$

is weaker than being a contraction, and it is not enough. On $\left[1 \,;\, +\infty\right[$, the function $f(x) = x + \dfrac{1}{x}$ satisfies $f'(x) = 1 - \dfrac{1}{x^2} \in \left[0 \,;\, 1\right[$, so it strictly brings every pair of points closer — and yet it has no fixed point, since $f(x) = x$ would require $\dfrac{1}{x} = 0$. What is missing is a uniform constant $k < 1$.