Contraction Mapping Theorem

When Iteration Must Converge to a Fixed Point

In Contractions, we saw that repeated application of a contraction produces a Cauchy sequence. That conclusion alone does not ensure a fixed point: the limit might not belong to the space, as the example on the open interval $(0,1)$ illustrated. The missing condition is completeness. In a complete metric space, every Cauchy sequence has a limit in the space, and contraction estimates make that limit a fixed point.

The resulting theorem is an existence-and-uniqueness principle. It does more than guarantee that a fixed point exists: starting from any point gives an iteration that converges to it. We state the theorem here and examine its consequences; the next tutorial gives its proof in full.

Theorem (Contraction Mapping Theorem): Let $(X,d)$ be a nonempty complete metric space, and let $f:X\to X$ be a contraction with contraction constant $q$, where $0\leq q<1$. Then $f$ has a unique fixed point $p\in X$. Moreover, for every starting point $x_0\in X$, the iterates defined by $x_{n+1}=f(x_n)$ converge to $p$.

The conditions play different roles. The self-map condition ensures that every iterate remains in $X$. Completeness supplies a limit in $X$ for the Cauchy sequence of iterates. The strict contraction estimate lets us identify that limit as a fixed point and, by the Uniqueness of a Fixed Point theorem, rules out any other fixed point. Nonemptiness is included because an empty space has no point that could be a fixed point.

The theorem is also constructive in a practical sense. It suggests a method: choose $x_0$, calculate $x_1=f(x_0)$, then continue. The iterates approach $p$, and estimates derived from the contraction constant tell us how close a particular iterate is likely to be. These estimates are useful even when solving $f(x)=x$ directly is difficult.

Estimating the Error in an Iteration

Suppose the theorem gives a fixed point $p$, and let $x_{n+1}=f(x_n)$. Consecutive steps shrink geometrically: the Cauchy Estimate for Successive Iterates gives $d(x_{n+1},x_n)\leq q^n d(x_1,x_0)$. The distance from an iterate to the fixed point can be bounded by adding all the remaining steps. A bound using just the most recent step is especially convenient when $p$ is unknown.

Theorem (A Posteriori Error Bound): Under the hypotheses of the Contraction Mapping Theorem, let $p$ be its fixed point and let $x_{n+1}=f(x_n)$. For every $n\geq0$, $$ d(x_n,p)\leq \frac{d(x_{n+1},x_n)}{1-q}. $$

Proof. The triangle inequality and the fixed-point identity $f(p)=p$ give

d(x_n,p) \leq d(x_n,x_{n+1})+d(x_{n+1},p) =d(x_n,x_{n+1})+d(f(x_n),f(p)).

Since $f$ is a contraction, $d(f(x_n),f(p))\leq q\,d(x_n,p)$. Therefore

d(x_n,p)\leq d(x_{n+1},x_n)+q\,d(x_n,p).

Subtracting $q\,d(x_n,p)$ from both sides yields $(1-q)d(x_n,p)\leq d(x_{n+1},x_n)$. Because $q<1$, the number $1-q$ is positive, so division gives the claimed bound. This argument also covers $q=0$. $\square$

This is called an a posteriori estimate because it uses a quantity already observed during the iteration: the distance between consecutive iterates. It does not require knowing $p$. There is also an a priori estimate, which uses the starting point and the number of steps. Summing the remaining geometric bounds gives

d(x_n,p) \leq \sum_{k=n}^{\infty}d(x_{k+1},x_k) \leq d(x_1,x_0)\sum_{k=n}^{\infty}q^k =\frac{q^n}{1-q}d(x_1,x_0).

For $q=0$, the iterates are constant from $x_1$ onward, and the displayed estimate is interpreted directly for $n\geq1$: then $d(x_n,p)=0$. For $0<q<1$, the factor $q^n$ explains why the bound improves geometrically as the number of iterations grows.

Worked Example: A Rational Contraction on a Closed Interval

Let $X=[0,1]$ with the usual distance, and define $f(x)=1/(2+x)$. If $x\in[0,1]$, then $2\leq2+x\leq3$, so $1/3\leq f(x)\leq1/2$. In particular, $f(x)\in[0,1]$, and $f$ is a self-map. For $x,y\in[0,1]$,

|f(x)-f(y)| =\left|\frac{1}{2+x}-\frac{1}{2+y}\right| =\frac{|x-y|}{(2+x)(2+y)} \leq\frac{1}{4}|x-y|,

because both factors in the denominator are at least $2$. Thus $f$ is a contraction with $q=1/4$. The interval $[0,1]$ is complete, so the Contraction Mapping Theorem guarantees a unique fixed point. Solving $x=1/(2+x)$ for $x\in[0,1]$ gives

x(2+x)=1 \quad\Longleftrightarrow\quad x^2+2x-1=0 \quad\Longleftrightarrow\quad x=-1\pm\sqrt{2}.

Of these roots, $-1+\sqrt{2}$ lies in $[0,1]$, while $-1-\sqrt{2}<0$. Substitution verifies the fixed point: $2+(-1+\sqrt{2})=1+\sqrt{2}$, and $1/(1+\sqrt{2})=\sqrt{2}-1$. Starting, for example, at $x_0=0$, the first iterate is $x_1=1/2$. The a posteriori bound gives $d(x_0,p)\leq (1/2)/(1-1/4)=2/3$; it is a guaranteed bound, not necessarily the exact error.

How Sensitive Is the Fixed Point?

The fixed point can also be stable under changes to the map. Suppose two contractions act on the same complete metric space and have the same contraction constant bound $q<1$. If their values are uniformly close, then their fixed points must be close. This conclusion is useful when a map is replaced by an approximation, or when the rule defining a problem changes slightly.

Theorem (Stability Under Perturbation): Let $(X,d)$ be a nonempty complete metric space. Suppose $f,g:X\to X$ are contractions with contraction constants at most $q<1$, and let $p$ and $r$ be their respective fixed points. If $d(f(x),g(x))\leq\varepsilon$ for every $x\in X$, then $$ d(p,r)\leq\frac{\varepsilon}{1-q}. $$

Proof. Since $p=f(p)$ and $r=g(r)$, the triangle inequality gives

d(p,r) =d(f(p),g(r)) \leq d(f(p),g(p))+d(g(p),g(r)).

The uniform closeness assumption bounds the first term by $\varepsilon$. The contraction inequality for $g$ bounds the second by $q\,d(p,r)$. Hence $d(p,r)\leq\varepsilon+q\,d(p,r)$. Rearranging and dividing by $1-q>0$ proves the estimate. $\square$

Worked Example: Comparing Two Affine Contractions

On $X=\mathbb{R}$ with the usual distance, let $f(x)=x/4+3$ and $g(x)=x/4+13/4$. Each is a self-map of $\mathbb{R}$, which is complete, and for either map the distance between images is $1/4$ times the distance between inputs. Thus both have contraction constant $q=1/4$.

The fixed point of $f$ solves $x=x/4+3$, so $3x/4=3$ and $p=4$; substitution gives $f(4)=1+3=4$. The fixed point of $g$ solves $x=x/4+13/4$, so $3x/4=13/4$ and $r=13/3$; substitution gives $g(13/3)=13/12+39/12=52/12=13/3$. For every $x$,

|f(x)-g(x)| =\left|3-\frac{13}{4}\right| =\frac{1}{4}.

The stability estimate therefore gives $|p-r|\leq (1/4)/(1-1/4)=1/3$. In fact, $|4-13/3|=1/3$, so equality holds in this example.

Completeness and the Other Hypotheses Matter

Completeness cannot simply be dropped from the theorem. The example on $(0,1)$ in Contractions already showed a contraction whose iterates approach a point outside the space. The condition $f:X\to X$ matters as well: if an iteration leaves $X$, it is no longer an iteration of a self-map on that space. Finally, a map that merely does not increase distances is not necessarily a contraction. For example, the identity map on $\mathbb{R}$ has every real number as a fixed point, so neither strict contraction nor uniqueness follows from nonexpansion alone.

The next example highlights the allowed endpoint $q=0$. In this case the map sends every point to one value, so a fixed point exists immediately when the map is a self-map of a nonempty space. This is consistent with the theorem, but it also illustrates why the hypotheses specify a nonempty domain.

Worked Example: A Contraction on a Finite Discrete Space

Let $X=\{a,b\}$ and give it the discrete metric: $d(u,v)=0$ if $u=v$, and $d(u,v)=1$ otherwise. This space is complete. Indeed, any Cauchy sequence is eventually constant: use the Cauchy condition with $\varepsilon=1$, after which all terms in the tail have distance less than $1$, hence distance $0$, from one another.

Define $f(a)=b$ and $f(b)=b$. For any $u,v\in X$, the images are both $b$, so $d(f(u),f(v))=0$. Thus $f$ is a contraction with $q=0$, and $b$ is a fixed point because $f(b)=b$. It is unique: $a$ is not fixed, since $f(a)=b\ne a$. Starting at either point reaches $b$ after at most one application of $f$, as the theorem predicts.

The theorem therefore supplies both a qualitative conclusion and a quantitative method. Completeness guarantees that iteration has somewhere to converge; contraction guarantees a unique destination and controls how quickly approximations approach it. When using the theorem, verify the space, the self-map property, and one uniform constant strictly below one before drawing its conclusion.

Check Your Understanding

Use the theorem and estimates in this tutorial to answer the following questions.

Which hypothesis ensures that the Cauchy sequence of iterates has a limit in $X$?
For the a posteriori error bound, why is it valid to divide by $1-q$?
If two contractions have a common contraction constant bound $q$ and differ everywhere by at most $\varepsilon$, what bound does the stability theorem give for their fixed points?
Why does the identity map on a metric space with more than one point not contradict the Contraction Mapping Theorem?
For the finite discrete-space example, verify that the defined map has contraction constant $0$, including when the two inputs differ.

What You'll Learn