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 11.1.39Let f : X → Y where
(X, d)
and
(Y,ρ)
are metric spaces. Then f is said tobe Lipschitz continuousif for every x,
ˆx
∈ X, ρ
(f (x),f (ˆx))
≤ rd
(x,xˆ)
. The function is called acontraction map if r < 1.
The big theorem about contraction maps is the following.
Theorem 11.1.40Let f :
(X,d)
→
(X,d)
be a contraction map and let
(X, d)
be a complete metricspace. Thus Cauchy sequences converge and also d
(f (x ),f (ˆx))
≤ rd
(x,ˆx)
where r < 1. Then f has aunique 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,x ) ≤ d(x0,f-(x0))-
0 1− r
Also, for each n,
d(fn (x0),x0) ≤ d(x0,f-(x0)),
1− r
and x = lim_{n→∞}f^{n}
(x0)
.
Proof: Pick x_{0}∈ X and consider the sequence of iterates of the map,
x0,f (x0),f2(x0),⋅⋅⋅.
We argue that this is a Cauchy sequence. For m < n, it follows from the triangle inequality,
which shows that this is indeed a Cauchy sequence. Therefore, there exists x such that
lim f n(x0) = x
n→ ∞
By continuity,
( n ) n+1
f (x) = f lnim→∞ f (x0) = nl→im∞ f (x0) = x.
Also note that this estimate yields
d(x0,f (x0))
d(x0,f n(x0)) ≤ -----------
1− r
Now d
(x ,x )
0
≤ d
(x ,fn(x ))
0 0
+ d
(fn(x ),x)
0
and so
n d(x0,f (x0))
d (x0,x)− d (f (x0),x ) ≤ 1 − r
Letting n →∞, it follows that
d(x0,x) ≤ d-(x0,f-(x0))
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
(x,x′)
= 0 because r < 1. ■
The above is the usual formulation of this important theorem, but we actually proved a better
result.
Corollary 11.1.41Let B be a closed subset of the complete metric space
(X,d)
and let f : B → X be acontraction 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(x0)}
_{n=1}^{∞}remains in B. Then fhas a unique fixed point in B which is the limit of the sequence of iterates. This is a pointx ∈ B such that f
(x )
= x. In the case that B =B
(x0,δ)
, the sequence of iterates satisfies theinequality
d(x0,f (x0))
d (fn(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,
n∑−1
d (fm (x0),fn(x0)) ≤ d (fk+1(x0),f k(x0))
k=m
∑∞ rm
≤ rkd (f (x0),x0) = ----d(f (x0),x0)
k=m 1− r
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,
( )
x = lim fn (x0) = lim fn+1(x0) = f lim fn (x0) = f (x)
n→∞ n→ ∞ n→∞
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
n --1--
d(x0,f (x0)) ≤ 1 − rd(f (x0),x0)
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 11.1.42Let f :
(X,d)
→
(X, d)
have the property that for some n ∈ ℕ, f^{n}is acontraction map and let
(X,d)
be a complete metric space. Then there is a unique fixed point for f.As in the earlier theorem the sequence of iterates
{fn(x0)}
_{n=1}^{∞}also converges to the fixed point.
Proof:From Theorem 11.1.40 there is a unique fixed point for f^{n}. Thus
fn(x) = x
Then
fn(f (x)) = f n+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
→ x which contradicts the above
inequality. Hence the sequence of iterates converges to x, as it did for f a contraction map.
■
Now with the above material on analysis, it is time to begin using the ideas from linear algebra in this
special case where the field of scalars is ℝ or ℂ.