Analysis

2.8 Lipschitz Continuity And Contraction Maps

The following is of more interest in the case of normed vector spaces, but there is no harm in stating it in this more general setting. You should verify that the functions described in the following definition are all continuous.

The big theorem about contraction maps is the following.

Proof: Pick x₀ ∈ X and consider the sequence of iterates of the map,

2 x0,f (x0) ,f (x0),⋅⋅⋅.

We argue that this is a Cauchy sequence. For m < n, it follows from the triangle inequality,

m n n∑−1 ( k+1 k ) ∑∞ k d (f (x0),f (x0)) ≤ d f (x0),f (x0) ≤ r d(f (x0),x0) k=m k=m

The reason for this last is as follows.

( ) d f 2(x0),f (x0) ≤ rd(f (x0),x0)

d (f 3(x ),f2 (x )) ≤ rd (f2(x ),f (x )) ≤ r2d(f (x ),x ) 0 0 0 0 0 0

and so forth. Therefore,

rm d(fm (x0),fn (x0)) ≤ d (f (x0),x0)----- 1− r

which shows that this is indeed a Cauchy sequence. Therefore, there exists x such that

n nli→m∞ f (x0) = x

By continuity,

f (x ) = f ( lim fn(x )) = lim fn+1(x ) = x. n→ ∞ 0 n→ ∞ 0

Also note that this estimate yields

d (x0,fn (x0)) ≤ d(x0,f (x0)) 1− r

Now d

≤ d + d and so

d (x ,x)− d (fn (x ),x) ≤ d(x0,f (x0)) 0 0 1− r

Letting n →∞, it follows that

d (x0,f (x0)) d(x0,x) ≤---1-−-r---

It only remains to verify that there is only one fixed point. Suppose then that x,x^′ are two. Then

d(x,x′) = d(f (x),f (x ′)) ≤ rd(x′,x)

and so d

= 0 because r < 1. ■

The above is the usual formulation of this important theorem, but we actually proved a better result.

Proof: By assumption, the sequence of iterates stays in B. Then, as in the proof of the preceding theorem, for m < n, it follows from the triangle inequality,

Hence the sequence of iterates is Cauchy and must converge to a point x in X. However, B is closed and so it must be the case that x ∈ B. Then as before,

n n+1 ( n ) x = lnim→∞ f (x0) = nl→im∞ f (x0) = f lnim→∞ f (x0) = f (x)

As to the sequence of iterates remaining in B where B is a ball as described, the inequality above in the case where m = 0 yields

d(x0,fn(x0)) ≤--1--d(f (x0),x0) 1 − r

and so, if the right side is less than δ, then the iterates remain in B. As to the fixed point being unique, it is as before. If x,x^′ are both fixed points in B, then d

= d ≤ rd and so x = x^′. ■

The contraction mapping theorem has an extremely useful generalization. In order to get a unique fixed point, it suffices to have some power of f a contraction map.

Proof: From Theorem 2.8.2 there is a unique fixed point for fⁿ. Thus

fn(x) = x

Then

fn(f (x)) = fn+1 (x) = f (x)

By uniqueness, f

= x.

Now consider the sequence of iterates. Suppose it fails to converge to x. Then there is ε > 0 and a subsequence n_k such that

d (fnk (x0),x) ≥ ε

Now n_k = p_kn + r_k where r_k is one of the numbers

. It follows that there exists one of these numbers which is repeated infinitely often. Call it r and let the further subsequence continue to be denoted as n_k. Thus

( ) d fpkn+r(x0),x ≥ ε

In other words,

d(fpkn(fr(x )),x) ≥ ε 0

However, from Theorem 2.8.2, as k →∞,f^p_kn

→ x which contradicts the above inequality. Hence the sequence of iterates converges to x, as it did for f a contraction map. ■