4.2 Convergence, completeness and the contraction mapping theorem

A space is complete when every sequence whose terms bunch together has a limit in the space. A map that shrinks every distance by a fixed factor below 1, run again and again in a complete space, always settles on exactly one fixed point. That is how cos x = x, Newton's method, PageRank and reinforcement-learning value iteration all work.

Chapter 1.2 ended on a fact about the real line: a sequence of real numbers converges if and only if its terms bunch together (the Cauchy criterion). The fact is what lets us prove a limit exists without knowing its value. Does it hold in other metric spaces? In $\mathbb Q$ it fails, and in the space of continuous functions it holds. The spaces where it holds are called complete, and they are where equations get solved. The method is to start with any guess, improve it by a rule that brings every pair of points closer together by a fixed factor, and let the sequence of guesses run. The guesses bunch, completeness gives them somewhere to land, and the landing point solves the equation.

Before you start

4.1: metric space, open ball, closed set and the sup metric. 1.2: the Cauchy criterion. 1.6: uniform convergence and the geometric series.

Quick checkWhich sequence of rational numbers has terms that bunch together (is Cauchy) but has no limit in

\mathbb Q

Quick checkIn the sup metric on

C[0, 1]

, what does

d(f, g) < 0.1

say about the graphs?

Quick checkFor

0 \le q < 1

, what is

1 + q + q^2 + q^3 + \cdots

The picture: the staircase that closes in

We want a number $x$ with $\cos x = x$ . Nobody has a formula, but here is a method: start anywhere, press the cosine key on a calculator, and press it again on the answer, over and over. The picture shows what happens. The curve is $y = \cos x$ and the dashed line is $y = x$ . A solution is a point where they cross. Going up or down from the dashed line to the curve applies the map. Going sideways back to the dashed line copies the output into the next input. The red and green segments form a staircase (a cobweb) that closes in on the crossing point. Three things to do:

Run the cosine preset from several starting points. The staircase always lands on the same point, $x^* \approx 0.7390851$ .
Switch to “Newton for x² − 2”. The curve is almost flat where it crosses the line, and the path lands on $\sqrt 2$ in two or three rounds.
Switch to “−1.5x + 1.25”. There is still a crossing, but the staircase spirals outward. The map pushes points apart instead of together. The difference between the two behaviours is whether the slope at the crossing has size below $1$ .

$n$	$x_n$	error $\lvert x_n - x^*\rvert$
$0$	$1$	$0.2609$
$1$	$0.5403$	$0.1988$
$2$	$0.8576$	$0.1185$
$3$	$0.6543$	$0.0848$
$5$	$0.7014$	$0.0377$
$10$	$0.7442$	$0.0052$

The error drops by a factor of about $0.67$ per step, which is the size of the slope of the cosine curve at the crossing, $\lvert \sin 0.739 \rvert \approx 0.674$ .

Where this came from· Picard's iteration, Banach's abstraction

Émile Picard’s memoir of 1890 on partial differential equations used the method of successive approximations: to solve an equation, start from a guess, plug it into the right-hand side to get a better guess, and repeat. In 1893 he applied the same method to ordinary differential equations and showed that the guesses converge. Stefan Banach’s doctoral work in Lwów (written around 1920, published in 1922 in Fundamenta Mathematicae, volume 3, under the title Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales) set the idea in abstract spaces and proved the fixed point theorem of this chapter. The abstract version isolates exactly what the iteration needs: a space where bunching sequences have limits, and a map that shrinks every distance by a fixed factor. Picard’s theorem for differential equations and the theorems for integral equations became applications of one result, which is why it carries Banach’s name.

The idea, in words

Three ideas, each one a line in the picture.

Why· Convergence, completeness, contraction

Convergence in a metric space is the game of 1.2 with the distance $d$ in place of $|x - y|$ : $x_n \to x$ means $d(x_n, x)$ goes to $0$ .
Completeness says there are no holes. If the terms of a sequence bunch together, there is a point at the place where they are bunching. $\mathbb R$ has this; $\mathbb Q$ does not (the truncations of $\sqrt 2$ bunch at a hole), and neither does $(0, 1]$ (the sequence $\frac1n$ bunches at $0$ , which is not in the space).
A contraction is a map $T$ with $d(Tx, Ty) \le q\,d(x, y)$ for a fixed $q < 1$ : it brings every pair of points closer together by the same factor. Applying it again and again, the steps $d(x_{n+1}, x_n)$ shrink geometrically, so their sum is finite and the sequence bunches. Completeness provides the limit, and the limit is fixed by $T$ because $T$ is continuous. Two different fixed points are impossible, because a contraction would bring them closer together, yet each stays put.

Definitions and theorems: convergence

Definition B

Convergent sequence in a metric space

Let $(x_n)$ be a sequence of points in a metric space $(X, d)$ . It converges to $x \in X$ , written $x_n \to x$ , if

\forall \varepsilon > 0\ \ \exists N\ \ \forall n > N:\quad d(x_n, x) < \varepsilon.

Equivalently, every open ball $B(x, \varepsilon)$ contains all but finitely many terms. For $X = \mathbb R$ with $d = |x - y|$ this is the definition of 1.2.

In one line $x_n \to x$ if the distance $d(x_n, x)$ tends to $0$ : for every $\varepsilon > 0$ , all terms after some index lie in the ball $B(x, \varepsilon)$ .

Why it existsIt is the $\varepsilon$ - $N$ game of 1.2 with the distance of the space in place of $|a_n - L|$ , so every theorem about limits can be re-proved with only (M1) to (M3).

Theorem B Rudin ch. 3; Abbott Sec. 2.2

Limits in a metric space are unique

If $x_n \to x$ and $x_n \to y$ in a metric space, then $x = y$ .

In one lineA sequence in a metric space converges to at most one point.

Why it is trueGive each limit half the budget: eventually the terms are within $\varepsilon/2$ of both, so the two limits are within $\varepsilon$ of each other, and (M1) turns 'within every $\varepsilon$ ' into 'equal'.

ProofAbbott Sec. 2.2

The idea: The same ε/2 proof as in 1.2, using only (M1) to (M3).

Let

\varepsilon > 0

Arbitrary tolerance.

Choose

N

with

d(x_n, x) < \frac\varepsilon2

and

d(x_n, y) < \frac\varepsilon2

for

n > N

Convergence to

x

and to

y

, each with tolerance

\varepsilon/2

; take the later of the two starting indices.

For such

n

d(x, y) \le d(x, x_n) + d(x_n, y) < \varepsilon

(M3) through

x_n

, and (M2) to turn

d(x, x_n)

into

d(x_n, x)

d(x, y) = 0

and

x = y

\blacksquare

A non-negative number below every positive

\varepsilon

0

, and (M1):

d(x, y) = 0

means

x = y

Theorem B standard; Apostol Sec. 8.4

Convergence in R^n is coordinatewise

Let $x^{(k)} = (x^{(k)}_1, \dots, x^{(k)}_n) \in \mathbb R^n$ and $x = (x_1, \dots, x_n)$ . Then $x^{(k)} \to x$ in $d_1$ , or in $d_2$ , or in $d_\infty$ , if and only if $x^{(k)}_i \to x_i$ for every $i$ .

In one lineA sequence of vectors converges in $\mathbb R^n$ (for any of the 1-, 2- or max-distances) if and only if each coordinate converges as a sequence of real numbers.

Why it is trueBy the comparison theorem of 4.1 the three norms are within factors of $n$ of each other and of the size of any single coordinate, so 'the vector is within $\varepsilon$ ' and 'every coordinate is within about $\varepsilon$ ' are the same statement.

Proofstandard

The idea: Sandwich each coordinate gap between norms: one coordinate is at most the max-norm, which is at most the 2-norm, at most the 1-norm; and the 1-norm is at most n times the max-norm.

For every

i

\lvert x^{(k)}_i - x_i \rvert \le \lVert x^{(k)} - x \rVert_\infty \le \lVert x^{(k)} - x \rVert_2 \le \lVert x^{(k)} - x \rVert_1

By the comparison theorem of 4.1 (the 1-, 2- and max-norms), applied to the vector

x^{(k)} - x

(

\Rightarrow

) If

x^{(k)} \to x

in one of the three distances, every coordinate converges.

Each coordinate gap is at most each of the three norms, by the chain. If one of those three tends to

0

(whichever distance we assumed), the coordinate gap, which is non-negative and below it, is squeezed to

0

(

\Leftarrow

) Let

\varepsilon > 0

. There is

N

with

\lvert x^{(k)}_i - x_i \rvert < \frac\varepsilon n

for all

i

and all

k > N

Each coordinate converges, so each has its own starting index for tolerance

\varepsilon/n

; take the largest of the

n

indices.

\lVert x^{(k)} - x \rVert_\infty \le \lVert x^{(k)} - x \rVert_2 \le \lVert x^{(k)} - x \rVert_1 < \varepsilon

. All three distances are below

\varepsilon

\blacksquare

For such

k

\lVert x^{(k)} - x \rVert_\infty < \frac\varepsilon n

. Then

\lVert \cdot \rVert_1 \le n\,\lVert \cdot \rVert_\infty

from 4.1, and

\lVert \cdot \rVert_\infty \le \lVert \cdot \rVert_2 \le \lVert \cdot \rVert_1

Theorem B Rudin ch. 7; Abbott Sec. 6.2

Convergence in the sup metric is uniform convergence

Let $f_n, f \in C[a, b]$ . Then $f_n \to f$ in the sup metric if and only if $f_n \to f$ uniformly on $[a, b]$ .

In one lineFor continuous $f_n$ and $f$ on $[a, b]$ : $d_\infty(f_n, f) \to 0$ if and only if $f_n \to f$ uniformly on $[a, b]$ .

Why it is trueThe sup metric is the largest vertical gap, and 'the largest gap is below $\varepsilon$ ' says the same as 'every gap is below $\varepsilon$ '. The $N$ that works for all $x$ at once is the $N$ that makes the largest gap small.

ProofAbbott Sec. 6.2

The idea: Unpack both definitions side by side. They differ only by 'max of the gap is below ε' versus 'every gap is below ε', and these are equivalent because the maximum is one of the gaps.

Sup metric:

\forall \varepsilon\ \exists N\ \forall n > N:\ \max_{x \in [a, b]} \lvert f_n(x) - f(x) \rvert < \varepsilon

The definition of convergence in a metric space, with

d_\infty(f_n, f) = \max_x \lvert f_n(x) - f(x) \rvert

Uniform:

\forall \varepsilon\ \exists N\ \forall n > N\ \forall x \in [a, b]:\ \lvert f_n(x) - f(x) \rvert < \varepsilon

The definition of uniform convergence in 1.6: one

N

for all

x

at once.

So the first implies the second for the same

N

If the maximum of the gaps is below

\varepsilon

, every gap is, since each is at most the maximum.

If every gap is below

\varepsilon

, the maximum is a gap, so it is below

\varepsilon

. Hence the second implies the first.

\blacksquare

The maximum is attained at some point (extreme value theorem, 1.3), and at that point the gap is below

\varepsilon

In the picture of 1.6, the open ball $B(f, \varepsilon)$ in the sup metric is the tube of half-height $\varepsilon$ around the graph of $f$ : a function $g$ is in the ball exactly when its whole graph fits in the tube. Convergence in the sup metric is the graphs $f_n$ fitting into every tube eventually.

Theorem B Rudin ch. 3; Abbott Sec. 3.2

Closed sets and limits of sequences

In a metric space: (a) $x \in \overline A$ iff there are points $a_n \in A$ with $a_n \to x$ . (b) $A$ is closed iff ( $a_n \in A$ and $a_n \to x$ imply $x \in A$ ).

In one lineA point lies in the closure of $A$ if and only if some sequence in $A$ converges to it. Hence $A$ is closed if and only if the limit of every convergent sequence of points of $A$ lies in $A$ .

Why it is trueA point in the closure has a point of $A$ in each ball $B(x, \frac1n)$ , and those points converge to $x$ ; conversely a sequence in $A$ tending to $x$ puts points of $A$ in every ball around $x$ .

ProofAbbott Sec. 3.2

The idea: (a) Choose a_n in the ball of radius 1/n, for the forward direction; use a ball containing late terms for the backward. (b) A closed iff A equals its closure, and (a) describes the closure.

(a,

\Rightarrow

) Let

x \in \overline A

. For each

n

, pick

a_n \in A \cap B(x, \frac1n)

By the definition of the closure in 4.1, every ball around

x

meets

A

Then

a_n \to x

d(a_n, x) < \frac1n \to 0

(a,

\Leftarrow

) If

a_n \in A

and

a_n \to x

, every ball

B(x, r)

contains some

a_n \in A

, so

x \in \overline A

Convergence: given

r > 0

, all late terms are in

B(x, r)

, and they are points of

A

(b)

A

is closed iff

\overline A \subseteq A

iff every limit of a sequence in

A

is in

A

, by (a).

\blacksquare

The theorem on interior, closure and boundary in 4.1, part (b):

A

is closed iff

A = \overline A

, and always

A \subseteq \overline A

Definitions and theorems: Cauchy sequences and completeness

Definition B

Cauchy sequence in a metric space

A sequence $(x_n)$ in a metric space is Cauchy if $\forall \varepsilon > 0\ \exists N\ \forall m, n > N:\ d(x_m, x_n) < \varepsilon$ . (For $\mathbb R$ this is the Cauchy sequence of 1.2.)

In one lineA sequence whose terms eventually stay close to each other: for every $\varepsilon > 0$ there is $N$ with $d(x_m, x_n) < \varepsilon$ for all $m, n > N$ .

Why it existsIt describes bunching without naming a limit, so we can prove a limit exists when we cannot find it.

Theorem B Rudin Thm 3.11(a)

Convergent sequences are Cauchy

Every convergent sequence in a metric space is a Cauchy sequence.

In one lineIf $x_n \to x$ in a metric space, then $(x_n)$ is Cauchy.

Why it is trueTerms close to $x$ are close to each other: split $d(x_m, x_n)$ through $x$ with $\varepsilon/2$ each.

ProofRudin 3.11

The idea: Triangle inequality through the limit.

Let

\varepsilon > 0

and choose

N

with

d(x_n, x) < \frac\varepsilon2

for

n > N

Arbitrary tolerance, and half of it for each term.

For

m, n > N

d(x_m, x_n) \le d(x_m, x) + d(x, x_n) < \frac\varepsilon2 + \frac\varepsilon2 = \varepsilon

\blacksquare

(M3) and (M2).

The converse is what fails in some spaces and holds in others, and that difference is the next definition.

Definition B

Complete metric space

A metric space $X$ is complete if every Cauchy sequence in $X$ converges to a point of $X$ .

In one lineA metric space in which every Cauchy sequence converges to a point of the space.

Why it existsIt is the 'no holes' property. It lets us construct solutions as limits of approximations without knowing the solution in advance.

Worked example

Decide whether each space is complete:

\mathbb R

\mathbb Q

(0, 1]

[0, 1]

, and a set with the discrete metric.

Solution.

$\mathbb R$ is complete. Every Cauchy sequence of reals converges. That is the Cauchy criterion of 1.2, which rests on the completeness axiom of 1.1.
$\mathbb Q$ is not. The truncations $1, 1.4, 1.41, 1.414, \dots$ of $\sqrt 2$ are rational and Cauchy, but their only limit in $\mathbb R$ is $\sqrt 2 \notin \mathbb Q$ , and limits are unique. The Cauchy sequence bunches at a hole of $\mathbb Q$ , which we know by uniqueness of limits.
$(0, 1]$ is not. The sequence $x_n = \frac1n$ is Cauchy (it converges in $\mathbb R$ ), but its limit $0$ is not in $(0, 1]$ . The point missing from the space is the endpoint $0$ . No point of $(0, 1]$ can serve as a limit, since the limit in $\mathbb R$ is unique.
$[0, 1]$ is complete. A Cauchy sequence in $[0, 1]$ converges in $\mathbb R$ to some $x$ , and $0 \le x_n \le 1$ passes to the limit, so $x \in [0, 1]$ . Closed subsets keep their limits. This is the idea of the theorem on closed subsets below.
A set with the discrete metric is complete. For $\varepsilon = \frac12$ , $d(x_m, x_n) < \frac12$ forces $d(x_m, x_n) = 0$ , that is, $x_m = x_n$ , for all $m, n > N$ . So a Cauchy sequence is constant from some point, and it converges to that constant. The metric takes only the values $0$ and $1$ , so “close” means “equal”.

Answer. Complete: $\mathbb R$ , $[0, 1]$ , discrete spaces. Not complete: $\mathbb Q$ , $(0, 1]$ . $\blacksquare$

Quick checkWhich of these is a complete metric space with the usual distance

|x - y|

Theorem B Rudin Thm 3.11(c); Apostol Sec. 8.4

R^n is complete

Every Cauchy sequence in $\mathbb R^n$ (with $d_1$ , $d_2$ or $d_\infty$ ) converges.

In one line $\mathbb R^n$ with the 1-, 2- or max-distance is complete.

Why it is trueA Cauchy sequence of vectors has Cauchy coordinates, each coordinate sequence converges in the complete line $\mathbb R$ , and convergence is coordinatewise.

ProofRudin 3.11

The idea: Cauchy in the vector implies Cauchy in each coordinate (a coordinate gap is at most the norm), so each coordinate converges by completeness of R, and then the vector converges by the coordinatewise theorem.

Let

(x^{(k)})

be Cauchy. Then, for each coordinate

i

, the real sequence

(x^{(k)}_i)_k

is Cauchy.

The first link of the chain in the coordinatewise proof:

\lvert x^{(k)}_i - x^{(l)}_i \rvert \le \lVert x^{(k)} - x^{(l)} \rVert_\infty \le \lVert x^{(k)} - x^{(l)} \rVert_2 \le \lVert x^{(k)} - x^{(l)} \rVert_1

x^{(k)}_i \to x_i

for some real number

x_i

, for each

i

\mathbb R

is complete (1.2).

Put

x = (x_1, \dots, x_n)

. Then

x^{(k)} \to x

in the vector distance.

\blacksquare

The theorem that convergence in R^n is coordinatewise, proved above.

The space of continuous functions is complete

This is the theorem where 1.6 and this unit meet. A Cauchy sequence of continuous functions is a sequence of graphs that bunch together in the tube sense. We must produce a limit function that is itself continuous.

Theorem B Rudin ch. 7; Abbott Sec. 6.2

C[a, b] with the sup metric is complete

The metric space $C[a, b]$ with $d_\infty(f, g) = \max_{[a, b]} \lvert f - g \rvert$ is complete.

In one lineEvery Cauchy sequence of continuous functions on $[a, b]$ , in the sup metric, converges uniformly to a continuous function.

Why it is trueFix $x$ : the numbers $f_n(x)$ are a Cauchy sequence of reals, so they converge. That defines a limit function. The Cauchy condition gives the same $N$ for every $x$ , so the convergence is uniform, and a uniform limit of continuous functions is continuous.

ProofRudin ch. 7

The idea: Build the limit function point by point using completeness of R, show the convergence is uniform because the Cauchy N does not depend on x, and then show the limit is continuous with the 3-epsilon argument (the theorem of 1.6, written out again here).

Let

(f_n)

be a Cauchy sequence in

C[a, b]

for

d_\infty

By hypothesis:

\forall \varepsilon\ \exists N\ \forall m, n > N:\ \max_x \lvert f_n(x) - f_m(x) \rvert < \varepsilon

Fix

x \in [a, b]

. The real sequence

(f_n(x))_n

is Cauchy.

For one fixed

x

\lvert f_n(x) - f_m(x) \rvert \le d_\infty(f_n, f_m)

, because the maximum is at least the value at

x

.Where the idea comes from: evaluate at a point, and the sup metric becomes a plain distance in R.

So it converges. Define

f(x) = \lim_n f_n(x)

for each

x \in [a, b]

. This is the pointwise limit, a function on

[a, b]

that we do not yet know is continuous.

\mathbb R

is complete (1.2, Cauchy criterion).

Let

\varepsilon > 0

and choose

N

with

d_\infty(f_n, f_m) < \frac\varepsilon2

for all

m, n > N

Arbitrary tolerance; use half of it for the Cauchy condition.

For all

x \in [a, b]

and all

n > N

\lvert f_n(x) - f(x) \rvert \le \frac\varepsilon2 < \varepsilon

Fix any

x

and any

n > N

. For every

m > N

\lvert f_n(x) - f_m(x) \rvert < \frac\varepsilon2

. Let

m \to \infty

f_m(x) \to f(x)

, and a bound that holds along a convergent sequence holds in the limit, in the non-strict form.This is the key step: N was chosen before x, so the same N serves every point.

f_n \to f

uniformly on

[a, b]

This is the definition of uniform convergence in 1.6: one

N

for all

x

at once.

Let

c \in [a, b]

and

\varepsilon > 0

. By uniform convergence, pick one index

n

with

|f_n(x) - f(x)| < \frac\varepsilon3

for every

x \in [a, b]

We must show the pointwise limit

f

is continuous at an arbitrary point

c \in [a, b]

: for every

\varepsilon

\delta

with

|f(x) - f(c)| < \varepsilon

when

|x - c| < \delta

. We have no formula for

f

, so we compare it with a function we do understand, one

f_n

.This is the 3-epsilon argument, the same one as in the theorem of 1.6 that a uniform limit of continuous functions is continuous.

Choose

\delta > 0

with

|f_n(x) - f_n(c)| < \frac\varepsilon3

whenever

|x - c| < \delta

f_n

is continuous at

c

(it is in

C[a, b]

), so there is

\delta > 0

that keeps

f_n(x)

within

\frac\varepsilon3

f_n(c)

For

|x - c| < \delta

|f(x) - f(c)| \le |f(x) - f_n(x)| + |f_n(x) - f_n(c)| + |f_n(c) - f(c)| < \frac\varepsilon3 + \frac\varepsilon3 + \frac\varepsilon3 = \varepsilon

Go from

f(x)

f(c)

by way of

f_n(x)

and

f_n(c)

: three pieces, each below

\frac\varepsilon3

. The two outer pieces are the uniform estimate, used at the two points

x

and

c

with the same

n

. The middle piece is the continuity of

f_n

.The uniformity matters: the same

n

works at both

x

and

c

. With only pointwise convergence the

n

needed at

x

could be different from the one needed at

c

, and the argument fails.

Therefore

f

is continuous, so

f \in C[a, b]

c

was arbitrary, so

f

is continuous at every point of

[a, b]

Hence

f_n \to f

d_\infty

, and the Cauchy sequence converges in

C[a, b]

\blacksquare

The theorem above that convergence in the sup metric is uniform convergence: uniform convergence of continuous functions is convergence in

d_\infty

In the picture: the graphs $f_n$ and $f_m$ for large $n, m$ lie in a tube around each other; at each $x$ the values $f_n(x)$ pile up at a number, which we call $f(x)$ ; and the tube around $f$ then contains $f_n$ for large $n$ . The tube of the visualizer above is that tube.

Proof workshopRebuild the proof that C[a, b] is complete

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

Let $(f_n)$ be Cauchy in $d_\infty$ . For each fixed $x$ , $(f_n(x))$ is a Cauchy sequence of real numbers.
So $f_n(x)$ converges. Define $f(x) = \lim f_n(x)$ .
Given $\varepsilon$ , choose $N$ with $d_\infty(f_n, f_m) < \varepsilon/2$ for $m, n > N$ .
For every $x$ and $n > N$ : $\lvert f_n(x) - f(x) \rvert \le \varepsilon/2$ .
So $f_n \to f$ uniformly on $[a, b]$ .
Fix $c$ and $\varepsilon$ . Pick $n$ with $|f_n - f| < \varepsilon/3$ everywhere, then $\delta$ with $|f_n(x) - f_n(c)| < \varepsilon/3$ for $|x - c| < \delta$ . Then $|f(x) - f(c)| < \varepsilon$ .
So $f$ is continuous at every $c$ .
Hence $f \in C[a, b]$ and $d_\infty(f_n, f) \to 0$ .

Theorem B standard

Closed subsets of complete spaces are complete

Let $X$ be a complete metric space and $A \subseteq X$ , with the distance of $X$ . Then $A$ is complete if and only if $A$ is closed in $X$ .

In one lineInside a complete space, a subset with the same distance is complete if and only if it is closed.

Why it is trueA Cauchy sequence in the subset has a limit in the big space; being closed keeps that limit in the subset. Conversely, a subset that is complete already contains the limit of any sequence of its points that converges in the big space.

Proofstandard

The idea: (⇐) A Cauchy sequence in A is Cauchy in X, so it converges to some x in X, and closedness puts x in A. (⇒) A convergent sequence of points of A is Cauchy, so it has a limit inside A, and limits are unique.

(

\Leftarrow

) Let

A

be closed and

(a_n)

a Cauchy sequence in

A

. It is Cauchy in

X

The distance is the same, so the Cauchy condition does not change.

a_n \to x

for some

x \in X

X

is complete.

Since

A

is closed,

x \in A

. So

A

is complete.

The theorem above on closed sets and limits of sequences, part (b).

(

\Rightarrow

) Let

A

be complete and

a_n \in A

with

a_n \to x \in X

. Then

(a_n)

is Cauchy.

Convergent sequences are Cauchy.

a_n \to a \in A

, and

a = x

. Hence

x \in A

, and

A

is closed by the same theorem.

\blacksquare

A

is complete, so

a_n \to a

for some

a \in A

. Limits are unique in

X

Worked example

Show that the set

\Delta

of probability vectors in

\mathbb R^n

(entries

\ge 0

adding to

1

) is complete.

Solution.

$\mathbb R^n$ is complete. With the 1-distance, say. The theorem above, which holds for each of the three distances.
$\Delta$ is closed. Let $x^{(k)} \in \Delta$ with $x^{(k)} \to x$ . By the coordinatewise theorem, each $x^{(k)}_i \to x_i$ . Each $x^{(k)}_i \ge 0$ , so $x_i \ge 0$ (limits preserve non-strict inequalities). And $\sum_i x^{(k)}_i = 1$ , so $\sum_i x_i = 1$ by the sum law of 1.2. Closed means limits of sequences in the set stay in the set. Inequalities with " $\ge$ " and equations survive limits.
Apply the closed-subset theorem. $\Delta$ is closed in a complete space, hence complete. This is the space on which PageRank is iterated, as we see below.

Answer. $\Delta$ is complete. The same argument shows any set defined by non-strict inequalities and equations on coordinates is complete. $\blacksquare$

Quick checkIn the proof that

C[a, b]

is complete, what does the sup metric give us that makes the limit function continuous?

Definitions and theorems: contractions

Definition B

Contraction

A map $T : X \to X$ from a metric space to itself is a contraction if there is a number $q$ with $0 \le q < 1$ such that

d(Tx, Ty) \le q\,d(x, y) \qquad \text{for all } x, y \in X.

The number $q$ is a contraction constant. It must be the same for all pairs, and it must be less than $1$ .

In one lineA map $T : X \to X$ that brings every pair of points closer together by a fixed factor $q < 1$ : $d(Tx, Ty) \le q\,d(x, y)$ .

Why it existsIt is the map whose repeated application squeezes the whole space, which is what makes iteration converge.

Definition B

Fixed point

A fixed point of $T : X \to X$ is a point $x^* \in X$ with $T x^* = x^*$ . In the cobweb picture it is a point where the curve $y = T(x)$ crosses the line $y = x$ .

In one lineA point $x^*$ that $T$ leaves where it is: $T x^* = x^*$ .

Why it existsSolving an equation $x = T(x)$ is the same as finding a fixed point of $T$ . Many equations can be put in that form.

Worked example

Which of these are contractions of

\mathbb R

T_1(x) = \frac x3 + 5

T_2(x) = 2x

T_3(x) = \sin x

T_4(x) = \frac{\lvert x \rvert}{2}

Solution. For each map, compute $\lvert Tx - Ty \rvert$ in terms of $\lvert x - y \rvert$ .

$T_1$ . $\lvert T_1x - T_1y \rvert = \frac13\lvert x - y \rvert$ . The constant $5$ cancels. So $T_1$ is a contraction with $q = \frac13$ . The fixed point solves $x = \frac x3 + 5$ , giving $x^* = 7.5$ .
$T_2$ . $\lvert T_2x - T_2y \rvert = 2\lvert x - y \rvert$ . The factor is $2$ , which is not below $1$ : it expands. Not a contraction.
$T_3$ . For $x$ and $y$ close to $0$ , $\sin x - \sin y \approx x - y$ , so the ratio $\frac{\lvert \sin x - \sin y \rvert}{\lvert x - y \rvert}$ gets arbitrarily close to $1$ . No $q < 1$ works for all pairs. The mean value theorem gives ratio $\lvert \cos c \rvert$ for some $c$ between $x$ and $y$ , whose supremum over $c$ is $1$ . So $T_3$ shrinks distances but not by a uniform factor, so it is not a contraction on $\mathbb R$ .
$T_4$ . By the reverse triangle inequality (the worked example in 4.1, with $z = 0$ ), $\lvert \lvert x \rvert - \lvert y \rvert \rvert \le \lvert x - y \rvert$ , so $\lvert T_4x - T_4y \rvert \le \frac12\lvert x - y \rvert$ . Absolute value does not expand distances, and the factor $\frac12$ does the rest. So $q = \frac12$ , and the fixed point is $0$ .

Answer. $T_1$ and $T_4$ are contractions; $T_2$ and $T_3$ are not. $\blacksquare$

When a map is differentiable, a bound on the slope settles it. This is the mean value theorem of 1.4 at work.

Theorem B standard (mean value theorem)

Derivative test for a contraction

Let $I$ be an interval, $g : I \to \mathbb R$ differentiable with $\lvert g'(x) \rvert \le q$ for all $x \in I$ , where $q < 1$ . Then $\lvert g(x) - g(y) \rvert \le q\,\lvert x - y \rvert$ for all $x, y \in I$ . If also $g(I) \subseteq I$ and $I$ is closed, $g$ is a contraction of the complete space $I$ .

In one lineIf $g$ is differentiable on an interval $I$ and $\lvert g'(x) \rvert \le q < 1$ for every $x \in I$ , then $\lvert g(x) - g(y) \rvert \le q\lvert x - y \rvert$ for all $x, y \in I$ .

Why it is trueBetween two points the mean value theorem says the average slope equals the derivative somewhere in between, and that derivative has size at most $q$ .

Proofstandard

The idea: The mean value theorem turns the difference g(x) − g(y) into g'(c)(x − y), and |g'(c)| ≤ q.

Let

x \ne y

I

. There is

c

between

x

and

y

with

g(x) - g(y) = g'(c)\,(x - y)

Nothing to prove for

x = y

. Otherwise the mean value theorem (1.4) applies on the interval between them, inside

I

, where

g

is differentiable.

\lvert g(x) - g(y) \rvert = \lvert g'(c) \rvert\,\lvert x - y \rvert \le q\,\lvert x - y \rvert

\blacksquare

c \in I

, where

\lvert g' \rvert \le q

(A closed interval $I$ is a closed subset of the complete space $\mathbb R$ , so it is complete by the closed-subset theorem. This is why the derivative test comes with ” $g(I) \subseteq I$ and $I$ closed”.)

Quick checkIs

T(x) = x + \dfrac1x

[1, \infty)

a contraction? (It satisfies

\lvert Tx - Ty \rvert < \lvert x - y \rvert

whenever

x \ne y

The Banach fixed point theorem

Theorem B Banach 1922; Rudin ch. 9

Banach fixed point theorem

Let $(X, d)$ be a non-empty complete metric space and $T : X \to X$ a contraction with constant $q$ , $0 \le q < 1$ . Then:

(a) $T$ has exactly one fixed point $x^*$ .

(b) For every $x_0 \in X$ , the sequence $x_{n+1} = T x_n$ converges to $x^*$ .

(d) A posteriori bound: $d(x_n, x^*) \le \dfrac{q}{1 - q}\,d(x_n, x_{n-1})$ for every $n \ge 1$ .

In one lineA contraction $T$ of a non-empty complete metric space has exactly one fixed point $x^*$ ; from any start $x_0$ the iterates $x_{n+1} = T x_n$ converge to $x^*$ , with $d(x_n, x^*) \le \dfrac{q^n}{1 - q}\,d(x_1, x_0)$ .

Why it is trueThe steps $d(x_{n+1}, x_n)$ shrink by the factor $q$ each time, so the total distance still to travel is a geometric series. That makes the sequence Cauchy; completeness gives the limit; continuity of $T$ makes it fixed; and two fixed points would be pulled together, which is impossible.

ProofRudin ch. 9; Banach 1922

The idea: Step 1: each step is at most q times the previous, so steps shrink geometrically. Step 2: add the steps from n on with the triangle inequality; the geometric sum is finite and small, so the sequence is Cauchy. Step 3: completeness gives a limit. Step 4: the limit is fixed. Step 5: uniqueness by pulling two fixed points together. Steps 6 and 7: let m go to infinity in the Step 2 bound.

Let

x_0 \in X

and

x_{n+1} = T x_n

. Then

d(x_{n+1}, x_n) = d(T x_n, T x_{n-1}) \le q\,d(x_n, x_{n-1})

Pick any starting point and define the iterates. Apply the contraction inequality with

x = x_n

and

y = x_{n-1}

.Where the idea comes from: it is the contractive sequence of 1.2's stretch problem, now in any metric space.

d(x_{n+1}, x_n) \le q^n\,d(x_1, x_0)

for all

n \ge 0

Induction on

n

: the case

n = 0

is an equality, and each step multiplies the bound by

q

For

m > n

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

For

m > n

, the triangle inequality (M3) applied repeatedly along

x_n, x_{n+1}, \dots, x_m

: the distance is at most the total length of the journey in small steps.The detour through intermediate points is where the triangle inequality is used to the full.

d(x_m, x_n) \le \dfrac{q^n}{1 - q}\,d(x_1, x_0)

for all

m > n

The finite geometric sum is below the infinite one:

\sum_{k \ge n} q^k = \frac{q^n}{1 - q}

(1.6).

The right side tends to

0

n \to \infty

, so

(x_n)

is Cauchy.

q^n \to 0

because

0 \le q < 1

(1.6, geometric sequence). Given

\varepsilon

, choose

N

with

\frac{q^N}{1 - q}\,d(x_1, x_0) < \varepsilon

; then every

m > n > N

has

d(x_m, x_n) < \varepsilon

x_n \to x^*

for some

x^* \in X

. This proves (b).

X

is complete: this is the only place the hypothesis is used.No formula for x* is needed. Completeness is what promises that x* is there.

Now

d(T x^*, x^*) \le d(T x^*, x_{n+1}) + d(x_{n+1}, x^*) \le q\,d(x^*, x_n) + d(x_{n+1}, x^*)

The contraction inequality with

x = x^*

and

y = x_n

gives

d(T x^*, x_{n+1}) \le q\,d(x^*, x_n)

, because

x_{n+1} = T x_n

. This is the proof that a contraction is continuous: if

x_n \to x^*

then

T x_n \to T x^*

, since

d(T x_n, T x^*) \le q\,d(x_n, x^*)

.Having a limit is not yet having a fixed point. We must still show that T does not move the limit, and this is the place where T being continuous is used.

d(T x^*, x^*) = 0

, that is,

T x^* = x^*

. This shows a fixed point exists.

Both terms on the right tend to

0

because

x_n \to x^*

. A non-negative number below every

\varepsilon

0

, and (M1).

Subtract:

(1 - q)\,d(x, y) \le 0

. Since

1 - q > 0

and

d \ge 0

d(x, y) = 0

, so

x = y

. This proves (a).

Uniqueness. If

T x = x

and

T y = y

, then

d(x, y) = d(T x, T y) \le q\,d(x, y)

Hence

d(x^*, x_n) \le \dfrac{q^n}{1 - q}\,d(x_1, x_0)

. This proves (c).

For fixed

n

, let

m \to \infty

d(x_m, x_n) \le \frac{q^n}{1 - q}\,d(x_1, x_0)

. We have

x_m \to x^*

, and the reverse triangle inequality gives

\lvert d(x_m, x_n) - d(x^*, x_n) \rvert \le d(x_m, x^*) \to 0

, so

d(x_m, x_n) \to d(x^*, x_n)

Then

d(x_n, x^*) \le \dfrac{q}{1 - q}\,d(x_n, x_{n-1})

. This proves (d).

\blacksquare

Apply (c) to the iteration that starts at

x_{n-1}

: its first step is

x_n

, its zeroth is

x_{n-1}

, and its limit is the same

x^*

by uniqueness. Take the exponent

1

in (c).

In the picture: the red and green staircase has steps that shrink by the factor $q$ at each round. A path with geometrically shrinking steps has finite total length, so it cannot wander forever. It settles at a point, and that point must lie on the diagonal ( $Tx = x$ ) because the last step before settling has length $0$ .

Proof workshopRebuild the proof of the Banach fixed point theorem

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Why· Where each hypothesis was used, and what fails without it

Completeness (step “so $x_n \to x^*$ ”). Without it there can be no fixed point. $T(x) = \frac x2$ on $X = (0, 1]$ is a contraction with $q = \frac12$ , and the iterates $\frac12, \frac14, \frac18, \dots$ bunch at $0$ , a hole. $T$ has no fixed point in $X$ .
$q < 1$ , uniformly. For $T(x) = x + \frac1x$ on $[1, \infty)$ distances shrink but the factor tends to $1$ ; there is no fixed point although $[1, \infty)$ is complete.
$T$ maps $X$ into $X$ . $T(x) = \frac x2 + 1$ is a contraction of $\mathbb R$ with fixed point $2$ , but it sends $[0, 1]$ out of $[0, 1]$ (it sends $1$ to $1.5$ ). Restricted to $[0, 1]$ the iteration leaves the space, and there is no fixed point in $[0, 1]$ .
Non-empty. The theorem says “there is exactly one”, which needs a point to start from.

Why· The two error bounds are for different jobs

The a priori bound (c) tells you before you start how many steps you need. Given $q$ and the first step $d(x_1, x_0)$ , you can solve $\frac{q^n}{1 - q}d(x_1, x_0) < \text{tolerance}$ for $n$ . The a posteriori bound (d) says that once you have computed two consecutive iterates, the remaining error is at most $\frac{q}{1 - q}$ times their gap. That is a safe stopping rule: for $q = \frac12$ , stop when two successive guesses differ by less than the tolerance, because then the error is at most the gap. For $q$ near $1$ the factor $\frac{q}{1-q}$ is large, and a small gap does not guarantee a small error. The bounds are usually pessimistic, because $q$ is a worst case over all pairs of points.

Quick checkIn the Banach fixed point theorem, which step is the ONLY one that uses completeness of

X

Quick checkA map has a fixed point

x^*

and

T

has slope

-1.5

there (as in the last preset of the cobweb). What happens to iterates started near

x^*

Examples: solving equations by iteration

Worked example

Solve

\cos x = x

by iteration, with a guaranteed error bound.

Solution.

Put the equation in the form $x = g(x)$ . $g(x) = \cos x$ . A solution of $\cos x = x$ is exactly a fixed point of $g$ .
Choose a complete space that $g$ maps into itself. $X = [0, 1]$ . On $[0, 1]$ , $\cos$ is decreasing, so $g([0, 1]) = [\cos 1, 1] = [0.5403, 1] \subseteq [0, 1]$ . $[0, 1]$ is a closed subset of $\mathbb R$ , hence complete. And $g$ must map $X$ into $X$ , or the iteration could leave the space.
Bound the slope. $g'(x) = -\sin x$ , and on $[0, 1]$ , $\sin$ is increasing, so $\lvert g'(x) \rvert \le \sin 1 \approx 0.8415 =: q < 1$ . The derivative test (mean value theorem) turns this into $\lvert g(x) - g(y) \rvert \le q\lvert x - y \rvert$ .
Apply Banach. There is exactly one solution of $\cos x = x$ in $[0, 1]$ , and the iterates converge to it from any start in $[0, 1]$ . There are no other solutions anywhere: if $\cos x = x$ then $x = \cos x \in [-1, 1]$ and $\cos x > 0$ there, so $x \in (0, 1]$ .
Compute. Start at $x_0 = 1$ : $x_1 = \cos 1 = 0.5403$ , $x_2 = 0.8576$ , $x_3 = 0.6543$ , and so on. Here $d(x_1, x_0) = 0.4597$ . One step to find the number the a priori bound needs.
Number of steps. The bound is $\dfrac{q^n}{1 - q}\,d(x_1, x_0) = 2.90\,(0.8415)^n$ . For error below $10^{-6}$ we need $n \ge 87$ . $0.8415^{87} \times 2.90 \approx 8.7 \times 10^{-7}$ .
Compare with reality. The error is already below $10^{-6}$ at $n = 32$ . The bound used the worst slope on all of $[0, 1]$ , namely $\sin 1 = 0.84$ . Near the solution the slope is $\sin(0.739) = 0.674$ , so the true rate is $0.674$ per step. The bound is a guarantee, not an estimate.

Answer. The unique solution is $x^* \approx 0.7390851$ (the “Dottie number”); $87$ steps are guaranteed to give six correct decimals, and $32$ suffice in practice. $\blacksquare$

Your answerStarting at

x_0 = 1

and iterating

x_{n+1} = \cos x_n

(in radians), what is

x_2

? (Three decimals.)

Your answerFor

\cos x = x

with

q = \sin 1 \approx 0.8415

and

d(x_1, x_0) \approx 0.4597

, find the smallest

n

with

\frac{q^n}{1 - q}d(x_1, x_0) \le 10^{-6}

Python labFixed-point iteration for cos x = x: the guarantee against the truth

import math

g = math.cos            # the map: we solve cos(x) = x
x0 = 1.0                # starting guess
q = math.sin(1)         # contraction constant of cos on [0, 1]: max |sin x| = sin 1

# find the fixed point to machine accuracy
xs = [x0]
for _ in range(200):
    xs.append(g(xs[-1]))
xstar = xs[-1]

d10 = abs(xs[1] - xs[0])
print("fixed point x* =", xstar)
print(" n   x_n        true error   a priori bound")
for n in [1, 2, 3, 5, 10, 20, 32, 40]:
    err = abs(xs[n] - xstar)
    bound = q**n / (1 - q) * d10
    print(f"{n:2d}  {xs[n]:.7f}  {err:.2e}    {bound:.2e}")

tol = 1e-6
n_guaranteed = math.ceil(math.log(tol * (1 - q) / d10) / math.log(q))
n_actual = next(n for n in range(len(xs)) if abs(xs[n] - xstar) < tol)
print("steps guaranteed by the bound:", n_guaranteed, " steps actually needed:", n_actual)

Try this. The bound is above the true error in every row, as the theorem promises. Now solve $x = e^{-x}$ instead: change the map to g = lambda x: math.exp(-x), the start to x0 = 0.5, and the constant to q = math.exp(-0.4) (valid on $[0.4, 0.7]$ ), and delete the rows with n above 20. You should see 32 steps guaranteed and 20 actually needed. Which map has the larger gap between guarantee and truth, and why? (The constant $q$ is the worst slope on the whole interval; the true rate is the slope at the fixed point.)

Newton’s method is a contraction near a root

Newton’s method for $f(x) = 0$ iterates $N(x) = x - \dfrac{f(x)}{f'(x)}$ . A root $r$ is a fixed point of $N$ . Why does it converge so fast?

Theorem B standard

Newton's method is a local contraction

Let $f$ be twice continuously differentiable near $r$ with $f(r) = 0$ and $f'(r) \ne 0$ . Then there is $\delta > 0$ such that $N(x) = x - f(x)/f'(x)$ maps $I = [r - \delta, r + \delta]$ into $I$ and satisfies $\lvert N(x) - N(y) \rvert \le \frac12\lvert x - y \rvert$ on $I$ . Hence for every $x_0 \in I$ , the Newton iterates converge to $r$ , and $r$ is the only root in $I$ .

In one lineIf $f$ has a continuous second derivative, $f(r) = 0$ and $f'(r) \ne 0$ , then for some $\delta > 0$ Newton's map $N$ is a contraction of $[r - \delta, r + \delta]$ with constant $\frac12$ , so Newton's method converges to $r$ from every start in that interval.

Why it is true $N'(x) = f(x)f''(x)/f'(x)^2$ , which is $0$ at the root. A derivative that is $0$ at $r$ and continuous is small on a small interval around $r$ .

Proofstandard

The idea: Differentiate N, see that N'(r) = 0, use continuity to keep |N'| ≤ 1/2 on a small interval, and check N maps the interval into itself.

N'(x) = 1 - \dfrac{f'(x)^2 - f(x)f''(x)}{f'(x)^2} = \dfrac{f(x)\,f''(x)}{f'(x)^2}

Quotient rule on

f/f'

\left(\frac{f}{f'}\right)' = \frac{f'^2 - f f''}{f'^2}

. We need

f''

to exist for this, and

f' \ne 0

near

r

(by continuity of

f'

from

f'(r) \ne 0

N'(r) = 0

f(r) = 0

.This is the whole secret of Newton's method: the map is flat at the fixed point.

Choose

\delta > 0

with

f' \ne 0

and

\lvert N'(x) \rvert \le \frac12

for all

x \in I

N'

is continuous near

r

(since

f, f', f''

are continuous and

f' \ne 0

), and

N'(r) = 0

, so for small enough

\delta

we have

\lvert N'(x) \rvert \le \frac12

I

. Continuity of

N'

r

with value

0

means: for the tolerance

\frac12

there is a

\delta

that works.

Then

\lvert N(x) - N(y) \rvert \le \frac12\lvert x - y \rvert

I

The derivative test: mean value theorem.

N

maps

I

into

I

. As

I

is closed in

\mathbb R

, it is complete, so Banach applies.

\blacksquare

N(r) = r

because

f(r) = 0

, so

\lvert N(x) - r \rvert = \lvert N(x) - N(r) \rvert \le \frac12\lvert x - r \rvert \le \delta

for

x \in I

Worked example

Newton's method for

x^2 = 2

: find an interval where

N

is a contraction and bound the error.

Solution.

The map. $f(x) = x^2 - 2$ , $N(x) = x - \dfrac{x^2 - 2}{2x} = \dfrac{x}{2} + \dfrac1x$ . This is the Babylonian method of 1.2.
The slope. $N'(x) = \dfrac12 - \dfrac1{x^2}$ , which is $0$ at $x = \sqrt 2$ . The root is a fixed point where the slope vanishes.
Choose an interval. Take $I = [1.2, 1.6]$ . $N'$ is increasing, with $N'(1.2) = 0.5 - 0.694 = -0.194$ and $N'(1.6) = 0.5 - 0.391 = 0.109$ . So $\lvert N' \rvert \le 0.195$ on $I$ ; take $q = 0.2$ . An increasing function has its extreme values at the ends of the interval.
Check that $N$ maps $I$ into $I$ . $N$ is convex ( $N''(x) = 2/x^3 > 0$ ), so its largest value on $I$ is at an end: $N(1.2) = 1.4333$ , $N(1.6) = 1.425$ . And $N(x) \ge \sqrt 2 = 1.4142$ for all $x > 0$ (arithmetic-geometric mean). So $N(I) \subseteq [1.4142, 1.4333] \subseteq I$ . The map must send the space into itself.
Run it from $x_0 = 1.5$ . $x_1 = \frac{17}{12} = 1.416667$ , so $d(x_1, x_0) = 0.0833$ . The a priori bound gives $d(x_n, \sqrt 2) \le \dfrac{0.2^n}{0.8}(0.0833) = 0.104\,(0.2)^n$ . Apply Banach with $q = 0.2$ .
Compare with the true errors. $x_1 - \sqrt 2 = 2.5 \times 10^{-3}$ , $x_2 - \sqrt 2 = 2.1 \times 10^{-6}$ , $x_3 - \sqrt 2 = 1.6 \times 10^{-12}$ . The bound allows $0.0208,\ 0.0042,\ 0.0008$ . The bound is true but loose. The true error is roughly squared at each step, which is faster than any fixed factor $q$ : a map whose slope is $0$ at the fixed point has a better contraction constant on every smaller interval.

Answer. On $[1.2, 1.6]$ , $N$ is a contraction with $q = 0.2$ ; the iterates converge to $\sqrt 2$ from any start there. $\blacksquare$

Your answerNewton's method for

x^2 = 2

N(x) = \frac x2 + \frac1x

. Starting at

x_0 = 1.5

, what is

x_1

? (Give a fraction.)

Worked example

Solve the linear system

x = Ax + b

by iteration, with

A = \begin{bmatrix} 0.5 & 0.2 \\ 0.1 & 0.3 \end{bmatrix}

and

b = (1, 2)

Solution. We use the max-distance on $\mathbb R^2$ , the complete space of 4.1.

Write the map. $T(x) = Ax + b$ . A solution of the system is a fixed point of $T$ . The system $(I - A)x = b$ is the same equation as $x = Ax + b$ .
Compute the contraction constant. $T(x) - T(y) = A(x - y)$ . For any vector $z$ , $\lVert Az \rVert_\infty = \max_i \lvert \sum_j A_{ij}z_j \rvert \le \max_i \sum_j \lvert A_{ij} \rvert\,\lVert z \rVert_\infty$ . The row sums of $\lvert A \rvert$ are $0.7$ and $0.4$ , so $\lVert Az \rVert_\infty \le 0.7\,\lVert z \rVert_\infty$ . Each entry of $z$ has size at most $\lVert z \rVert_\infty$ , and the largest row sum is the worst case. This is the operator norm of 3.5 for the max-distance.
Apply Banach. $T$ is a contraction of the complete space $(\mathbb R^2, d_\infty)$ with $q = 0.7$ . There is exactly one solution and the iteration converges from any start. $\mathbb R^2$ is complete, by the theorem above.
Iterate from $x_0 = (0, 0)$ . $x_1 = (1, 2)$ , $x_2 = (1.9, 2.7)$ , $x_3 = (2.49, 3.0)$ , $x_4 = (2.845, 3.149)$ . Each step is one matrix-vector product plus $b$ .
Compare with the exact solution. Solving $(I - A)x = b$ by elimination gives $x^* = (\frac{10}3, \frac{10}3)$ . The errors in max-distance are $3.33,\ 2.33,\ 1.43,\ 0.84,\ 0.49$ , shrinking by about $0.58$ to $0.7$ per step. The a priori bound $\frac{0.7^n}{0.3}(2)$ gives $4.67,\ 3.27,\ 2.29,\ 1.60$ for $n = 1, 2, 3, 4$ . Every error is below its bound, as the theorem promises.

Answer. $x^* = (10/3, 10/3)$ . The method needs only matrix-vector products, which is why iterative solvers for huge sparse systems use it. $\blacksquare$

Worked example

Picard iteration for

y' = y

y(0) = 1

: the contraction on a space of functions.

Solution. We solve the differential equation by finding a fixed point of an operator that acts on functions.

Turn the equation into an integral equation. $y' = y$ with $y(0) = 1$ holds exactly when $y(t) = 1 + \int_0^t y(s)\,ds$ . The fundamental theorem of calculus (1.5) in both directions.
Define the operator. On the space $X = C[0, a]$ with the sup metric, let $(Ty)(t) = 1 + \int_0^t y(s)\,ds$ . A fixed point $Ty = y$ is a solution. $T$ sends continuous functions to continuous functions (an integral is continuous in its upper limit). The “points” of the space are now functions, and $T$ is a map from the space to itself.
Show it is a contraction. For $y, z \in X$ and $t \in [0, a]$ : $\lvert (Ty)(t) - (Tz)(t) \rvert = \left\lvert \int_0^t (y - z)\,ds \right\rvert \le \int_0^t \lvert y(s) - z(s) \rvert\,ds \le t\,d_\infty(y, z) \le a\,d_\infty(y, z)$ . Taking the maximum over $t$ , $d_\infty(Ty, Tz) \le a\,d_\infty(y, z)$ . The integral of a function bounded by $d_\infty(y, z)$ over an interval of length $t$ is at most $t\,d_\infty(y, z)$ . So $q = a$ , which is below $1$ for $a < 1$ .
Apply Banach with $a = \frac12$ . $C[0, \frac12]$ is complete, so there is exactly one solution on $[0, \frac12]$ , found by iterating from any starting function. Completeness of $C[a, b]$ is the theorem of this chapter.
Run the iteration from $y_0 = 1$ . $y_1 = 1 + t$ , $y_2 = 1 + t + \frac{t^2}{2}$ , $y_3 = 1 + t + \frac{t^2}2 + \frac{t^3}{6}$ , in general $y_n = \sum_{k=0}^n \frac{t^k}{k!}$ . Each application of $T$ integrates the previous polynomial and adds $1$ .
Recognise the limit. $y_n \to e^t$ uniformly on $[0, \frac12]$ : the partial sums of the exponential series of 1.6. The theorem promised convergence in the sup metric; here we see it concretely.
Error bound. $d_\infty(y_1, y_0) = \max_{[0, 1/2]} t = \frac12$ , so $d_\infty(y_n, e^t) \le \frac{(1/2)^n}{1/2} \cdot \frac12 = 2^{-n}$ . For $n = 3$ the bound is $0.125$ , and the true error is $e^{0.5} - \frac{79}{48} \approx 0.0029$ . Again a guarantee that is far from tight. The factor $a$ is the worst case over the interval.

Answer. The unique solution on $[0, \frac12]$ is $y = e^t$ . Restarting the argument at $t = \frac12$ with the new initial value $e^{1/2}$ extends it to $[0, 1]$ , and so on, so it exists for all $t \ge 0$ . $\blacksquare$

Your answerIn Picard iteration for

y' = y

y(0) = 1

, the third iterate is

y_3(t) = 1 + t + \frac{t^2}{2} + \frac{t^3}{6}

. What is

y_3(\frac12)

? (Give a fraction.)

A preview· Preview: chapter 7.1, the existence and uniqueness theorem for ODEs

The example above had $f(t, y) = y$ . For a general equation $y' = f(t, y)$ with $y(0) = y_0$ , the operator is $(Ty)(t) = y_0 + \int_0^t f(s, y(s))\,ds$ on $C[0, a]$ . If $f$ satisfies a Lipschitz condition $\lvert f(t, y) - f(t, z) \rvert \le L\,\lvert y - z \rvert$ , the same estimate gives $d_\infty(Ty, Tz) \le L\,a\,d_\infty(y, z)$ . So $T$ is a contraction when $a < \frac1L$ . This is the Picard–Lindelöf theorem of MATH 376, and chapter 7.1 is this page with $f$ in place of $y$ .

Where it is used

Used inside maths· Inside maths: existence theorems and the real numbers themselves

The contraction mapping theorem is how analysts prove that equations have solutions without finding them: the existence and uniqueness of solutions of ODEs (7.1), the inverse function theorem (Rudin’s ch. 9 proves it by contraction), and the implicit function theorem in Unit 5. Completeness also underlies the real numbers: $\mathbb R$ is what you get by adding to $\mathbb Q$ the limit of every Cauchy sequence, a construction due to Cantor and others around 1870. And it explains 1.6: a series converges when its partial sums are Cauchy, and on a closed interval inside its radius of convergence the partial sums of a power series are a Cauchy sequence in $C[a, b]$ , so the sum is a continuous function.

Used in the real world· PageRank is a contraction in the 1-norm

In 2.11 the Google matrix $G = dP + \frac{1-d}{n}\mathbf 1\mathbf 1^{\mathsf T}$ ranks web pages: the power method $x_{k+1} = Gx_k$ converges to the stationary vector $\pi$ . We can read this as a contraction. Take $X = \Delta$ , the set of probability vectors, which is complete (above), with the 1-distance $\lVert x - y \rVert_1$ . For $x, y \in \Delta$ , the difference $z = x - y$ has entries adding to $0$ , so $\mathbf 1^{\mathsf T}z = 0$ and the teleportation term vanishes:

Gx - Gy = dP(x - y) + \tfrac{1-d}{n}\mathbf 1\,(\mathbf 1^{\mathsf T}z) = dP z.

In 2.11 we proved that a stochastic matrix never increases the 1-norm: $\lVert Pz \rVert_1 \le \lVert z \rVert_1$ . Hence

\lVert Gx - Gy \rVert_1 \le d\,\lVert x - y \rVert_1 .

Also $G$ maps $\Delta$ into $\Delta$ : for a probability vector $x$ , $Gx = dPx + \frac{1-d}{n}\mathbf 1$ has non-negative entries that add to $d + (1 - d) = 1$ (the theorem “A stochastic matrix keeps probability vectors” of 2.11 gives that $Px$ adds to $1$ ). So $G$ is a contraction of $\Delta$ with constant $q = d = 0.85$ . Banach gives, at once and without the Perron–Frobenius theorem: a unique stationary distribution, convergence from every starting vector, and $\lVert x_k - \pi \rVert_1 \le d^k\,\lVert x_0 - \pi \rVert_1 \le 2d^k$ (two probability vectors are at 1-distance at most $2$ ). This recovers the bound of 2.11. To guarantee a 1-distance below $10^{-8}$ takes $k = 118$ steps, because $2 \times 0.85^{118} \approx 9.4 \times 10^{-9}$ . Page, Brin, Motwani and Winograd’s 1998 report says that for a web of 322 million links the iteration converged in about 52 steps (the figure quoted in 2.11), so the guarantee is cautious and the actual rate is set by the second eigenvalue.

Worked example 2.11; computed

Run the PageRank contraction on the four-page web of 2.11 with

d = 0.85

, from

x_0 = (1, 0, 0, 0)

Solution.

The matrix. Page 1 links to pages 2, 3, 4; page 2 to 3 and 4; page 3 to page 1; page 4 to pages 1 and 3. The columns of $P$ are $(0, \frac13, \frac13, \frac13)$ , $(0, 0, \frac12, \frac12)$ , $(1, 0, 0, 0)$ , $(\frac12, 0, \frac12, 0)$ , and $G = 0.85\,P + \frac{0.15}{4}\mathbf 1\mathbf 1^{\mathsf T}$ . This is the web of 2.11. Every entry of $G$ is at least $0.0375$ .
The fixed point. Solving $G\pi = \pi$ gives $\pi \approx (0.3682,\ 0.1418,\ 0.2880,\ 0.2021)$ . Page 1 ranks highest: two pages link to it, and one of them is page 3 which sends all its weight there.
Iterate and measure. The 1-distance to $\pi$ at steps $k = 0, 1, 2, 3, 4, 5, 6$ is $1.264,\ 0.661,\ 0.223,\ 0.085,\ 0.058,\ 0.028,\ 0.008$ . The guarantee $d^k \lVert x_0 - \pi \rVert_1$ is $1.264,\ 1.074,\ 0.913,\ 0.776,\ 0.660,\ 0.561,\ 0.477$ . The error is below the guarantee at every step, and much below it: the actual rate is about $0.46$ , the second-largest eigenvalue size of $G$ ( $0.85 \times 0.547$ , using the $|\lambda_2| \approx 0.547$ of 2.11).
Steps for $10^{-8}$ . The guarantee needs $k = 118$ ; this web reaches $10^{-8}$ at $k = 25$ . The contraction constant $d$ is a worst case over all webs. The real rate depends on the web’s own eigenvalues, as the power method theorem of 2.11 said.

Answer. $\pi \approx (0.368, 0.142, 0.288, 0.202)$ is the unique PageRank vector. Banach turns “does it converge, and how fast” into one line: $q = d$ . $\blacksquare$

Your answerBy the guarantee

2\,d^k

with

d = 0.85

, what is the smallest number of PageRank iterations

k

that ensures a 1-distance below

10^{-8}

to the PageRank vector?

Used in the real world· Reinforcement learning: value iteration converges because the Bellman operator is a $\gamma$-contraction

An agent in a world with states $s$ chooses actions $a$ , collects rewards $r(s, a)$ , and moves to a next state $s'$ with probability $P(s' \mid s, a)$ . A discount $\gamma \in [0, 1)$ makes later rewards worth less. The value $V(s)$ is the best total discounted reward from state $s$ . The Bellman operator maps a table of values $V \in \mathbb R^{\lvert S \rvert}$ to a new table:

(TV)(s) = \max_a \Big[ r(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\,V(s') \Big].

The optimal value $V^*$ is a fixed point of $T$ . Claim: $T$ is a contraction of $(\mathbb R^{\lvert S \rvert}, d_\infty)$ with $q = \gamma$ . Proof. Fix $s$ and $a$ and write $u_a$ and $w_a$ for the bracket evaluated at $V$ and at $W$ . Then $\lvert u_a - w_a \rvert = \gamma\,\big\lvert \sum_{s'} P(s' \mid s, a)(V(s') - W(s')) \big\rvert \le \gamma\,\lVert V - W \rVert_\infty$ , because the probabilities are non-negative and add to $1$ . Also $\lvert \max_a u_a - \max_a w_a \rvert \le \max_a \lvert u_a - w_a \rvert$ (if the larger maximum is $u_{a^*}$ , then $\max u - \max w \le u_{a^*} - w_{a^*}$ ). Hence $\lVert TV - TW \rVert_\infty \le \gamma\,\lVert V - W \rVert_\infty$ . $\blacksquare$ Since $\mathbb R^{\lvert S \rvert}$ with the max-distance is complete, Banach gives a unique $V^*$ , value iteration $V_{k+1} = TV_k$ converges to it from any start, and $\lVert V_k - V^* \rVert_\infty \le \gamma^k \lVert V_0 - V^* \rVert_\infty$ . Richard Bellman developed dynamic programming in the 1950s (his book Dynamic Programming appeared in 1957); this is the standard proof that its main algorithm works, found in any reinforcement-learning text (Sutton and Barto’s, for example).

Worked example

Value iteration on a two-state world with

\gamma = 0.9

Solution. States $A$ and $B$ , two actions each. In $A$ : stay gives reward $1$ and keeps you in $A$ ; go gives reward $0$ and moves you to $B$ . In $B$ : stay gives reward $2$ ; go gives reward $0$ and moves you to $A$ . All moves are certain (so $P$ is $0$ or $1$ ).

The Bellman operator. $(TV)(A) = \max(1 + 0.9\,V(A),\ 0 + 0.9\,V(B))$ and $(TV)(B) = \max(2 + 0.9\,V(B),\ 0 + 0.9\,V(A))$ . The maximum is over the two actions available in each state.
Contraction. $q = \gamma = 0.9$ in the max-distance on $\mathbb R^2$ . By the claim above. So one fixed point, reached from any start.
Iterate from $V_0 = (0, 0)$ . $V_1 = (1, 2)$ . $V_2 = (\max(1.9, 1.8),\ \max(3.8, 0.9)) = (1.9, 3.8)$ . $V_3 = (\max(2.71, 3.42),\ \max(5.42, 1.71)) = (3.42, 5.42)$ . At step 3 the best move from $A$ switches from “stay” to “go”: it is better to walk to the richer state $B$ .
Find the fixed point by hand. In $B$ staying forever is best: $V^*(B) = \dfrac{2}{1 - 0.9} = 20$ . In $A$ , going to $B$ gives $0.9 \times 20 = 18$ , which beats staying ( $1 + 0.9 \times 18 = 17.2$ ), so $V^*(A) = 18$ . Check: $T(18, 20) = (\max(17.2, 18),\ \max(20, 16.2)) = (18, 20)$ .
The errors. $\lVert V_k - V^* \rVert_\infty = 20,\ 18,\ 16.2,\ 14.58$ for $k = 0, 1, 2, 3$ , which is exactly $20 \times 0.9^k$ . The bound $\gamma^k\lVert V_0 - V^* \rVert_\infty$ is attained here: the worst-case rate $\gamma$ really happens.
Steps to accuracy $0.01$ . $20 \times 0.9^k < 0.01$ needs $k \ge 73$ . $20 \times 0.9^{73} = 0.0091$ , while $0.9^{72} \times 20 = 0.0102$ .

Answer. $V^* = (18, 20)$ , and value iteration reaches error below $0.01$ after $73$ steps. With $\gamma$ close to $1$ (an agent that cares about the far future) the contraction constant is near $1$ and convergence is slow. $\blacksquare$

Your answerIn the two-state world, value iteration from

V_0 = (0, 0)

gives

V_1 = (1, 2)

. What is

V_2(A) = \max(1 + 0.9\,V_1(A),\ 0.9\,V_1(B))

Traps

Watch out· Distances shrinking is not the same as contracting

A map with $d(Tx, Ty) < d(x, y)$ for all $x \ne y$ need not be a contraction and need not have a fixed point ( $x + \frac1x$ on $[1, \infty)$ ). The constant $q < 1$ must be the same for all pairs. Also $\sin x$ shrinks distances on $\mathbb R$ but has $q = 1$ in the supremum.

Watch out· The map must send the space into itself

For cosine, $[0, 1]$ works because $\cos[0, 1] \subseteq [0, 1]$ . On $[0, 2]$ it would not: $\cos 2 < 0$ . Always check $T(X) \subseteq X$ and that $X$ is complete (closed, for a subset of $\mathbb R^n$ ) before using the theorem. Forgetting the first check is the most common error.

Watch out· Open intervals are not complete

$(0, 1)$ with the usual distance is not complete. A contraction of $(0, 1)$ into itself can fail to have a fixed point. The reason to work on a closed interval is not decoration. It is the hypothesis.

Watch out· A small step does not prove the iteration has converged

The a posteriori bound $\frac{q}{1 - q}d(x_n, x_{n-1})$ needs the contraction constant. For $q = 0.99$ the factor is $99$ : two successive guesses differing by $10^{-6}$ only guarantee an error of $10^{-4}$ . And without a contraction (like $\sqrt n$ in 1.2, whose neighbouring terms get arbitrarily close) a small step proves nothing at all.

Watch out· Slope below 1 at the fixed point is local; the theorem needs it on the whole space

For $T(x) = x^2$ the slope at the fixed point $0$ is $0$ , yet iterating from $x_0 = 2$ runs off to infinity. The contraction holds only on a small interval such as $[0, \frac13]$ . When the slope bound holds only near the fixed point, Banach applies to a small closed interval around it, and you must start inside.

Watch out· Completeness belongs to the metric, not only to the shape of the set

$\mathbb R$ with $d(x, y) = \lvert \arctan x - \arctan y \rvert$ is a metric space with the same notion of “nearby” as before, but it is not complete: the sequence $x_n = n$ is Cauchy and has no limit. Completeness is a property of the distance, which is why changing the norm on a function space (sup norm to 2-norm) can destroy it.

Problems

check

Which of these maps of $\mathbb R$ are contractions, and with what constant: (a) $T(x) = 0.4x - 3$ ; (b) $T(x) = x + 0.1$ ; (c) $T(x) = \frac12\cos x$ ; (d) $T(x) = -x$ ?

Solution

(a) Yes, $q = 0.4$ . (b) No: $T$ preserves distances ( $q = 1$ ) and has no fixed point. (c) Yes: $\lvert T'(x) \rvert = \frac12\lvert \sin x \rvert \le \frac12$ , so $q = \frac12$ by the derivative test. (d) No: $\lvert Tx - Ty \rvert = \lvert x - y \rvert$ , so $q = 1$ . (It has the fixed point $0$ but is not a contraction: iterates bounce between $x$ and $-x$ .)

check

For $T(x) = \frac x3 + 5$ , find the fixed point, and starting at $x_0 = 0$ compare the true error $\lvert x_n - x^* \rvert$ with the a priori bound.

Solution

Fixed point: $x = \frac x3 + 5$ gives $x^* = 7.5$ . Iterates: $x_1 = 5$ , so $d(x_1, x_0) = 5$ and $q = \frac13$ . The bound is $\frac{(1/3)^n}{2/3}\cdot 5 = 7.5\,(1/3)^n$ . The true error: $T(x) - 7.5 = \frac13(x - 7.5)$ , so $\lvert x_n - 7.5 \rvert = 7.5\,(1/3)^n$ . The bound is exactly the true error: it cannot be improved, because here the slope is $\frac13$ everywhere.

check

What does a Cauchy sequence look like in the discrete metric? Is a sequence of bit strings under the Hamming distance, in which consecutive terms differ in at most one bit, always Cauchy?

Solution

In the discrete metric a Cauchy sequence is eventually constant (take $\varepsilon = \frac12$ ). In the Hamming distance the same holds, because the distance takes whole-number values: take $\varepsilon = 1$ to get eventually constant. A sequence that changes one bit at every step is not Cauchy, since $d_H(x_{n+1}, x_n) = 1 \not< 1$ for all $n$ .

check

Is $(0, 1)$ complete with the distance $\lvert x - y \rvert$ ? Give a Cauchy sequence that shows your answer, and say which point is missing.

Solution

No. The sequence $x_n = \frac1n$ is Cauchy in $(0, 1)$ (it converges in $\mathbb R$ ) but its limit $0$ is not in $(0, 1)$ . The missing point is $0$ . The same space with the extra endpoint, $[0, 1]$ , is complete.

use

Show that the iteration $x_{n+1} = e^{-x_n}$ converges to the unique solution of $x = e^{-x}$ from any starting point in $[0.4, 0.7]$ . Starting at $x_0 = 0.5$ , how many steps does the a priori bound guarantee for error below $10^{-6}$ ?

Solution

Let $g(x) = e^{-x}$ on $X = [0.4, 0.7]$ , a closed interval, hence complete. $g$ is decreasing, so $g(X) = [e^{-0.7}, e^{-0.4}] = [0.4966, 0.6703] \subseteq X$ . And $\lvert g'(x) \rvert = e^{-x} \le e^{-0.4} = 0.6703 =: q < 1$ . By the derivative test and Banach there is a unique fixed point (about $0.5671$ ) and convergence. With $x_0 = 0.5$ : $x_1 = e^{-0.5} = 0.6065$ , $d(x_1, x_0) = 0.1065$ . The bound $\frac{0.6703^n}{0.3297}(0.1065) \le 10^{-6}$ needs $n \ge 32$ . (In practice $20$ steps suffice.)

use

Show that $x_{n+1} = 1 + \dfrac{1}{x_n}$ converges to the golden ratio $\frac{1 + \sqrt5}{2}$ from any start in $[1.5, 2]$ , and give the contraction constant.

Solution

Let $g(x) = 1 + \frac1x$ on $X = [1.5, 2]$ . $g$ is decreasing, with $g(1.5) = \frac53 \approx 1.667$ and $g(2) = 1.5$ , so $g(X) = [1.5, 1.667] \subseteq X$ . $\lvert g'(x) \rvert = \frac1{x^2} \le \frac1{2.25} = \frac49 =: q$ on $X$ . Banach gives a unique fixed point in $X$ . A fixed point satisfies $x = 1 + \frac1x$ , i.e. $x^2 - x - 1 = 0$ , whose positive root is $\frac{1 + \sqrt5}{2} \approx 1.618$ . The iterates from $1.5$ are $1.667,\ 1.6,\ 1.625,\ 1.615,\ \dots$ (ratios of consecutive Fibonacci numbers).

use

For $A = \begin{bmatrix} 0.2 & 0.3 \\ 0.1 & 0.4 \end{bmatrix}$ and $b = (1, 2)$ , show that $x \mapsto Ax + b$ is a contraction in the max-distance, find $q$ , and compute $x_1, x_2, x_3$ from $x_0 = (0, 0)$ . The exact solution is $(\frac83, \frac{34}9)$ .

Solution

Row sums of the entries’ absolute values: $0.5$ and $0.5$ , so $\lVert Az \rVert_\infty \le 0.5\,\lVert z \rVert_\infty$ and $q = 0.5$ . Iterates: $x_1 = (1, 2)$ , $x_2 = (0.2 + 0.6 + 1,\ 0.1 + 0.8 + 2) = (1.8, 2.9)$ , $x_3 = (0.36 + 0.87 + 1,\ 0.18 + 1.16 + 2) = (2.23, 3.34)$ . The exact solution is $(2.667, 3.778)$ , and the max-error at $x_3$ is $0.438$ , which is below the a priori bound $\frac{0.5^3}{0.5}(2) = 0.5$ .

use

Show that $T(x) = x^2$ is a contraction of $[0, \frac13]$ , find $q$ , and say what the theorem predicts for the iteration from $x_0 = \frac13$ .

Solution

$T$ maps $[0, \frac13]$ into $[0, \frac19] \subseteq [0, \frac13]$ . $\lvert T'(x) \rvert = 2x \le \frac23 =: q$ . By Banach there is a unique fixed point in $[0, \frac13]$ ; it is $0$ (the other solution of $x^2 = x$ is $1$ , outside the interval). From $x_0 = \frac13$ : $x_1 = \frac19$ , $d(x_1, x_0) = \frac29$ , so $d(x_n, 0) \le \frac{(2/3)^n}{1/3}\cdot\frac29 = \frac23\left(\frac23\right)^n$ . (The true error is $\left(\frac13\right)^{2^n}$ , much smaller: the slope is $0$ at the fixed point.)

prove

Prove that every Cauchy sequence in a metric space is bounded: there are a point $p$ and a number $M$ with $d(x_n, p) \le M$ for all $n$ .

Solution

Plan. After some index all terms are within $1$ of one term; the finitely many earlier terms are at finite distance.

Take $\varepsilon = 1$ : there is $N$ with $d(x_m, x_n) < 1$ for $m, n > N$ . Let $p = x_{N+1}$ . Then $d(x_n, p) < 1$ for all $n > N$ . Let $M = \max(1, d(x_1, p), \dots, d(x_N, p))$ , a maximum of finitely many numbers. Then $d(x_n, p) \le M$ for every $n$ . $\blacksquare$

prove

Prove that a Cauchy sequence in a metric space that has a convergent subsequence converges (to the same limit).

Solution

Plan. This is the last step of the Cauchy criterion proof in 1.2: split the distance through a late term of the subsequence.

Let $(x_n)$ be Cauchy and $x_{n_k} \to x$ . Let $\varepsilon > 0$ . Choose $N$ with $d(x_m, x_n) < \frac\varepsilon2$ for $m, n > N$ . Choose $k$ with $n_k > N$ and $d(x_{n_k}, x) < \frac\varepsilon2$ . For $n > N$ : $d(x_n, x) \le d(x_n, x_{n_k}) + d(x_{n_k}, x) < \varepsilon$ . So $x_n \to x$ . $\blacksquare$

prove

Prove the a posteriori bound: if $T$ is a contraction with constant $q$ on a complete space, then $d(x_n, x^*) \le \frac{q}{1 - q}\,d(x_n, x_{n-1})$ .

Solution

Plan. Compare $x_n$ with $x^*$ through $x_{n+1}$ and use the contraction on the pair $(x_n, x^*)$ .

$d(x_n, x^*) \le d(x_n, x_{n+1}) + d(x_{n+1}, x^*)$ . Now $x_{n+1} = T x_n$ and $x^* = T x^*$ , so $d(x_{n+1}, x^*) \le q\,d(x_n, x^*)$ . Also $d(x_n, x_{n+1}) \le q\,d(x_{n-1}, x_n)$ . Hence $d(x_n, x^*)(1 - q) \le q\,d(x_n, x_{n-1})$ , and dividing by $1 - q > 0$ gives the claim. $\blacksquare$

prove

Prove: if $A$ is an $n \times n$ matrix whose largest absolute row sum $\max_i \sum_j \lvert A_{ij} \rvert$ is $q < 1$ , then for every $b$ the equation $x = Ax + b$ has exactly one solution in $\mathbb R^n$ , and $x_{k+1} = Ax_k + b$ converges to it from any start.

Solution

Plan. Show $T x = Ax + b$ is a contraction of the complete space $(\mathbb R^n, d_\infty)$ , then apply Banach.

$\mathbb R^n$ with $d_\infty$ is complete (theorem above). For $x, y$ put $z = x - y$ . Then $Tx - Ty = Az$ , and for each $i$ , $\lvert (Az)_i \rvert = \left\lvert \sum_j A_{ij}z_j \right\rvert \le \sum_j \lvert A_{ij} \rvert\,\lvert z_j \rvert \le \left(\sum_j \lvert A_{ij} \rvert\right)\lVert z \rVert_\infty \le q\,\lVert z \rVert_\infty$ . Taking the maximum over $i$ , $d_\infty(Tx, Ty) \le q\,d_\infty(x, y)$ . The Banach fixed point theorem gives the unique solution and the convergence. $\blacksquare$ (Consequently $I - A$ is invertible.)

prove

Prove that a contraction on any metric space (complete or not) has at most one fixed point, and that it is continuous.

Solution

Plan. Uniqueness is the pull-together argument; continuity follows from the contraction inequality directly.

If $Tx = x$ and $Ty = y$ , then $d(x, y) = d(Tx, Ty) \le q\,d(x, y)$ , so $(1 - q)\,d(x, y) \le 0$ , so $d(x, y) = 0$ and $x = y$ . For continuity: given $\varepsilon > 0$ take $\delta = \varepsilon$ . If $d(x, y) < \delta$ , then $d(Tx, Ty) \le q\,d(x, y) \le d(x, y) < \varepsilon$ , because $q < 1$ . So $T$ is continuous (even uniformly). $\blacksquare$

stretch

Suppose $T : X \to X$ on a non-empty complete metric space is such that some power $S = T^m$ (apply $T$ $m$ times) is a contraction. Prove that $T$ has exactly one fixed point. (This is how Picard iteration works on all of $[0, \infty)$ at once: for the operator of the $y' = y$ example, repeating the integral estimate $m$ times gives $\lvert (T^my)(t) - (T^mz)(t) \rvert \le \frac{t^m}{m!}\,d_\infty(y, z)$ , so $T^m$ has constant $a^m/m!$ on $[0, a]$ , which is below $1$ for large $m$ however large $a$ is.)

Solution

Plan. Use Banach for $S$ , then show the fixed point of $S$ is also fixed by $T$ .

By Banach, $S$ has a unique fixed point $x^*$ . Then $S(Tx^*) = T(Sx^*) = T x^*$ (because $S = T^m$ commutes with $T$ ), so $Tx^*$ is also a fixed point of $S$ . By uniqueness, $Tx^* = x^*$ . Any fixed point of $T$ is a fixed point of $S$ , so it equals $x^*$ . $\blacksquare$

stretch

Show that $d(x, y) = \lvert \arctan x - \arctan y \rvert$ is a metric on $\mathbb R$ and that $(\mathbb R, d)$ is not complete, although $\mathbb R$ with $\lvert x - y \rvert$ is.

Solution

Plan. A metric pulled back through an injective function; then find a Cauchy sequence escaping to infinity.

(M1): $d \ge 0$ , and $d = 0$ iff $\arctan x = \arctan y$ iff $x = y$ (arctan is strictly increasing, so injective). (M2) is clear. (M3): $\lvert \arctan x - \arctan z \rvert \le \lvert \arctan x - \arctan y \rvert + \lvert \arctan y - \arctan z \rvert$ is the triangle inequality for real numbers. Now take $x_n = n$ . Since $\arctan n \to \frac\pi2$ , the real sequence $(\arctan n)$ is Cauchy, so $d(x_m, x_n) = \lvert \arctan m - \arctan n \rvert \to 0$ as $m, n \to \infty$ : the sequence is Cauchy. It has no limit: for any real $x$ , $d(x_n, x) = \lvert \arctan n - \arctan x \rvert \to \frac\pi2 - \arctan x > 0$ . So $(\mathbb R, d)$ is not complete. A Cauchy sequence escapes to a point at infinity that this metric does not contain.

Summary

$x_n \to x$ in a metric space means $d(x_n, x) \to 0$ . In $\mathbb R^n$ it is coordinatewise convergence; in $C[a, b]$ with the sup metric it is uniform convergence.
A set is closed iff it contains the limits of all convergent sequences of its points. A closed subset of a complete space is complete, and a complete subset is closed.
A space is complete when every Cauchy sequence converges in it. $\mathbb R$ , $\mathbb R^n$ and $C[a, b]$ with the sup metric are complete; $\mathbb Q$ and $(0, 1]$ are not. The $C[a, b]$ proof builds the limit pointwise, gets a uniform $N$ from the sup metric, and uses that a uniform limit of continuous functions is continuous.
A contraction shrinks every distance by one fixed factor $q < 1$ . The Banach fixed point theorem: on a non-empty complete space a contraction has exactly one fixed point, iteration from any start converges to it, and $d(x_n, x^*) \le \frac{q^n}{1 - q}d(x_1, x_0)$ .
Using it takes four checks: $T$ maps a complete set into itself, and $\lvert Tx - Ty \rvert \le q\lvert x - y \rvert$ for one $q < 1$ (for a differentiable $T$ , $\lvert T' \rvert \le q$ ). Then say what $q$ is and what the bound promises.
Applications: $\cos x = x$ ( $q = \sin 1$ ); Newton’s method (slope $0$ at the root, so $q$ can be made as small as you like near it); linear systems $x = Ax + b$ (row sums below $1$ ); Picard iteration for ODEs (the integral operator on $C[0, a]$ , preview of 7.1).
PageRank is a contraction of the probability vectors in the 1-norm with $q = d$ ; value iteration in reinforcement learning is a contraction in the max-norm with $q = \gamma$ .

4.2 Convergence, completeness and the contraction mapping theorem

The picture: the staircase that closes in

The idea, in words

Definitions and theorems: convergence

Convergent sequence in a metric space

Limits in a metric space are unique

Convergence in R^n is coordinatewise

Convergence in the sup metric is uniform convergence

Closed sets and limits of sequences

Definitions and theorems: Cauchy sequences and completeness

Cauchy sequence in a metric space

Convergent sequences are Cauchy

Complete metric space

R^n is complete

The space of continuous functions is complete

C[a, b] with the sup metric is complete

Closed subsets of complete spaces are complete

Definitions and theorems: contractions

Contraction

Fixed point

Derivative test for a contraction

The Banach fixed point theorem

Banach fixed point theorem

Examples: solving equations by iteration

Newton’s method is a contraction near a root

Newton's method is a local contraction

Where it is used

Traps

Problems

Summary

Where this sits

Comes from

Leads to

Same idea elsewhere