Completeness and Contraction

The real numbers were built in 2A.4 The Real Numbers to be complete: every Cauchy sequence converges. In 2A.6 Sequences that property turned out to be equivalent to the least upper bound property, and it powered every existence theorem of Book 2A. This chapter defines completeness for any metric space, sorts the spaces of 2B.1 Metric Spaces into complete and incomplete ones, and then proves the theorem that makes completeness pay off.

That theorem is the contraction mapping principle, also called Banach's fixed point theorem. If a map pulls every pair of points closer together by at least a fixed factor, and the space is complete, then the map has exactly one fixed point, and you can find it by iterating the map from any starting point. The proof is a page long. The theorem is the engine behind the existence of solutions of ordinary differential equations (2B.10 Ordinary Differential Equations), the inverse function theorem (2B.9 The Inverse and Implicit Function Theorems), the short-time existence of nonlinear heat equations (6A.7 Nonlinear Parabolic Equations) and, through them, of Ricci flow itself (11A.3 Short-Time Existence and Uniqueness). Tao proves it in his chapter on several-variable calculus; this guidebook moves it here, directly after completeness, because it is the first and most-used way that completeness produces solutions.

By the end of this chapter you will be able to:

• prove that a metric space is complete, or exhibit a Cauchy sequence that doesn't converge;
• prove that closed subsets of complete spaces are complete, and use this to manufacture complete spaces;
• state and prove the contraction mapping theorem, with its a-priori and a-posteriori error bounds;
• show that a given map is a contraction, usually through a derivative bound and the mean value theorem;
• handle the two variants needed later: eventually contracting maps, and fixed points that depend on a parameter.

2.1Cauchy sequences and complete spaces

The Cauchy condition refers only to the terms of the sequence, never to a limit. That is its whole point. It lets us recognise that a sequence ought to converge before we know what it converges to, and completeness then guarantees that the limit exists.

Two facts hold in every metric space, with the proofs of 2A.6 Sequences unchanged:

• every convergent sequence is Cauchy (if $x_n \to x$, then $d(x_m, x_n) \leq d(x_m, x) + d(x, x_n)$);
• a Cauchy sequence with a convergent subsequence converges, to the same limit.

2.1.1Which spaces are complete

• $\mathbb{R}$ is complete (2A.6 Sequences). $\mathbb{Q}$ is not: the decimal truncations of $\sqrt2$ are a Cauchy sequence of rationals with no rational limit.
• $\mathbb{R}^n$, with any of the three metrics of 2B.1 Metric Spaces, is complete. A sequence is Cauchy in $d_{\ell^\infty}$ exactly when each coordinate sequence is Cauchy in $\mathbb{R}$; each coordinate converges, and so the points converge. (Uniformly equivalent metrics have the same Cauchy sequences, so the choice of metric doesn't matter.)
• $(0, 1]$ with the usual metric is not complete: $\tfrac1n$ is Cauchy, and its only possible limit, $0$, is missing.
• Any set with the discrete metric is complete: a Cauchy sequence must eventually have $d(x_m, x_n) < 1$, so it is eventually constant.
• $C([a, b])$ with the sup metric is complete. This is the theorem that a uniform limit of continuous functions is continuous, proved in 2B.5 Uniform Convergence and Arzelà–Ascoli. We will use it in this chapter's forward look and prove it there.
• $C([0, 1])$ with the area metric $d_1$ is not complete (Exercise 2.8). Steeper and steeper ramps form a $d_1$-Cauchy sequence whose only candidate limit is a step function, which isn't continuous.

The missing point of $(0, 1]$ suggests a general principle: inside a complete space, the complete subsets are exactly the ones that are not missing any limit points.

Part 2 is how complete spaces are manufactured in practice. Every closed subset of $\mathbb{R}^n$ is complete: closed balls, spheres, closed squares. So is every closed subset of $C([a, b])$, for example the set of continuous functions with $|f| \leq 1$, or with $f(a) = 0$. Each of these appears below as the space on which a contraction acts.

2.2A map on the floor

The tabletop version is a good experiment: put a map of a room on the floor of that room. The fixed point exists whatever angle the map is laid at, and it moves when the map is moved.

2.3The contraction mapping theorem

Lipschitz maps are continuous: take $\delta = \varepsilon / q$. For differentiable functions on an interval, the mean value theorem (2A.10 Derivatives) turns a derivative bound into a Lipschitz constant: if $|f'| \leq q$ on an interval $I$, then $|f(x) - f(y)| = |f'(c)|\,|x - y| \leq q|x - y|$ for $x, y \in I$. That is how most contractions in practice are recognised.

The a-priori bound says, before computing anything, how many iterations guarantee a given accuracy. The a-posteriori bound uses the last step actually taken, which is usually much sharper, and it is the one used as a stopping rule: stop when the last step is less than $\frac{1-q}{q}$ times the accuracy wanted.

The error falls by a factor of at least $q$ per step. On a logarithmic scale that is a straight line of slope $\log q$, which is what "linear convergence" means (Figure 2.3).

2.3.1Every hypothesis is needed

• Completeness. $f(x) = x/2$ maps $(0, 1]$ into itself with $q = \tfrac12$, but its only candidate fixed point, $0$, is missing. The iterates $2^{-n}$ are Cauchy and have nowhere to converge.
• Mapping into the space. $f(x) = x/2 + 1$ is a contraction of $\mathbb{R}$ with fixed point $2$, but as a map from $[0, 1]$ it has no fixed point, because it doesn't map $[0, 1]$ into itself. Checking $f(X) \subseteq X$ is often the real work.
• A uniform constant $q < 1$. $f(x) = x + \frac1x$ on $[1, \infty)$ is complete and satisfies $|f(x) - f(y)| < |x - y|$ for $x \neq y$ (Exercise 2.10), but it has no fixed point, since $f(x) > x$ everywhere. A map that shrinks distances by a factor that creeps up towards $1$ is not enough.

2.3.2The Dottie number

2.3.3Newton's method for square roots, again

In 2A.4 The Real Numbers the Babylonian iteration $x \mapsto \frac x2 + \frac1x$ produced rationals converging to $\sqrt2$. The contraction theorem explains why, and gives a rate. On $X = [1, 2]$, the map $g(x) = \frac x2 + \frac1x$ has $g'(x) = \frac12 - \frac1{x^2} \in [-\tfrac12, \tfrac14]$, so $g$ is a contraction with $q = \tfrac12$. And $g$ maps $[1, 2]$ into itself: its minimum on $[1, 2]$ is $g(\sqrt2) = \sqrt2$ and its maximum is $g(1) = g(2) = \tfrac32$. So iteration converges to the unique fixed point, where $\frac x2 = \frac1x$, that is, $x = \sqrt2$.

The real behaviour is much better than $q = \tfrac12$ suggests. From $1$: $1.5$, $1.41667$, $1.4142157$, $1.41421356237469$, $1.414213562373095$, with the number of correct digits roughly doubling each step. The reason is that $g'(\sqrt2) = 0$: near the fixed point, the effective contraction constant tends to zero. This is quadratic convergence, the hallmark of Newton's method, which is this iteration in disguise (Exercise 2.12).

2.3.4PageRank

2.4Variants needed later

2.4.1Eventually contracting maps

Sometimes $f$ itself is not a contraction, but an iterate $f^k = f \circ \cdots \circ f$ is. This happens for the Picard iteration of ODEs on long time intervals (2B.10 Ordinary Differential Equations), where each application of the integral operator gains a factor $\frac{(LT)^k}{k!}$ rather than a fixed $q$.

2.4.2Fixed points that depend on a parameter

In the inverse function theorem (2B.9 The Inverse and Implicit Function Theorems) and for ODEs with varying initial data (2B.10 Ordinary Differential Equations), the contraction depends on a parameter, and we need its fixed point to depend continuously on the parameter. The proof is a single estimate.

The pattern of this proof, "the fixed point moves at most $\frac{1}{1-q}$ times as much as the map does", is used over and over. It is a stability statement: a contraction's fixed point is robust under perturbation of the map, with the perturbation amplified by at most $\frac1{1-q}$.

2.5History

The method is older than the theorem. Solving equations by successive approximation goes back to antiquity (the Babylonian square root), and in the 19th century Joseph Liouville and then Émile Picard used successive approximations to prove that differential equations have solutions; Picard's 1890 work made the method systematic. Stefan Banach isolated the abstract principle in his 1920 doctoral thesis, published in Fundamenta Mathematicae in 1922, where he stated it for complete normed spaces. The metric-space form above is the one now standard. It is unusual among existence theorems in being constructive: it doesn't merely assert that a solution exists, it computes one, with an error bound. Brouwer's fixed point theorem (every continuous map of a closed ball to itself has a fixed point, 7A.7 Smooth Topology) is far more general and far less informative: it guarantees a fixed point but gives no way to find it and no uniqueness.

2.6Exercises

Hint

For (b), suppose $d_1(f_n, f) \to 0$. Show that $\int_0^{1/2}|f| = 0$ and $\int_{1/2 + \delta}^1 |f - 1| = 0$ for every $\delta > 0$, and use continuity.

Solution

(a) For $m < n$, $f_m$ and $f_n$ agree outside $[\tfrac12, \tfrac12 + \tfrac1m]$, where they differ by at most $1$; the region between the graphs is a triangle of area $\tfrac12(\tfrac1m - \tfrac1n) \leq \frac1{2m}$. (b) $\int_0^{1/2}|f| = \int_0^{1/2}|f - f_n| \leq d_1(f_n, f) \to 0$, so $f = 0$ on $[0, \tfrac12]$ by continuity (a continuous non-negative function with zero integral vanishes, 2B.1 Metric Spaces). Likewise, for each $\delta > 0$ and $n > 1/\delta$, $\int_{1/2+\delta}^1|f - 1| \leq d_1(f_n, f) \to 0$, so $f = 1$ on $(\tfrac12, 1]$. Then $f$ is not continuous at $\tfrac12$. (c) No: $d_\infty(f_n, f_{2n}) = \tfrac12$.

Solution

(a) $d(x_n, x^*) \leq d(x_n, x_{n+1}) + q\,d(x_n, x^*)$, so $d(x_n, x^*) \leq \frac{1}{1-q}d(x_{n+1}, x_n) \leq \frac{q}{1-q}d(x_n, x_{n-1})$. (b) Need $q^n \cdot 0.4597/(1 - q) < 10^{-10}$, i.e. $n > \log(10^{-10}(1-q)/0.4597)/\log q \approx 139$, so $140$ iterations.

Solution

$f'(x) = 1 - 1/x^2 \in [0, 1)$ on $[1, \infty)$, so by the mean value theorem $|f(x) - f(y)| = f'(c)|x - y| < |x - y|$. There is no $q < 1$ that works, since $f'(x) \to 1$. No fixed point, since $f(x) - x = 1/x > 0$. On a compact space, $x \mapsto d(x, f(x))$ is continuous, so it has a minimum at some $x_0$. If $f(x_0) \neq x_0$, then $d(f(x_0), f(f(x_0))) < d(x_0, f(x_0))$, contradicting minimality. Uniqueness is as in the theorem.

Solution

$|\cos'(x)| = |\sin x| = 1$ at $x = \pi/2$, and by the mean value theorem no constant $q < 1$ works near there. For $\cos\circ\cos$: its derivative is $\sin(\cos x)\sin x$, and $|\sin(\cos x)| \leq \sin 1$ because $\cos x \in [-1, 1]$; so $|(\cos\circ\cos)'| \leq \sin 1 < 1$ on all of $\mathbb{R}$.

Solution

(a) Quotient rule. (b) $N'$ is continuous with $N'(r) = 0$, so $|N'| \leq \tfrac12$ on some $[r - \delta, r + \delta]$. There, $|N(x) - r| = |N(x) - N(r)| \leq \tfrac12|x - r| \leq \delta$, so the interval is mapped into itself, and $N$ is a contraction with $q = \tfrac12$. (c) $x - \frac{x^2 - 2}{2x} = \frac x2 + \frac1x$.

Solution

(a) $|\Phi(y)(t) - \Phi(z)(t)| \leq \int_0^t |y - z| \leq T\,d_\infty(y, z)$. (b) By induction: if $y_n = \sum_{k \leq n} t^k/k!$, then $1 + \int_0^t y_n = 1 + \sum_{k\leq n} t^{k+1}/(k+1)! = y_{n+1}$. (c) By induction, $|\Phi^k(y)(t) - \Phi^k(z)(t)| \leq \frac{t^k}{k!}d_\infty(y, z)$: integrating $\frac{s^{k}}{k!}$ from $0$ to $t$ gives $\frac{t^{k+1}}{(k+1)!}$. Since $\frac{T^k}{k!} \to 0$, some $\Phi^k$ is a contraction. The fixed point is the uniform limit of the Taylor polynomials, which is $e^t$ (2B.6 Power Series, Exponentials and Bump Functions).