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.
Definition 2.8.1Let f : X → Y where
(X,d)
and
(Y,ρ)
are metric spaces.Then f is said to be Lipschitz continuousif for every x,
xˆ
∈ X, ρ
(f (x),f (xˆ))
≤rd
(x,ˆx)
. The function is called a contraction map if r < 1.
The big theorem about contraction maps is the following.
Theorem 2.8.2Let f :
(X, d)
→
(X,d)
be a contraction map and let
(X,d)
be acomplete metric space. Thus Cauchy sequences converge and also d
(f (x),f (ˆx))
≤ rd
(x,ˆx)
where r < 1. Then f has a unique fixed point. This is a point x ∈ X such that f
(x)
= x. Also,if x_{0}is any point of X, then
d (x ,f (x ))
d(x,x0) ≤---0----0--
1 − r
Also, for each n,
d(fn(x ),x ) ≤ d-(x0,f-(x0)),
0 0 1− r
and x = lim_{n→∞}f^{n}
(x0)
.
Proof: Pick x_{0}∈ 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
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
(x,x′)
= 0 because r < 1. ■
The above is the usual formulation of this important theorem, but we actually proved a
better result.
Corollary 2.8.3Let B be a closed subset of the complete metric space
(X, d)
and letf : B → X be a contraction map
d(f (x),f (xˆ)) ≤ rd (x,xˆ) , r < 1.
Also suppose there exists x_{0}∈ B such that the sequence of iterates
{fn(x )}
0
_{n=1}^{∞}remainsin B. Then f has a unique fixed point in B which is the limit of the sequence of iterates. Thisis a point x ∈ B such that f
(x)
= x. In the case that B =B
(x ,δ)
0
, the sequence of iteratessatisfies the inequality
n d(x0,f (x0))
d (f (x0),x0) ≤ 1− r
and so it will remain in B if
d(x0,f (x0))< δ.
1− r
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
(x,x′)
= d
(f (x) ,f (x′))
≤ rd
(x,x′)
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.
Theorem 2.8.4Let f :
(X, d)
→
(X, d)
have the property that for some n ∈ ℕ,f^{n}is a contraction map and let
(X, d)
be a complete metric space. Then there is a uniquefixed point for f. As in the earlier theorem the sequence of iterates
n
{f (x0)}
_{n=1}^{∞}alsoconverges to the fixed point.
Proof:From Theorem 2.8.2 there is a unique fixed point for f^{n}. Thus
fn(x) = x
Then
fn(f (x)) = fn+1 (x) = f (x)
By uniqueness, f
(x)
= 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_{k}n + r_{k} where r_{k} is one of the numbers
{0,1,2,⋅⋅⋅,n − 1}
. 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