THE INVERSE FUNCTION THEOREM FOR LIPSCHITZ MAPS

RALPH HOWARD DEPARTMENT OF MATHEMATICS UNIVERSITY OF SOUTH CAROLINA COLUMBIA, S.C. 29208, USA

                     HOWARD@MATH.SC.EDU

Abstract. This is an edited version of a proof, in the from of exercises with detailed hints, of the inverse function that was given to a graduate class in differential equations as homework. The goal of the assignment was not only to present the basics about inverse functions, but to recall/introduce the basics about differential calculus in Banach spaces and to give an example of a nontrivial application of the contraction mapping principle (which is also included as one of the problems) as these were among the basic tools used in the class. Thus the presentation starts more or less from the definition of the derivative of maps between Banach spaces and proves not only the standard version of the inverse function, but also the version for Lipschitz maps.

Contents

1. Introduction. 2 2. Derivatives of maps between Banach Spaces 2 2.1. Bounded linear maps between Banach spaces. 2 2.2. The derivative of maps between Banach spaces 5 3. The Inverse Function Theorem for Lipschitz Maps 9 4. The Inverse Function Theorem 11 5. Implict Function Theorem: Surjective From 14 5.1. Preliminary results on surjective linear maps. 14 .2. The surjective form of the implict function theorem for Lipschitz

maps. 16

A. Appendix: Contraction Mappings and the Banach Fixed Point

Theorem 16 A.1. Some Review 16 A.2. Metric spaces 17 A.3. The Banach Fixed Point Theorem 17

Date: March 1997.

1. Introduction.

There are many motivations for the inverse function theorem. Here is one. Consider a map f: R^{n} → R^{m} and a point y ∈ R^{m}. Then it is interesting to know when the equation f(x) = y can be solve for x. Of course in complete generality there is no reasonable solution to the problem. But assume f is smooth, or at least continuously differentiable, and that f(x_{0}) = y_{0}. Then it is reasonable to look for conditions on f so that for y sufficiently close to y_{0} that f(x) = y has a solution with x close to x_{0}. This is the problem the inverse function theorem answers. Let f′(x_{0}): R^{n} → R^{m} be the derivative (this is the linear map that best approximates f near x_{0} see §2.2 for the exact definition) and assume that f′(x_{0}): R^{n} → R^{m} is onto. Then the implicit function theorem gives us a open neighbor hood V so that for every y ∈ V the equation f(x) = y has a solution. More than that it allows us to choose a continuously differentiable function φ: V → R^{n} with φ(y_{0}) = x_{0} and such that f(φ(y)) = y that is not only can we solve the equation f(x) = y, we can do it in such a way that the solution x = φ(y) is a smooth function of y ∈ V. Showing that f(x) = y can be solved for x is a more or less typical application of the Banach Fixed Point Theorem (i.e contraction mapping principle which is included in an appendix), but is nontrivial enough to be quite interesting. Showing that the solution x = φ(y) depends smoothly on y requires more work.

Rather than just work with maps between the Euclidean spaces, we will work with maps between Banach spaces. The definitions and results we need on bounded linear maps and differentiable functions between are given in in the preliminary sections. The work is split into two steps. First a version of the theorem is given for Lipschitz maps (see §3) that are sufficiently close to a linear map. This version gives the existence of an inverse φ which is continuous. This is then used (in §4) to show that if the original map is continuously differentiable then so is the its local inverse φ. One advantage to splitting the proof up in this manner is that if makes it easy to give explicit bounds on the size of the neighborhood where the local inverse is defined.

2. Derivatives of maps between Banach Spaces

2.1. Bounded linear maps between Banach spaces. Recall that a Banach space is a normed vector space that is complete (i.e. Cauchy sequences converge) with respect to the metric by the norm. Let X and Y be Banach spaces with norms | · |_{X} and | · |_{Y}. Then a linear map A: X → Y is bounded iff there is a constant C so that

|Ax|_{Y} ≤ C|x|_{X} for all x ∈ X.

The best constant C in this inequality is the operator norm (which we will usually just call the norm) of A and denoted by ∥A∥. Thus ∥A∥ is given by

∥A∥ := sup_{0≠x∈X} \frac{|Ax|_{Y}}{|x|_{X}} .

Exercise 2.1. Show that a linear map L: X → Y is continuous if and only if it is bounded.

Denote by B(X, Y) the set of all bounded linear maps A: X → Y.

Exercise 2.2. 1. Show that the norm ∥ · ∥ makes B(X, Y) into a normed linear space. That is show if A, B ∈ B(X, Y) and c_{1} and c_{2} are real numbers then c_{1}A + c_{2}B ∈ B(X, Y) and

∥c_{1}A + c_{2}B∥ ≤ |c_{1}|∥A∥ + |c_{2}|∥B∥.

2. Show that the norm ∥ · ∥ is complete on B(X, Y) and so B(X, Y) is

a Banach space. Hint: This can be done as follows. Let {A_{k}}_{k=1}^{∞} be a Cauchy sequence in X. Then M := sup_{k} ∥A_{k}∥ < ∞. Show

(a) For any x ∈ X the sequence {A_{k}x}_{k=1}^{∞} is a Cauchy sequence and as Y is a Banach space this implies lim_{k→∞} A_{k}x exists.

(b) Define a map A: X → Y by Ax := lim_{k→∞} A_{k}x. Then show A is linear and |Ax|_{Y} ≤ M|x|_{X} for all x ∈ X. Thus A is bounded.

(c) Let ε > 0 and let N_{ε} be so that k, ℓ ≥ N_{ε} implies ∥A_{k} − A_{ℓ}∥ ≤ ε (N_{ε} exists as {A_{k}}_{k=1}^{∞} is Cauchy). Then for any x ∈ X and k ≥ N_{ε} and all ℓ ≥ N_{ε} we have

|Ax − A_{k}x|_{Y} ≤ |Ax − A_{ℓ}x|_{Y} + |(A_{ℓ} − A_{k})x|_{Y}

≤ |Ax − A_{ℓ}x|_{Y} + ε|x|_{X}

⟶^{ℓ→∞} 0 + ε|x|_{X} = ε|x|_{X}.

This implies ∥A − A_{k}∥ ≤ ε for k ≥ N_{ε} and thus lim_{k→∞} A_{k} = A. This shows any Cauchy sequence in B(X, Y) converges.

3. If Z is a third Banach space A ∈ B(X, Y) and B ∈ B(Y, Z)) then BA ∈ B(X, Z) and ∥BA∥ ≤ ∥B∥∥A∥. In particular if A ∈ B(X, X) then by induction ∥A^{k}∥ ≤ ∥A∥^{k}.

Remark 2.3. Some inequalities involving norms of linear maps will be used repeatedly in what follows without comment. The inequalities in question are

|Ax|_{Y} ≤ ∥A∥|x|_{X}, ∥BA∥ ≤ ∥B∥ ∥A∥, ∥A^{k}∥ ≤ ∥A∥^{k}.

Of course the various forms of the triangle inequality will also be used. The includes the form |u − v| ≥ |u| − |v|.

As first step in understanding when nonlinear maps have inverses we look at the set of invertible linear maps

The linear map A ∈ B(X, Y) is invertible iff there is a B ∈ B(Y, X) so that AB = I_{Y} and BA = I_{X} (where I_{X} is the identity map on X). The map B is called the inverse of A and is denoted by B = A^{−1}.

Proposition 2.4. Let X be a Banach space and A ∈ B(X, X) with ∥I_{X} − A∥ < 1. Then the A in invertible and the inverse is given by

A^{−1} = ∑_{k=0}^{∞}(I_{X} − A)^{k} = I_{X} + (I_{X} − A) + (I_{X} − A)^{2} + (I_{X} − A)^{3} + ⋯

and satisfies the bound

∥A^{−1}∥ ≤ \frac{1}{1 − ∥I_{X} − A∥}.

Moreover if 0 < ρ < 1 then

∥A − I_{X}∥, ∥B − I_{X}∥ ≤ ρ implies ∥A^{−1} − B^{−1}∥ ≤ \frac{1}{(1 − ρ)^{2}} ∥A − B∥

Proof. Let B := ∑_{k=0}^{∞}(I_{X} − A)^{k} then ∥(I_{X} − A)^{k}∥ ≤ ∥I_{X} − A∥^{k} and as ∥I_{X} − A∥ < 1 the geometric series ∑_{k=0}^{∞} ∥I_{X} − A∥^{k} converges. Therefore by comparison the series defining B converges and

∥B∥ ≤ ∑_{k=0}^{∞} ∥I_{X} − A∥^{k} = \frac{1}{1 − ∥I_{X} − A∥}.

Now compute

AB = ∑_{k=0}^{∞} A(I_{X} − A)^{k} = ∑_{k=0}^{∞}(I_{X} − (I_{X} − A))(I_{X} − A)^{k}

= ∑_{k=0}^{∞}(I_{X} − A)^{k} − ∑_{k=0}^{∞}(I_{X} − A)^{k+1} = I_{X}.

A similar calculation shows that BA = I_{X} (or just note A and B clearly commute). Thus B = A^{−1}. (The formula for B = A^{−1} was motivated by the power series (1 − x)^{−1} = ∑_{k=0}^{∞} x^{k}.)

If ∥A − I_{X}∥, ∥B − I_{X}∥ ≤ ρ then by what we have just done we have

∥A^{−1}∥, ∥B^{−1}∥ ≤ \frac{1}{1 − ρ}

Therefore

∥A^{−1} − B^{−1}∥ = ∥A^{−1}(B − A)B^{−1}∥ ≤ ∥A^{−1}∥ ∥B^{−1}∥ ∥B − A∥

≤ \frac{1}{(1 − ρ)^{2}} ∥A − B∥.

This completes the proof.

The next proposition is a somewhat more general version of the last result. It is not required for the proof of the inverse function and can be skipped. However as a good exercise in learning to do calculations with linear operators I recommend you try to prove it on your own.

Proposition 2.5. Let X and Y be Banach spaces and let A, B ∈ B(X, Y). Assume that A is invertible. Then if B satisfies

∥A − B∥ < \frac{1}{∥A^{−1}∥}

then B is also invertible and

∥B^{−1}∥ ≤ \frac{∥A^{−1}∥}{1 − ∥A^{−1}∥ ∥A − B∥}, ∥B^{−1} − A^{−1}∥ ≤ \frac{∥A^{−1}∥^{2}∥B − A∥}{1 − ∥A^{−1}∥ ∥A − B∥}.

Therefore the set of invertible maps from X to Y is open in B(X, Y) and the map A ↦ A^{−1} is continuous on this set.

Proof. This is more or less a corollary to the last result. Write B = A − (A − B) = A(I_{X} − A^{−1}(A − B)). But ∥A^{−1}(A − B)∥ ≤ ∥A^{−1}∥ ∥A − B∥ < 1 by assumption. Thus the last proposition gives that I_{X} − A^{−1}(A − B) is invertible and that

∥(I_{X} − A^{−1}(A − B))^{−1}∥ ≤ \frac{1}{1 − ∥A^{−1}(A − B)∥} ≤ \frac{1}{1 − ∥A^{−1}∥ ∥(A − B)∥}.

Whence B = A(I_{X} − A^{−1}(A − B)) is the product of invertible maps and whence invertible with B^{−1} = (I_{X} − A^{−1}(A − B))^{−1}A^{−1}. Thus

∥B^{−1}∥ ≤ ∥(I_{X} − A^{−1}(A − B))^{−1}∥ ∥A^{−1}∥ ≤ \frac{∥A^{−1}∥}{1 − ∥A^{−1}∥ ∥(A − B)∥}

which gives the required bound on ∥B^{−1}∥.

Now A^{−1} − B^{−1} = A^{−1}(B − A)B^{−1}. Therefore

∥A^{−1} − B^{−1}∥ ≤ ∥A^{−1}∥ ∥A − B∥ ∥B^{−1}∥ ≤ \frac{∥A^{−1}∥^{2}∥B − A∥}{1 − ∥A^{−1}∥ ∥A − B∥}.

This completes the proof.

2.2. The derivative of maps between Banach spaces. Let X and Y be Banach spaces, U ⊆ X be an open set and f: U → Y a function. Then f is differentiable at a ∈ U if and only if there is a linear map A ∈ B(X, Y) so that

f(x) − f(a) = A(x − a) + o(|x − a|_{X}).

More explicitly this means these is a function x ↦ ε(x; a) from a neighborhood of a in U so that

f(x) − f(a) = A(x − a) + |x − a|_{X}ε(x; a) where lim_{x→a} |ε(x, a)|_{Y} = 0.

When f is differentiable at a the linear map A is unique and called the derivative of f at a. It will be denoted by A = f′(a). Thus for us the derivative is a bounded linear map f′(a) ∈ B(X, Y) rather than a number.

Exercise 2.6. Show that f is differential at a with f′(a) = A if and only if

lim_{x→a} \frac{|f(x) − f(a) − A(x − a)|_{Y}}{|x − a|_{X}} = 0.

Exercise 2.7. If f is differentiable at a then f is continuous at a.

To get a feel for what this linear map measures let v ∈ X, assume that f: U → Y is differentiable at a and let c(t) := f(a + tv). Then for t ≠ 0

\frac{1}{t}(c(t) − c(0)) = \frac{1}{t}(f(a + tv) − f(a)) = \frac{1}{t}(f′(a)tv + |tv|_{X}ε(a + tv; a))
= f′(a)v + |v|_{X}ε(a + tv; a).

But lim_{t→0} ε(a + tv; a) = 0 so this implies that c has a tangent vector at t = 0 and that it is given by c′(0) = f′(a)v. That is f′(a)v is the “directional derivative” at a of f in the direction v. As a variants on this here are a couple of exercises.

Exercise 2.8. Let X and Y be Banach spaces and U ⊂ X open. Let c: (a, b) → U be a continuously differentiable map and let f: U → Y be a map that is differentiable at c(t_{0}). Then γ(t) := f(c(t)) is differentiable at t_{0} and

\frac{d}{dt}f(c(t))|_{t=t_{0}} = γ′(t_{0}) = f′(c(t_{0}))c′(t_{0}).

Exercise 2.9. Let X = R^{n} and Y = R^{m} and let f: R^{n} → R^{m} be a function which can be given in components as

f(x) = [ f^{1}(x) ; f^{2}(x) ; ⋮ ; f^{m}(x)] .

Let \frac{∂f}{∂x^{i}} be the partial derivative of f with respect to x^{i}. That is

\frac{∂f}{∂x^{i}} = [ \frac{∂f^{1}}{∂x^{i}} (x) ; \frac{∂f^{2}}{∂x^{i}} (x) ; ⋮ ; \frac{∂f^{m}}{∂x^{i}} (x)]

Assume that f is differentiable at x = a. Then show that the matrix A of f′(a) in the standard basis of R^{n} and R^{n} is the matrix with columns

\frac{∂f}{∂x^{1}} , \frac{∂f}{∂x^{2}} , …, \frac{∂f}{∂x^{n}}. That is

A = [\frac{∂f}{∂x^{1}} , \frac{∂f}{∂x^{2}} , …, \frac{∂f}{∂x^{m}} ] = [\begin{matrix}\frac{∂f^{1}}{∂x^{1}} & \frac{∂f^{1}}{∂x^{2}} & ⋯ & \frac{∂f^{1}}{∂x^{n}} \\ \frac{∂f^{2}}{∂x^{1}} & \frac{∂f^{2}}{∂x^{2}} & ⋯ & \frac{∂f^{2}}{∂x^{n}} \\ ⋮ & ⋮ & ... & ⋮ \\ \frac{∂f^{m}}{∂x^{1}} & \frac{∂f^{m}}{∂x^{2}} & ⋯ & \frac{∂f^{m}}{∂x^{n}} \end{matrix} ]

where these are all evaluated at x = a.

The following gives trivial examples of differentiable maps.

Proposition 2.10. Let A: X → Y be a bounded linear map between Banach spaces and y_{0} ∈ Y. Set f(x) = Ax + y_{0} then f is differentiable at all points a ∈ X and f′(a) = A for all a.

Proof. f(x) − f(a) = A(x − a) so the definition of differentiable is verified with ε(x, a) ≡ 0.

The following gives a less trivial example.

Proposition 2.11. Let X and Y be Banach spaces and let U ⊂ B(X, Y) be the set of invertible elements (this is an open set by Proposition 2.5). Define a map f: U → B(Y, X) by

f(X) = X^{−1}.

Then f is differentiable and for A ∈ U the derivative f′(A): B(X, Y) → B(Y, X) is the linear map whose value on V ∈ B(X, Y) is

f′(A)V = −A^{−1}V A^{−1}.

Proof. Let L: B(X, Y) → B(Y, X) be the linear map LV := −A^{−1}V A^{−1} Then for X ∈ U

f(X) − f(A) − L(X − A) = X^{−1} − A^{−1} + A^{−1}(X − A)A^{−1}
= X^{−1}(A − X)A^{−1} + A^{−1}(X − A)A^{−1}
= (−X^{−1} + A^{−1})(X − A)A^{−1}
= X^{−1}(X − A)A^{−1}(X − A)A^{−1},

so that

∥f(X) − f(A) − L((X − A)∥ ≤ ∥X^{−1}∥ ∥A^{−1}∥^{2}∥X − A∥^{2}.

The map X ↦ X^{−1} is continuous (Proposition 2.5) so lim_{X→A} X^{−1} = A^{−1}. Thus

lim_{X→A} \frac{∥f(X) − f(A) − L((X − A)∥}{∥X − A∥} ≤ lim_{X→A} ∥X^{−1}∥ ∥A^{−1}∥^{2}∥X − A∥ = 0.

The result now follows from Exercise 2.6.

Next we consider the chain rule.

Proposition 2.12. Let X, Y and Z be Banach spaces U ⊆ X, V ⊆ Y open sets f: U → Y and g: V → Z. Let a ∈ U so that f(a) ∈ V and assume that f is differentiable at a and g is differentiable at f(a). Then g ∘ f is differentiable at a and

(g ∘ f)′(a) = g′(f(a))f′(a)

Proof. From the definitions f(x)−f(a) = f′(a)(x−a)+|x−a|_{X}ε_{1}(x; a) and g(y) − g(f(a)) = g′(f(a)) + |y − f(a)|_{Y}ε_{2}(x; f(a)) where lim_{x→a} ε_{1}(x; a) = 0 and lim_{y→f(a)} ε_{2}(y; f(a)) = 0. Then

g(f(x)) − g(f(a)) = g′(f(a))(f(x) − f(a)) + |f(x) − f(a)|_{Y}ε_{2}(f(x), f(a))
= g′(f(a))f′(a)(x − a) + g′(f(a))|x − a|_{X}ε_{1}(x, a)

+ |f′(a)(x − a) + |x − a|_{X}ε_{1}(x, a)|_{X}ε_{2}(f(x), f(a))

= g′(f(a))f′(a)(x − a) + |x − a|_{X} (g′(f(a))ε_{1}(x, a)

+ |f′(a)\frac{x − a}{|x − a|_{X}} + ε_{1}(x, a)|_{X} ε_{2}(f(x); f(a)))

= g′(f(a))f′(a)(x − a) + |x − a|_{X}ε_{3}(x; a),

where this defines ε_{3}(x, a). Then

|ε_{3}(x, a)|_{X} ≤ ∥g′(f(a))∥|ε_{1}(x, a)|_{Y} + (∥f′(a)∥ + |ε_{1}(x; a)|_{Y})|ε_{2}(f(x), f(a))|_{Z}.

This (and the continuity of f at a) implies lim_{x→a} ε_{3}(x, a) = 0 which completes the proof.

Let X and Y be Banach spaces, U ⊂ X open and f: U → Y. Then f is continuously differentiable on U iff f is differentiable at each point x ∈ U and the map x ↦ f′(x) is a continuous map from U to B(X, Y). Or what is the same thing, f′(x) exists for all x ∈ U and for a ∈ U we have lim_{x→a} ∥f′(x) − f′(a)∥ = 0.

If c: [a, b] → U is a continuously differentiable curve and f: U → Y is a continuously differentiable map, then γ(t) := f(c(t)) is a continuously differential curve γ: [a, b] → Y and by the chain rule (or Exercise(2.8))

γ′(t) = f′(c(t))c′(t).

Using the fundamental theorem of calculus this gives

γ(b) = γ(a) = ∫_{a}^{b} γ′(t) dt = ∫_{a}^{b} f′(c(t))c′(t) dt

But

|γ′(t)|_{Y} = |f′(c(t))c′(t)|_{Y} ≤ ∥f′(c(t))∥|c′(t)|_{X}.

These can be combined to give

|γ(b) − γ(a)|_{Y} = |∫_{a}^{b} f′(c(t))c′(t) dt|_{Y} ≤ ∫_{a}^{b} ∥f′(c(t))∥|c′(t)|_{X} dt. (2.1)

Proposition 2.13. Let X and Y be Banach spaces and let U ⊂ X be open and convex. Assume that f: U → Y is continuously differentiable and that ∥f′(x)∥ ≤ C for all x ∈ U. Then

|f(x_{1}) − f(x_{0})|_{Y} ≤ C|x_{1} − x_{0}|_{X}

for all x_{1}, x_{0} ∈ U

Proof. Let c: [0, 1] → U be given by c(t) = (1 − t)x_{0} + tx_{1} = x_{0} + t((x_{1} − x_{0}) (this curves lies in U as x_{0}, x_{1} ∈ U and U is convex). Then c′(t) = (x_{1} −x_{0}). Let γ(t) := f(c(t)). Then γ′(t) = f′(c(t))c′(t) = f′(c(t))(x_{1} − x_{0}). Putting this into (2.1) implies

|f(x_{1}) − f(x_{0})|_{Y} = |γ(1) − γ(0)|_{Y} ≤ ∫_{0}^{1} ∥f′(c(t))∥|x_{1} − x_{0}|_{X} dt
≤ ∫_{0}^{1} C|x_{1} − x_{0}|_{X} dt = C|x_{1} − x_{0}|_{X}.

This completes the proof.

3. The Inverse Function Theorem for Lipschitz Maps

The results of this section are a little more general than is usually needed in applications, but the proof of the more general results is actually easier in that it abstracts the inequality ((3.1) below) that is central to most proofs of the inverse function. A map f: X → Y between metric spaces (see the appendix for basics about metric spaces) in an open map iff f[U] is an open subset of Y for all open sets U ⊆ X. A map between f metric spaces is a Lipschitz map iff there is a constant M so that d(f(x_{2}), f(x_{1})) ≤ Md(x_{2}, x_{1}) It is a Lipeomorphism^{1} iff it is a Lipschitz map that has a Lipschitz inverse. We use the usual notation for open and closed balls, that is for x_{0} ∈ X and r > 0 then the open an closed balls of radius r about x_{0} are

B(x_{0}, r) := \{x ∈ X : |x − x_{0}|_{X} < r\}, \overline{B}(x_{0}, r) := \{x ∈ X : |x − x_{0}|_{X} ≤ r\}.

Theorem 3.1. Let X and Y be Banach spaces and let \overline{B}(x_{0}, r_{0}) be a closed ball in X. Let f: \overline{B}(x_{0}, r_{0}) → Y so that for some invertible linear map L: X → Y and some ρ < 1

|L^{−1}f(x_{2}) − L^{−1}f(x_{1}) − (x_{2} − x_{1})|_{X} ≤ ρ|x_{2} − x_{1}|_{X} (3.1)

holds for all x_{2}, x_{1} ∈ \overline{B}(x_{0}, r_{0}). Then for all x_{2}, x_{1} ∈ \overline{B}(x_{0}, r_{0})

\frac{(1 − ρ)}{∥L^{−1}∥}|x_{2} − x_{1}|_{X} ≤ |f(x_{2}) − f(x_{1})|_{Y} ≤ ∥L∥(1 + ρ)|x_{2} − x_{1}|_{X}. (3.2)

This f is injective on \overline{B}(x_{0}, r_{0}). Also the restriction f|_{B(x_{0},r_{0})} : B(x_{0}, r_{0}) → Y of f to the open ball B(x_{0}, r_{0}) is an open map so that V := f[B(x_{0}, r_{0})] is an open set in Y. Thus f|_{B(x_{0},r_{0})} : B(x_{0}, r_{0}) → V is a Lipeomorphism and V contains the open ball B(f(x_{0}), r_{1}) where

1“Lipeomorphism” gets my vote for the ugliest sounding term in mathematics.

r_{1} := βρ, with β := \frac{(1 − ρ)}{∥L^{−1}∥}. (3.3)

Finally if x_{1} ∈ B(x_{0}, r_{0}) there is the inclusion

B(f(x_{1}), β(r_{0} − |x_{1} − x_{0}|_{X})) ⊆ V (3.4)

(so that for all y ∈ B(f(x_{1}), β(r_{0} − |x|_{X})) the equation f(x) = y will have a solution in B(x_{1}, r_{0} − |x_{1}|_{X}).

Remark 3.2. Most proofs of the inverse function theorem show the existence of solutions to f(x) = y for y close to f(x_{0}) by using the Banach fixed point theorem to show that for some linear L the map Φ_{y}(x) = x − L^{−1}(f(x) − y) has a fixed point (which is then easily see to be also be a solution to f(x) = y). (Usually L = f′(x_{0}).) The condition (3.1) is just that Φ_{y} is a contraction and as such is a natural condition to assume.

Proof. For x_{1}, x_{2} ∈ \overline{B}(x_{0}, r_{0}) we can use (3.1) and estimate

|f(x_{2}) − f(x_{1})|_{Y} ≤ ∥L∥∥L^{−1}f(x_{2}) − L^{−1}f(x_{1})|_{X}

≤ ∥L∥(L^{−1}f(x_{2}) − L^{−1}f(x_{1}) − (x_{2} − x_{1})|_{X} + |x_{2} − x_{1}|_{X})

≤ ∥L∥(ρ|x_{2} − x_{1}|_{X} + |x_{2} − x_{1}|_{X})
= ∥L∥(1 + ρ)|x_{2} − x_{1}|_{X}

which proves the upper bound of (3.2). To prove the lower bound again use (3.1)

|x_{2} − x_{1}|_{X} ≤ |L^{−1}f(x_{2}) − L^{−1}f(x_{1}) − (x_{2} − x_{1})|_{X}
+ |L^{−1}f(x_{2}) − L^{−1}f(x_{1})|_{X}
≤ ρ|x_{2} − x_{1}|_{X} + ∥L^{−1}∥|f(x_{2}) − f(x_{1})|_{Y}.

This implies

\frac{1 − ρ}{∥L^{−1}∥}|x_{2} − x_{1}|_{X} ≤ |f(x_{2}) − f(x_{1})|_{Y}

which completes the proof of (3.2).

For y ∈ Y define Φ_{y}: \overline{B}(x_{0}, r_{0}) → X by

Φ_{y}(x) := x − L^{−1}(f(x) − y).

Then

(3.5) Φ_{y}(x) = x if and only if f(x) = y.

The condition (3.1) implies that for x_{1}, x_{2} ∈ \overline{B}(x_{0}, r_{0})

|φ_{y}(x_{2}) − Φ_{y}(x_{1})|_{X} = |L^{−1}f(x_{2}) − L^{−1}f(x_{1}) − (x_{2} − x_{1})|_{X} ≤ ρ|x_{2} − x_{1}|_{X}.

Therefore Φ_{y} is a contraction. If β and r_{1} are defined by (3.3) for x ∈ \overline{B}(x_{0}, r_{0}) and y ∈ \overline{B}(f(x_{0}), r_{1}) then |x − x_{0}|_{X} ≤ r_{0} and |y − f(x_{0})|_{Y} ≤ r_{1} = βr_{0} = \frac{(1−ρ)}{∥L^{−1}∥}r_{0}. Thus for x ∈ \overline{B}(x_{0}, r_{0}) and y ∈ \overline{B}(f(x_{0}), r_{1})

|x_{0} − Φ_{y}(x)|_{X} = |x_{0} − x − L^{−1}(f(x) − y)|_{X}

≤ |x_{0} − x − L^{−1}(f(x) − f(x_{0}))|_{X} + |L^{−1}(y − f(x_{0}))∥

≤ ρ|x − x_{0}|_{X} + ∥L^{−1}∥|y − f(x_{0})|_{Y}

≤ ρr_{0} + ∥L^{−1}∥\frac{(1 − ρ)}{∥L^{−1}∥}r_{0}

= r_{0}

Therefore if y ∈ \overline{B}(f(x_{0}), r_{1}) then Φ_{y}: \overline{B}(x_{0}, r_{0}) → \overline{B}(x_{0}, r_{0}). As Φ_{y} is a contraction the Banach fixed point theorem (Theorem A.5 in the appendix) Φ_{y} will have a unique fixed point in \overline{B}(x_{0}, r_{0}). By the equivalence (3.5) this implies that for y ∈ \overline{B}(f(x_{0}), r_{1}) there is a unique x ∈ \overline{B}(x_{0}, r_{0}) with f(x) = y. This shows \overline{B}(f(x_{0}), r_{1}) ⊂ f[\overline{B}(x_{0}, r_{0})]. But if |f(x) − f(x_{0})| < r_{1} then (using the definition of β and (3.2) we have β|x−x_{0}|_{X} ≤ |f(x)−f(x_{0})|_{Y} < r_{1} so that |x − x_{0}|_{X} < r_{1}/β = r_{0}. Thus shows that if y ∈ B(f(x_{0}), r_{1}), x ∈ \overline{B}(x_{0}, r_{0}), and f(x) = y then x ∈ B(x_{0}, r_{0}). Therefore f[B(x_{0}, r_{0})] ⊆ B(f(x_{0}), r_{1}).

Now for any x_{0} ∈ B(x_{0}, r_{0}) we can let x̃_{0} := x_{1} and r̃_{0} := r_{0} − |x_{1} − x_{0}|_{X} (so that \overline{B}(x̃_{0}, r̃_{0}) ⊂ \overline{B}(x_{0}, r_{0})). Then the argument we have just given (with x_{0} replaced by x̃_{0}, r_{0} replaced by r̃_{0} and f by f|_{\overline{B}(x̃_{0},r̃_{0})}) shows that

B(f(f(x_{1}), β(r_{0} − |x_{1} − x_{0}|_{X})) ⊆ f[B(x_{1}, r_{0} − |x_{1} − x_{0}|_{X})] ⊆ V

where V = f[B(x_{0}, r_{0})] as above. This proves (3.4). If y ∈ V then there is an x ∈ B(x_{0}, r_{0}) with f(x) = y. But then B(y, β(r_{0} − |x_{1} − x_{0}|_{X})) ⊂ V. Therefore V contains an open ball about any of its points and so V is open.

As f|_{B(x_{0},r_{0})} is injective it has an inverse φ := f|_{B(x_{0},r_{0})} : B(x_{0}, r_{0}). By (3.2) this will satisfy

\frac{1}{∥L∥(1 + ρ)}|y_{2} − y_{1}|_{Y} ≤ |φ(y_{2}) − φ(y_{1})|_{X} ≤ \frac{∥L^{−1}∥}{(1 − ρ)}|y_{2} − y_{1}|_{Y}.

Exercise 3.3. Prove these inequalities from the inequalities (3.2).

Thus both f|_{B(x_{0},r_{0})} and its inverse φ are Lipschitz and so f|_{B(x_{0},r_{0})} is a Lipeomorphism as claimed.

Finally to show that f|_{B(x_{0},r_{0})} is an open map note that in U ⊆ B(x_{0}, r_{0}) then f[U] = φ^{−1}[U] and as φ is continuous this implies f[U] is open.

4. The Inverse Function Theorem

Let X, Y be Banach spaces U ⊂ X, V ⊂ Y be open sets. Then a map f: U → V is a diffeomorphism if and only if f is continuously differentiable and there is a continuously differentiable map φ: V → U so that φ ∘ f = Id_{U} and f ∘ φ = Id_{V}. This implies that φ is the inverse of f (that is φ = f^{−1}). In particular this means that f: U → V bijective. Thus a diffeomorphism is just a continuously differentiable bijection between open sets so that the inverse is also continuously differentiable.

Remark 4.1. A continuously differentiable function f which is injective need not be a diffeomorphism. As an example let f: R → R be f(t) = t^{3}. This is smooth and bijective, but the inverse f^{−1}(s) = \sqrt[3]{s} is not differentiable at the origin.

Theorem 4.2 (Inverse Function Theorem). Let X and Y be Banach spaces, U ⊂ X be open and f: U → X be continuously differentiable. Let x_{0} ∈ U be a point where the linear map f′(x_{0}): X → Y is invertible. Then there is an r_{0} > 0 so that if V := f[B(x_{0}, r_{0})] is the image of the open ball of radius r_{0} about x_{0} then V is an open set in Y and f|_{B(x_{0},r_{0})} : B(x_{0}, r_{0}) → V is a diffeomorphism.

Remark 4.3. Sometimes it is useful to have explicit estimates for the size of r_{0} and the neighborhood V. We state one version of such estimates. (Most of the work in getting this bounds was done in Theorem 3.1.) By hypothesis x ↦ f′(x) is a continuous map and by Proposition 2.5 the map x ↦ f′(x)^{−1} is continuous. Thus x ↦ (f′(x_{0})^{−1}f′(x) − I_{X}) is continuous in a neighborhood of x_{0} and this map vanishes at x = x_{0}. Now fix ρ with 0 < ρ < 1, then by continuity there is an r_{0} > 0 so that \overline{B}(x_{0}, r_{0}) ⊆ U and

(4.1) x ∈ \overline{B}(x_{0}, r_{0}) implies ∥f′(x_{0})^{−1}f′(x) − I_{X}∥ ≤ ρ.

This r_{0} will work in the theorem so that if f|_{B(x_{0},r_{0})} : B(x_{0}, r_{0}) → V is a diffeomorphism with V := f[B(x_{0}, r_{0})]. Let

β := \frac{(1 − ρ)}{∥f′(x_{0})^{−1}∥}. (4.2)

Then we have the lower bound

B(f(x_{0}), βr_{0}) ⊆ V

for the size of V. More generally if x_{1} ∈ B(x_{0}, r_{0}) and r̃ := r_{0} − |x − x_{0}|_{X} then

B(f(x_{0}), βr̃) ⊆ V.

Finally in this ball f will satisfy the estimates

β|x_{2} − x_{1}|_{X} ≤ |f(x_{2}) − f(x_{1})|_{Y} ≤ ∥f′(x_{0})∥(1 + ρ)|x_{2} − x_{1}|_{X}.

Proof. Fix ρ with 0 < ρ < 1 and and to simplify set L := f′(x_{0}). Then as in Remark 4.3 there is an r_{0} so that

(4.3) x ∈ \overline{B}(x_{0}, r_{0}) implies ∥L^{−1}f′(x) − I_{X}∥ ≤ ρ.

Let F: U → Y be given by

F (x) = L^{−1}f(x) − x.

Then the derivative of F is

F′(x) = L^{−1}f′(x) − I_{X}.

Thus for x ∈ \overline{B}(x_{0}, r_{0})

∥F′(x)∥ ≤ ρ.

Now by Proposition 2.13 for x_{1}, x_{2} ∈ B(x_{0}, r_{0})

|L^{−1}f(x_{2}) − L^{−1}f(x_{1}) − (x_{2} − x_{1})|_{X} = |F (x_{2}) − F (x_{1})|_{X}

≤ ρ|x_{2} − x_{1}|_{X}. (4.4)

By continuity with will also hold for all x_{1}, x_{2} ∈ \overline{B}(x_{0}, r_{0}). Therefore f|_{\overline{B}(x_{0},r_{0})} : \overline{B}(x_{0}, r_{0}) → Y satisfies the hypothesis of Theorem 3.1 and so we can use the conclusions of that theorem. In particular the image V := f[B(r_{0}, r_{0})] is open and if β is given by (4.2) then for all x_{1}, x_{2} ∈ B(x_{0}, r_{0})

β|x_{2} − x_{1}|_{X} ≤ |f(x_{2}) − f(x_{1})|_{Y} ≤ ∥L∥(1 + ρ)|x_{2} − x_{1}|_{X}. (4.5)

Let φ := f|_{B(x_{0},r_{0})}^{−1} : V → B(x_{0}, r_{0}) be the inverse of f|_{B(x_{0},r_{0})}^{−1}. We now break the rest of the proof up into small steps leaving most of the details to the reader.

Step 1. The map φ: V → B(x_{0}, r_{0}) satisfies

\frac{1}{∥L∥(1 + ρ)}|y_{2} − y_{1}|_{Y} ≤ |φ(y_{2}) − φ(y_{1})|_{X} ≤ \frac{1}{β} |y_{2} − y_{1}|_{Y}

holds for all y_{1}, y_{2} ∈ V. Thus φ is continuous.

Exercise 4.4. Prove this. Hint: Use the inequalities (4.5)

Step 2. At each point x ∈ B(x_{0}, r_{0}) the derivative f′(x): X → Y is an invertible linear map and

∥f′(x)∥ ≤ \frac{∥L∥}{1 − ρ}.

Exercise 4.5. Prove this. Hint: Write f′(x) = LL^{−1}f′(x). Then ∥I_{X} − L^{−1}f′(x)∥ ≤ ρ by (4.3) and use Proposition 2.4 to conclude that L^{−1}f′(x) is invertible and ∥L^{−1}f′(x)∥ ≤ 1/(1 − ρ). Then f′(x) is a product of invertible maps.

Step 3. Let b ∈ V. Then φ is differentiable at b with

φ′(b) = f′(φ(b))^{−1}.

Exercise 4.6. Prove this by justifying the following: Let a = φ(b) so that b = f(a). As f is differentiable

f(x) − f(a) = f′(a)(x − a) + |x − a|_{X}ε(x; a)

where lim_{x→a} |ε(x; a)|_{Y} = 0. Letting x = φ(y) and a = φ(b) gives

y − b = f(φ(y)) − f(φ(b))
= f′(φ(b))(φ(y) − φ(b)) + |φ(y) − φ(b)|_{X}ε(φ(y); φ(b)).

By step 4 f′(φ(b)) exists and ∥f′(φ(b))^{−1}∥ ≤ ∥L∥/(1 − ρ). So solve for φ(y) − φ(b) in the last displayed equation to get

φ(y) − φ(b) = f′(φ(b))^{−1}(y − b) − |φ(y) − φ(b)|_{X}f′(φ(b))^{−1}ε(φ(y); φ(b))
= f′(φ(b))^{−1}(y − b)

− |y − b|_{X} \frac{|φ(y) − φ(b)|_{X}}{|y − b|_{X}} f′(φ(b))^{−1}ε(φ(y); φ(b))

= f′(φ(b))^{−1}(y − b) − |y − b|_{X}ε_{1}(y; b)

where this defines ε_{1}(x; b). But (Step 1)

\frac{|φ(y) − φ(b)|_{X}}{|y − b|_{Y}} ≤ \frac{1}{β} ,

so that

|ε_{1}(y, b)|_{X} ≤ \frac{∥f′(φ(b))∥}{β}|ε(φ(y); φ(b))|_{X}.

But φ is continuous and so lim_{y→b} |ε_{1}(y; b)|_{X} = 0.

Step 4. The map y ↦ φ′(y) is continuous on the set V.

Exercise 4.7. Prove this. Hint: As φ′(y) = f′(φ(y))^{−1} the map y ↦ φ′(y) is a composition of the maps y ↦ φ(y), x ↦ f′(x) and A ↦ A^{−1} each of which is continuous either by Step 1, the assumption that f is continuously differentiable, or Proposition 2.4.

Putting the above together completes the proof of the inverse function theorem.

Exercise 4.8. Prove the statements given in Remark 4.3. Hint: In the proof of Theorem 4.2 the bound (4.4) which allows the results of Theorem 3.1 to be used.

5. Implicit Function Theorem: Surjective From

5.1. Preliminary results on surjective linear maps. Let X, Y be Banach spaces and L: X → Y a bounded linear map. Then L has a right inverse iff there there is a bounded linear map S: Y → X so that LS = I_{Y}. This clearly implies that L is surjective (as if y ∈ Y then y = Lx with x = Sy). For linear maps L between finite dimensional spaces it is standard and elementary that L is surjective if and only if it has a right inverse. However there are examples of surjective linear maps L: X → Y between Banach spaces that do not have right inverses. We do have the following.

Proposition 5.1. Let L: X → Y be a Bounded surjective linear map between Banach spaces. Then L has a right inverse in the following cases:

1. Y is finite dimensional or

2. X is a Hilbert space (that is an inner product space so that the induced norm is complete).

Exercise 5.2. Prove this. Hint: For the first part let y_{1}, …, y_{n} be a basis of Y and let x_{i} ∈ X so that Lx_{i} = y_{i}. Then define S to be the unique linear map S: Y → X so that Sy_{i} = x_{i}. The second part is unfair unless you know some functional analysis, but here is the idea. Let ker L be the kernel (also called the null space) of L and let X_{1} := (ker L)^{⊥} be the orthogonal complement of ker L. Then L|_{X_{1}} : X → Y is bijective and therefore L|_{X_{1}}^{−1} : Y → X_{1} is a well defined linear map. But then the open mapping theorem implies that L|_{X_{1}}^{−1} is bounded. Thus S := L|_{X_{1}}^{−1} gives the desired right inverse.

Definition 5.3. Let X be a Banach space and let X_{0} and X_{1} be a closed linear subspaces of X. Then X is a direct sum of X_{0} and X_{1} , written as X = X_{0} ⊕ X_{1}, iff X_{0} ∩ X_{1} = {0} and there is a constant C so that every x ∈ X can be written as x = x_{0} + x_{1} with x_{0} ∈ X_{0}, x_{1} ∈ X_{1} and |x_{0}|_{X}, |x_{1}|_{X} ≤ C|x|_{X}.

Definition 5.4. Let X be a Banach space and X_{0} a closed linear subspace of X. Then X_{0} is complimented iff there is a closed linear subspace X_{1} so that X is a direct sum X = X_{0} ⊕ X_{1}.

Exercise 5.5 (For those who know the open mapping theorem). Let X be a Banach space and X_{0}, X_{1} closed subspaces of X such that X_{0}∩X_{1} = {0} and so that for each x ∈ X there are x_{0} ∈ X_{0} and x_{1} ∈ X_{1} such that x = x_{0} +x_{1}. Then there is a constant C > 0 so that if x = x_{0} + x_{1} with x_{0} ∈ X_{0} and x_{1} ∈ X_{1} then |x_{0}|_{X}, |x_{1}|_{X} ≤ C|x|_{X}. Hint: Let Y := X_{0} × X_{1} and give Y the norm |(x_{0}, x_{1})|_{Y} := |x_{0}|_{X} + |x_{1}|_{X}. This norm makes Y into a Banach space. Define a linear map T: Y → X by T (x_{0}, x_{1}) = x_{0} + x_{1}. This in linear and bijective. Moreover |T (x_{0}, x_{1})|_{X} = |x_{0} + x_{1}|_{X} ≤ |x_{0}|_{X} + |x_{1}|_{X} = |(x_{0}, x_{1})|_{Y}. Thus T is bounded with ∥T ∥ = 1. Therefore by the open mapping theorem the linear map T^{−1} : X → Y is bounded. If x = x_{0} + x_{1} with x_{0} ∈ X_{0} and x_{1} ∈ X_{1} then T (x_{0}, x_{1}) = x and so (x_{0} + x_{1}) = T^{−1}x. Thus |x_{0}|_{X}, |x_{1}|_{X} ≤ |x_{0}|_{X} + |x_{1}|_{X} = |(x_{0}, x_{1})|_{Y} ≤ ∥T^{−1}∥|x|_{X}. Therefore we can use C = ∥T^{−1}∥.

Proposition 5.6. Let L: X → Y be a bounded linear map between Banach spaces and assume that L has a right inverse S: Y → X. Let P := SL: X → X. Then

P^{2} = P

and if

X_{0} := ker P = ker L, X_{1} = ker(I_{X} − P)

then X is a direct sum X = X_{0} ⊕ X_{1}, and L_{1} := L|_{X_{1}} : X_{1} → Y in an bounded invertible linear map with inverse S: Y → X_{1} ⊆ X.

Exercise 5.7. Prove this by justifying the following. First P^{2} = SLSL = SI_{Y}L = SL = P. Set

P_{1} := P = SL, P_{0} = I_{X} − P.

Then P_{0} and P_{1} are bounded linear maps P_{i}: X → X that satisfy

P_{0} + P_{1} = I_{X}, P_{0}^{2} = P_{0}, P_{1}^{2} = P_{1}, P_{0}P_{1} = P_{1}P_{0} = 0.

These relations and the definition of X_{0} and X_{1} then imply

X_{0} = image P_{0} = ker P_{1}, X_{1} = image P_{1} = ker P_{0}.

(Here image P_{i} = P_{i}[X] = {P_{i}x : x ∈ X} is the image of P_{i}.) Therefore if x ∈ X we have x = P_{1}x + P_{0}x where x_{0} = P_{1}x ∈ X_{0} and x_{1} = P_{0}x ∈ X_{1} and |P_{i}x|_{X} ≤ C|x|_{X} where C := max{∥P_{0}∥, ∥P_{1}∥}. Also X_{0} ∩ X_{1} = {0} and so X = X_{0} ⊕ X_{1}.

Let y ∈ Y. Then Sy = SI_{Y}y = SLSy = P y = P_{1}y ∈ X_{1}. Therefore image S ⊆ X_{1}. But if x ∈ X_{1} then x = P_{1}x = P x = SLx ∈ image S. Thus image S = X_{1}. Also if x ∈ X_{1} then SLx = P x = P_{1}x = x so SL = I_{X_{1}}. Therefore S is the inverse of L|_{X_{1}}.

5.2. The surjective form of the implicit function theorem for Lipschitz maps.

A. Appendix: Contraction Mappings and the Banach Fixed Point Theorem

In this appendix we give the statement and proof of the Banach Fixed Point Theorem (also called the contraction mapping principle).

A.1. Some Review. There are several series that will come up several times and so we show know how to sum them. The first is the geometric series. This is the series

∑_{k=0}^{∞} ar^{k} = a + ar + ar^{2} + ar^{3} + ⋯ = \frac{a}{1 − r} = \frac{first term}{1 − ratio}

which converges when the ratio satisfies |r| < 1. (This is true for real or complex r.) Thus will often show up as follows:

Proposition A.1. Let ∑_{k=0}^{∞} a_{k} be a series or real or complex numbers so that for some C > 0 and r < 1 the bound |a_{k}| ≤ Ar^{k} holds. Then ∑_{k=0}^{∞} a_{k} converges and the sum satisfies |∑_{k=0}^{∞} a_{k}| ≤ C/(1 − r).

It is also good to have and estimate of the error when we only use n terms of the sum. Here is some practice for you:

Exercise A.2. Let A = ∑_{k=0}^{∞} a_{k} and A_{n} = ∑_{k=0}^{n} a_{k} and assume that the bound |a_{k}| ≤ Cr^{k} holds for all k and some r < 1. Then show

|A − A_{n}| ≤ \frac{Cr^{n+1}}{1 − r} .

A.2. Metric spaces. Certain metric spaces will be usefully to us (mostly metric spaces, in fact Banach spaces, of functions. Recall that a metric space (X, d) is a nonempty set X with a function d: X × X → [0, ∞) so that

1. d(x, y) ≥ 0 and d(x, y) = 0 iff x = y,

2. d(x, y) = d(y, x), (d is symmetric),

3. d(x, z) ≤ d(x, y) + d(y, z), (the triangle inequality). The metric space (X, d) is complete iff any Cauchy sequence {x_{k}}_{k=1}^{∞} in X converges. Given a sequence {x_{k}}_{k=1}^{∞} in a metric space, then by repeated use of the triangle inequality for m < n we can estimate

d(x_{m}, x_{n}) ≤ d(x_{m}, x_{m+1})+d(x_{m+1}, x_{m+2})+⋯+d(x_{n−2}, x_{n−1})+d(x_{n−1}, x_{n}).

We can combine this with some of the results above on series to get a dumb looking, but still useful, criterion for a series to be a Cauchy sequence.

Exercise A.3. Let (X, d) be a complete metric space and let {x_{k}}_{k=0}^{∞} be a sequence in X and assume that for some C > 0 and r < 1 that d(x_{k}, x_{k+1}) ≤ Cr^{k}. Then show

1. {x_{k}}_{k=0}^{∞} is a Cauchy sequence and therefore converges to some point x_{∗} of X.

2. For each n the estimate d(x_{n}, x_{∗}) ≤ Cr^{n}/(1 − r) holds.

A.3. The Banach Fixed Point Theorem. We now give what is one of the more important existence theorems for general non-linear equations. Let (X, d) be a metric space (say that (X, d) is the plane R^{2} with its usual metric), and let F: X → X be a continuous map. Then given y ∈ X we would like a method for solving the equation F (x) = y for x. Experience has shown that it is often better to rewrite this equation as f(x) = x for a new function f. (In the case X = R^{2} then for any constant let f(x) = c(F (x) − y) + x, then the equation f(x) = x has the same solutions as F (x) = y.) Thus it turns out that many useful theorems about solving equations are stated as fixed point theorems. I don’t have any real insight into why fixed point theorems turn out to easier to handle than other types of theorems on solutions, but this is the case. (In topology there is the Brouwer fixed point theorem which is a very general result about solving n equations in n unknowns.)

Let (X, d) be a metric space. Then a map f: X → X is a contraction iff there is a constant ρ < 1 so that d(f(x), f(y)) ≤ ρd(x, y). The number ρ is called the contraction factor. It is easy to see that any contraction is continuous.

Let Y be any set and g: Y → Y. Then the point y_{0} ∈ Y is a fixed point of g iff g(y_{0}) = y_{0}.

Exercise A.4. Let (X, d) be a metric space and f: X → X a contraction with contraction factor ρ. Then show that f has at most one fixed point. Hint: Assume that a, b ∈ X are fixed points of f. Then d(a, b) = d(f(a), f(b)) ≤ ρd(a, b).

Theorem A.5 (Banach Fixed Point Theorem). Let (X, d) be a complete metric space and f: X → X be a contraction with contraction factor ρ < 1. Then show that f has a unique fixed point x_{∗} in X. This fixed point can be found by starting with any x_{0} ∈ X and defining a sequence {x_{k}}_{k=0}^{∞} by recursion

x_{1} = f(x_{0}), x_{2} = f(x_{1}), x_{3} = f(x_{2}), … x_{k+1} = f(x_{k}), …

Then x_{∗} = lim_{k→∞} x_{k}. There is also an estimate on the error of using x_{n} as an approximation to x_{∗}. This is

d(x_{n}, x_{∗}) ≤ \frac{d(x_{0}, x_{1})ρ^{n}}{1 − ρ} . (A.1)

Remark A.6. This result was in Banach’s thesis which appeared in published form in 1922. In his thesis and this paper he also introduced “complete normed linear space” which have since been renamed as Banach spaces. The idea of looking at the sequence x_{0}, x_{1} = f(x_{0}), x_{2} = f(x_{1}) … is an abstraction of an idea of Picard.

Exercise A.7. Prove the theorem by doing the following:

1. For the sequence defined above show that d(x_{k}, x_{k+1}) ≤ d(x_{0}, x_{1})ρ^{n}.

2. Use exercise A.3 to conclude that {x_{k}}_{k=0}^{∞} converges to some point x_{∗} of X, and that the estimate (A.1) holds.

3. Show that x_{∗} is a fixed point of f. Hint: Take the limit as k → ∞ of x_{n+1} = f(x_{n}).

4. Show that x_{∗} is the only fixed point of f.