18.099b Problem Set 7b Due: Thursday, April 29th.

This assignment is to write an essay on the Banach fixed-point theorem and applications. It should be typeset in Tex. Arrange and express the material discussed below in whatever way you think best. The paper should flow smoothly and be well motivated.

Suppose (X, d_{1}) and (Y, d_{2}) are metric spaces. A map f : X → Y is called a contraction if there exists a real number 0 ≤ λ < 1 such that

d_{1}(f(x), f(y)) ≤ λ · d_{2}(x, y) for all x, y ∈ X.

Observe that a contraction is always continuous.

If f is a real-valued differentiable function on an interval [a, b] and there exists λ < 1 such that |f′(x)| ≤ λ for all x ∈ [a, b], then f is a contraction on [a, b].

Prove the Banach fixed-point theorem which states: If (X, d) is a complete metric space and f : X → X is a contraction, then there exists a unique point x ∈ X such that f(x) = x (called a fixed-point of f).

Discuss the following two applications:

1. Hausdorff metric on compact sets and fractals. Fix n > 0 and view ℝ^{n} as a metric space under the usual distance function d. For K ⊂ ℝ^{n} a non-empty compact set and x ∈ ℝ^{n}, define the distance from x to K by

d(x, K) := inf{d(x, y) : y ∈ K} = min{d(x, y) : y ∈ K}

(the first equality is a definition, the second equality requires proof). Given ϵ ≥ 0 we define

K_{ϵ} := {x ∈ ℝ^{n} : d(x, K) ≤ ϵ}.

If K, K′ ⊂ ℝ^{n} are non-empty compact sets, the Hausdorff distance between K and K′ is

d(K, K′) := inf{ϵ ≥ 0 : K ⊂ K′_{ϵ} and K′ ⊂ K_{ϵ}}.

Let K be the set of all non-empty compact subsets of ℝ^{n} with the Hausdorff distance function d defined above. Show that (K, d) is a complete metric space.

Show that if f_{1}, …, f_{m} : ℝ^{n} → ℝ^{n} are contractions then there is a unique compact set K ⊂ ℝ^{n} such that

K = f_{1}(K) ∪ ⋯ ∪ f_{m}(K).

Hint: Show that the map K ↦ f_{1}(K) ∪ ⋯ ∪ f_{m}(K) is a contraction on K and then use the Banach fixed-point theorem

Such a set is called a fractal. Include a short discussion of what is interesting about fractals.

2. Linear algebraic equations. Consider the system of n linear equations in n unknowns

(1)  ∑_{j=1}^{n} a_{i,j}x_{j} = b_{i}

for i = 1, …, n, where the a_{i,j}’s and b_{i}’s are real numbers. This can be expressed in matrix notation by

(2)  Ax = b

where A is the n × n matrix [a_{i,j}], x is the n × 1 column vector of indeterminates [x_{j}], and b is the n × 1 column vector [b_{j}]. Note that x ∈ ℝ^{n} is a solution to (2) exactly if it is a fixed-point of the map f : ℝ^{n} → ℝ^{n} given by f(x) = (I − A)x + b where I is the identity n × n matrix. Write I − A as the n × n matrix [c_{i,j}].

Show that if

max{∑_{j=1}^{n} |c_{i,j}| : i = 1, …, n} < 1

or

max{∑_{i=1}^{n} |c_{i,j}| : j = 1, …, n} < 1

then (2) has a (unique) solution. Hint: Use the Banach fixed-point theorem on ℝ^{n} equipped with two different distance functions. To handle the first condition use

d_{1}(x, y) = max{|x_{i} − y_{i}| : i = 1, …, n},

and to handle the second use

d_{2}(x, y) = ∑_{i=1}^{m} |x_{i} − y_{i}|.