Contraction mappings and hyperbolic IFS's

We may now add the missing ingredient to our definition of Iterated Function System. A hyperbolic IFS is a finite collection of affine linear maps of which are also contractions. The contractive nature is much more important than the fact that these maps are linear. The notion of an iterated function system (coined by Barnsley) is equally valid in any metric space.

Definition: A hyperbolic Iterated Function System on a complete metric space X is a finite collection of contractions . If these contractions have contractivity factors , respectively, we say is a contractivity factor of this IFS.

Our goal is to describe the attractor of an IFS. The basic step in forming this attractor is to start with a compact set K and apply all the contractions . These are what we have been calling the self-similar pieces of the fractals we have seen so far. The union of these pieces is a new set which is slightly ``closer'' to the attractor. We formulate this process as a mapping of compact sets:

 

In this formulation we are no longer assuming that the pieces are non-overlapping. The process of applying W is now a dynamical system:

The attractor is the ``limit'' of this sequence of sets. To make sense of this, we have to create a notion of distance between sets, instead of merely between points.

Barnsley calls the set of all compact subsets of X the space of fractals because this is where we find the attractors of dynamical systems. We would like a distance function d(A,B) on pairs of compact sets that behaves in the same way as the distance between points.

The key condition to satisfy is positivity:

d(A,B)=0 if and only if A=B

If d(A,B) is the minimum distance between a point of A and a point of B, then the two sets can just touch on their boundaries and still have d(A,B)=0. If we choose d(A,B) to be the maximum distance between a point of A and a point of B, we will have d(A,A)>0 for any compact set with more than one point. The correct choice is something in between these two options, a combination of minimum and maximum.

If x is any point in X, and A is a compact subset of X, we define d(x,A) to be the minimum of d(x,y) as y ranges over points in A. (Compactness assures that a minimum is achieved.) Given a second compact set B, we define

If d(B,A)=0, then d(x,A)=0 for all . This means each also belongs to A, or that . This almost fulfills the positivity condition. The new problem is lack of symmetry .

As an example, let A be the closed disk of radius 1 centered at (0,0), and B the closed disk of radius 2 centered at (2,0) (see this figure). d(B,A) is achieved at the points and , while d(A,B) occurs for the points and . Hence, d(A,B)=1 and d(B,A)=3.

  
Figure 42: Distance between sets

There is a simple way of rectifying the symmetry problem and satisfying the positivity condition at the same time. We define

Clearly, h(A,B)=h(B,A). Also, if h(A,B)=0, then both d(A,B) and d(B,A) must vanish. This implies and , which means that A=B. These steps are reversible, so that if A=b then h(A,B)=0. Our love affair with this new distance h(A,B) will be complete if we establish the triangle inequality

This labor of love we leave for the reader. The new distance function h(A,B) is called the Hausdorff metric on the space of fractals. At last, is a genuine metric space, with all the associated concepts of limits and convergence. We say a sequence of compact sets converges to if

Returning to the hyperbolic IFS and the associated map defined in (6.2), we now know what it means to say that the sequence of iterates converges to some compact set A. The question is why this would be true. The answer is a theorem:

Theorem: W is a contraction on with contractivity factor .

This means that for any . Our previous theorem about contractions and fixed points now furnishes a unique fixed point A of W and asserts that all sequences of iterates of W converge upon A. At last, we have the attractor of the IFS, which is this fixed point A of W.

How do we prove that W is a contraction? We give the proof next as an exhibit of how to manipulate maximum and minimum statements. First,

by definition. Then for any point ,

for any j. Next we compute the maximum of d(x,W(B)) over all . Since , we have for some or n and for some . Then by our previous inequality

For any z, . Thus,

when and . Then

Taking the maximum over all j, we conclude

Carrying out the same argument after interchanging A and B, we get

These last two inequalities imply that .

Next, we present two examples of the iteration of W. First, for the Cantor set, let's deliberately choose K=[-2,0] rather than I=[0,1]. Our theory says that the sequence of iterates should nonetheless converges onto the same Cantor set. What we shall do is display simultaneously the first few iterates . The process for generating the next iterate is

Then and

We can detect how the iterates are moving to the right. The figure below shows several more generations ordered vertically verifying that the limiting set is still the usual Cantor set in the interval [0,1]. Compare this figure with this figure.

  
Figure 43: Converging to the Cantor set

Secondly, we introduce the example of the Sierpiński triangle. This fractal begins with a triangle, for example, the equilateral triangle T with vertices , and . The midpoints of the three sides are , and . There are three equilateral triangles at each vertex , with vertices , with and with . We define three affine maps , , as the ones that take T onto , fixing and preserving orientation. For example, , and . Each has scaling factor . The precise formulas are given below

The Sierpiński triangle is the attractor of this IFS. In this figure, we show the original triangle along with the three smaller triangles labelled 1,2,3 corresponding to .

  
Figure 44: Sierpiński IFS: three linear maps transform the outer triangle into the three smaller triangles.

To compute , we plot all the pieces

where the a's range over all choices of 1, 2, or 3. This figure shows all ``words'' of length 4 applied to T in thin outline; all words of length 3 are plotted in thick blue. The red outline marks the particular piece . The symbols in the word correspond to smaller subdivisions as we move from left to right.

  
Figure 45: The Sierpiński IFS to fourth generation

Carrying out this process to the seventh generation produces a reasonable approximation of the Sierpiński Triangle, displayed in this figure.

  
Figure 46: The Sierpiński triangle