Prove the Contraction Mapping Theorem

From Convergent Iterates to a Fixed Point

The Metric-Space Compactness Theorem showed how completeness helps turn Cauchy sequences into limits inside a space. A similar idea underlies the contraction mapping theorem: repeatedly apply a map that shrinks distances, and the resulting iterates converge. The earlier theorem Contraction Iteration Converges in a Complete Metric Space establishes that convergence. Here we complete the fixed-point argument, prove uniqueness, and derive estimates that make the method useful in applications.

A fixed point of a map $T:X\to X$ is a point $p\in X$ such that $T(p)=p$. The key hypothesis is stronger than continuity: distances between images must be reduced by a single factor strictly less than one, uniformly throughout the space. Completeness ensures that the limit produced by iteration belongs to the space, while the distance-shrinking condition makes that limit fixed and rules out competing fixed points.

Definition: Let $(X,d)$ be a metric space. A map $T:X\to X$ is a contraction if there is a constant $q$ with $0\leq q<1$ such that $d(Tx,Ty)\leq qd(x,y)$ for all $x,y\in X$. A point $p\in X$ is a fixed point of $T$ if $T(p)=p$.

The same constant $q$ must work for every pair of points. A map that merely reduces some distances, or is continuous without a uniform distance bound of this form, need not be a contraction. The case $q=0$ is allowed: then every pair of image points has distance zero, so $T$ is constant.

The Contraction Mapping Theorem

We use the established theorem Contraction Iteration Converges in a Complete Metric Space: for a contraction on a nonempty complete metric space, the iterates starting from any initial point converge to a point of the space. The next argument identifies that limit and shows it is the only possible fixed point.

Theorem (Contraction Mapping Theorem): Let $(X,d)$ be a nonempty complete metric space, and let $T:X\to X$ be a contraction. Then $T$ has exactly one fixed point $p\in X$. For every initial point $x_0\in X$, the sequence defined by $x_{n+1}=T(x_n)$ converges to $p$.

Proof. Choose any $x_0\in X$ and define $x_{n+1}=T(x_n)$ for every nonnegative integer $n$. By Contraction Iteration Converges in a Complete Metric Space, there is a point $p\in X$ such that $x_n\to p$. We show that $T(p)=p$.

Since $T$ is a contraction, it is continuous: whenever $y_n\to y$, the inequality $d(Ty_n,Ty)\leq qd(y_n,y)$ implies $d(Ty_n,Ty)\to0$. Applying this to $x_n\to p$ gives $T(x_n)\to T(p)$. But $T(x_n)=x_{n+1}$, and the shifted sequence $x_{n+1}$ also converges to $p$. Uniqueness of limits in a metric space therefore gives $T(p)=p$. This proves existence.

For uniqueness, suppose $p$ and $r$ are both fixed points. Then

d(p,r)=d(Tp,Tr)\leq qd(p,r).

Because $0\leq q<1$, this implies $(1-q)d(p,r)\leq0$. The distance is nonnegative and $1-q>0$, so $d(p,r)=0$, and hence $p=r$. Thus the fixed point is unique. Since the initial point $x_0$ was arbitrary, the iteration from every initial point converges; its limit must be the unique fixed point. $\square$

The existence step depends on both convergence and continuity. The iteration theorem supplies a limit in $X$, and the contraction inequality ensures that applying $T$ respects that limit. The uniqueness step is separate: it compares any two proposed fixed points directly. Keeping these roles distinct makes the proof easier to adapt.

Error Bounds for Successive Approximations

The theorem guarantees convergence, but in computation it is also useful to know how close an iterate is to the fixed point. The contraction inequality gives two types of estimate. One uses the initial error $d(x_0,p)$, which may be unknown; the other uses the observed distance between successive iterates.

Theorem (Error Estimates for Contraction Iteration): Under the hypotheses of the Contraction Mapping Theorem, let $p$ be the unique fixed point and define $x_{n+1}=T(x_n)$. For every nonnegative integer $n$, $$ d(x_n,p)\leq q^n d(x_0,p). $$ If $n\geq0$, then also $$ d(x_n,p)\leq \frac{q^n}{1-q}d(x_1,x_0) \qquad\text{and}\qquad d(x_n,p)\leq\frac{d(x_n,x_{n+1})}{1-q}. $$

Proof. Since $T(p)=p$, the contraction inequality gives

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

Starting at $n=0$ and applying this inequality repeatedly proves by induction that $d(x_n,p)\leq q^n d(x_0,p)$. This is the first estimate, including the case $n=0$, where it is equality. When $q=0$, the estimate for positive $n$ says $d(x_n,p)=0$, as it should: a constant map reaches its fixed point after one application.

For the second estimate, repeated use of the contraction inequality gives

d(x_k,x_{k+1})\leq q^k d(x_0,x_1) \qquad(k\geq0).

For any integer $m>n$, the triangle inequality along the iterates yields

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

Letting $m$ tend to infinity and using $x_m\to p$ gives $d(x_n,p)\leq q^n d(x_0,x_1)/(1-q)$. This argument also covers $q=0$: for $n=0$ the bound is $d(x_0,p)\leq d(x_0,x_1)$, and for $n\geq1$ the iterate is already the fixed point.

Finally, the triangle inequality and the contraction property give

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

Subtracting $q\,d(x_n,p)$ from both sides and dividing by $1-q>0$ proves the last estimate. $\square$

The a priori estimate is most informative when the initial distance to the fixed point is known. The a posteriori estimate uses only the latest step size, so it can be applied while calculating: if successive approximations are close, the fixed point is close as well, with a factor depending on $q$.

Worked Applications and Hypothesis Checks

Worked Example: An Affine Contraction on the Real Line

Define $T:\mathbb{R}\to\mathbb{R}$ by $T(x)=(2x+3)/5$. For any real $x,y$,

|T(x)-T(y)| =\left|\frac{2x+3}{5}-\frac{2y+3}{5}\right| =\frac{2}{5}|x-y|.

Thus $T$ is a contraction with $q=2/5$. The real line is complete and nonempty, so the theorem gives a unique fixed point. Solving the fixed-point equation verifies its value:

x=\frac{2x+3}{5} \quad\Longleftrightarrow\quad 5x=2x+3 \quad\Longleftrightarrow\quad x=1.

Indeed, $T(1)=(2+3)/5=1$. Starting from any $x_0$, subtracting the fixed-point equation from the iteration gives $x_{n+1}-1=(2/5)(x_n-1)$. Induction therefore yields $x_n=1+(2/5)^n(x_0-1)$, which converges to $1$.

Worked Example: A Nonlinear Contraction on a Closed Interval

Let $X=[0,1]$ with its usual metric and define $T(x)=(1+x^2)/4$. For $x\in[0,1]$, we have $1/4\leq T(x)\leq1/2$, so $T$ maps $X$ into itself. For $x,y\in[0,1]$,

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

because $x+y\leq2$. Thus $T$ is a contraction with $q=1/2$. The interval $[0,1]$ is complete: a Cauchy sequence in it converges in $\mathbb{R}$, and preservation of order under limits keeps its limit in $[0,1]$. The theorem guarantees a unique fixed point. Its equation is

x=\frac{1+x^2}{4} \quad\Longleftrightarrow\quad x^2-4x+1=0.

The roots are $2-\sqrt{3}$ and $2+\sqrt{3}$. Since $1<\sqrt{3}<2$, we have $0<2-\sqrt{3}<1$, while $2+\sqrt{3}>1$. Hence the only root in $X$ is $2-\sqrt{3}$, the unique fixed point.

Worked Example: A Contraction Without a Fixed Point on an Incomplete Space

Consider $X=(0,1)$ with the usual metric and $T(x)=(x+1)/2$. For every $x\in(0,1)$, $1/2<T(x)<1$, so $T$ maps $X$ into itself. Moreover,

|T(x)-T(y)|=\frac12|x-y|,

so $T$ is a contraction. A fixed point would have to satisfy $x=(x+1)/2$, which implies $x=1$, but $1\notin X$. Thus this contraction has no fixed point in $X$. The space is not complete: the sequence $x_n=1-1/n$, for $n\geq2$, is Cauchy in $X$ and converges in $\mathbb{R}$ to $1$, which is not in $X$. This example shows why completeness cannot simply be omitted.

What the Theorem Does—and Does Not—Say

The fixed-point conclusion requires all the hypotheses to work together. The map must send points of $X$ back into $X$; the space must be complete; and one strict contraction factor must control every pair of points. If the factor is allowed to equal $1$, uniqueness can fail. For example, the identity map on $[0,1]$ preserves every point, so every point is fixed, but it is not a contraction with $q<1$.

A common proof error is to establish that the iterates converge and then declare their limit fixed without explaining why applying $T$ preserves the limit. Here that step follows from the contraction inequality itself, which implies continuity. Another error is to use the estimate $d(x_n,p)\leq q^n d(x_0,p)$ as a practical stopping rule when $d(x_0,p)$ is unknown. The a posteriori estimate avoids that problem by bounding the error using the computable distance $d(x_n,x_{n+1})$.

Check the map.
Verify that $T(x)\in X$ for every $x\in X$.

Check the contraction factor.
Find one $q<1$ that bounds $d(Tx,Ty)/d(x,y)$ for all distinct $x,y$.

Use completeness for existence.
The contraction iteration theorem gives a limit in $X$; continuity makes that limit a fixed point.

Use strict shrinking for uniqueness and estimates.
Compare two fixed points, or bound the distance from an iterate to the fixed point.

Check Your Understanding

Use the hypotheses and estimates in the proof to answer these questions.

At what point in the existence proof is continuity of $T$ used, and how does the contraction inequality provide it?
Why does $d(p,r)\leq qd(p,r)$, with $q<1$, force two fixed points $p$ and $r$ to be equal?
For the affine contraction in the first example, what does the a priori error estimate say about $d(x_n,1)$?
Why does the map $T(x)=(x+1)/2$ on $(0,1)$ not contradict the Contraction Mapping Theorem?
Which error estimate can be used when the distance from the initial point to the fixed point is not known?