Contractions and Fixed Points

The essential features of the linear maps that lead to fractals is that they reduce distances. These sort of maps are called contractions.

Definition: Let X be a metric space with distance function d(x,y). A transformation is called a contraction if there is a number s, , such that for any two points we have

 

s is called a contractivity factor of w. The smallest possible s that works is sometimes called the contractivity factor of w.

It's a crucial point that the factor s be strictly less than one. If we iterate our contraction,

Since as , we obtain a basic fact:

Theorem: If X is a complete metric space, then

exists and is independent of the choice of . Moreover, is the unique fixed point of w.

A little more discussion of this theorem is in order. Choose any point . Then

is certainly an infinite sequence of points in X. What does completeness mean? It means that any bounded sequence has a point of accumulation which we will call . We claim there is only one point of accumulation. Suppose there were another one . We will show this assumption is impossible.

We begin by noting that does not wander too far away from x, i.e. that this sequence is bounded. Suppose d(x,w(x))=t (which might be 0). Then by the contraction property. By the triangle inequality for the distance function,

using the formula for the sum of a geometric series. Since s<1, this is bounded above by . Therefore, all the terms in the sequence of iterates remain within a bounded distance of x. Let's call this maximum distance M.

Returning to our assumption that two points of accumulation and exist, suppose . There is an integer N such that . Our hypothesis implies there are such that and . On the other hand,

By the triangle inequality,

This leads to an absurd inequality . We have now established that our sequence has precisely one point of accumulation , and that

If we apply w (which is continuous, although that takes a little sorting through) to each term of the sequence, we obtain the same limit, which proves that . The contraction property may again be employed to show this is the only fixed point of w and all sequences of iterates of w converge to this fixed point. This shows that the limit of the sequence of iterates is completely independent of the seed point.