Contraction Mapping Principle

A contraction

d(Tx,Ty) \le q\,d(x,y)

(

q<1

) on a complete metric space has a unique fixed point — the Picard iterates

x_{n+1} = Tx_n

tighten inside the error ball

\frac{q^n}{1-q}|x_1-x_0|

T(x) = x/2

(0,1]

shows why completeness is essential: a contraction with no fixed point.

Examples & Exercises

For the Picard iterates $x_{n+1} = Tx_n$ of a contraction $T$ ( $d(Tx,Ty) \le q\,d(x,y)$ , $q<1$ ), show $d(x_n,x_m) \le \frac{q^n}{1-q}\,d(x_0,x_1)$ for $m>n$ , and prove $(x_n)$ is Cauchy.

d(x_{k+1},x_{k+2}) \le q\,d(x_k,x_{k+1}) \le q^{k+1}\,d(x_0,x_1)

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

n=8

: the Cauchy tail bound

2^{-8} \approx 0.0039

— every

x_m

with

m>8

lands inside it.

Show proof

Squeeze one step at a time: $d(x_{k+1},x_{k+2}) = d(Tx_k,Tx_{k+1}) \le q\,d(x_k,x_{k+1})$ , so by induction $d(x_k,x_{k+1}) \le q^k\,d(x_0,x_1)$ for every $k$ .
For $m>n$ , chaining the triangle inequality gives $d(x_n,x_m) \le \sum_{k=n}^{m-1} d(x_k,x_{k+1}) \le \left(\sum_{k=n}^{m-1} q^k\right) d(x_0,x_1)$ . Extending the sum to $\infty$ yields the geometric tail $\sum_{k=n}^{\infty} q^k = \frac{q^n}{1-q}$ , so $d(x_n,x_m) \le \frac{q^n}{1-q}\,d(x_0,x_1)$ .
The right side tends to $0$ as $n \to \infty$ , independently of $m$ , so $(x_n)$ is Cauchy. With $q = 1/2$ and $x_0 = 1$ , $d(x_1,x_0) = 1/2$ makes the bound $2^{-n}$ ; at $n = 8$ it is $\frac{1}{256} \approx 0.0039$ — matching the caption's figure.

Show that $T(x) = x/2$ is a contraction with $q = 1/2$ on $(0,1]$ , yet has no fixed point in $(0,1]$ . This is why completeness is essential.

|T(x) - T(y)| = \tfrac12|x - y|, \qquad T\big((0,1]\big) \subset (0,1]

x_0 = 1 \Rightarrow x_n = 2^{-n} \to 0 \notin (0,1]

n=8

x_8 = 2^{-8} \approx 0.0039

— the iterates drain toward the missing limit

0

Show proof

Since $|T(x) - T(y)| = \left|\frac{x}{2} - \frac{y}{2}\right| = \frac12|x - y|$ , $T$ is a contraction with $q = 1/2$ . And $x \in (0,1]$ gives $T(x) = x/2 \in (0, 1/2] \subset (0,1]$ , so $T$ maps $(0,1]$ into itself.
A fixed point would satisfy $x = x/2$ , i.e. $x = 0$ , but $0 \notin (0,1]$ . Hence $T$ has no fixed point in $(0,1]$ .
Starting from $x_0 = 1$ gives $x_n = 2^{-n}$ : $1, \frac12, \frac14, \dots$ . This sequence satisfies the geometric bound from the first problem, so it is Cauchy — but its limit $0$ lies outside the space. Without completeness a Cauchy sequence loses its "place to land" and the whole theorem collapses; at $n = 8$ , $x_8 = \frac{1}{256} \approx 0.0039$ , matching the caption's figure.

On a complete metric space, derive the error bound $d(x_n,x^*) \le \frac{q^n}{1-q}\,d(x_1,x_0)$ for the fixed point $x^*$ of a contraction, and prove there is at most one fixed point.

d(x_n,x^*) = \lim_{m \to \infty} d(x_n,x_m) \le \frac{q^n}{1-q}\,d(x_1,x_0)

|x^* - y^*| = |Tx^* - Ty^*| \le q|x^* - y^*| \Rightarrow x^* = y^*

n=8

|x_8 - 2| = 1/256 \approx 0.0039

— matches the bound exactly.

Show proof

Completeness makes the Cauchy sequence $(x_n)$ converge to a point $x^*$ inside the space. A contraction is continuous since $|Tx - Ty| \le q|x - y|$ , so $Tx^* = T(\lim x_n) = \lim Tx_n = \lim x_{n+1} = x^*$ — $x^*$ is a fixed point.
Letting $m \to \infty$ in the first problem's estimate (and $d(x_1,x_0) = d(x_0,x_1)$ ) gives the error bound $d(x_n,x^*) \le \frac{q^n}{1-q}\,d(x_1,x_0)$ . For $T(x) = x/2 + 1$ with $q = 1/2$ and $x_0 = 1$ , the bound is $\frac{(1/2)^8}{1/2}\cdot\frac12 = \frac{1}{256} \approx 0.0039$ , and the actual iterate $x_8 = 2 - 2^{-8} = 1.99609375$ has error $|x_8 - 2| = \frac{1}{256}$ , matching the bound exactly.
Uniqueness: if $x^*$ and $y^*$ are both fixed points, $|x^* - y^*| = |Tx^* - Ty^*| \le q|x^* - y^*|$ . Since $q < 1$ , this forces $|x^* - y^*| = 0$ , i.e. $x^* = y^*$ .

Contraction Mapping Principle

Part of these learning paths

Examples & Exercises