Iterated Function Systems
Up until now we have been drawing fractals by iterating a simple procedure
(like removing the middle thirds or adding a small triangle to each side)
on smaller and smaller scales. This procedure is called the 'geometric
construction' of fractals because we are drawing the successive stages (the
actual fractal being the (infinite) limit of the stages). This procedure
allowed us to see how the complexity of the fractal is generated and also
to calculate quantities such as the length of the Koch curve, and in the
case of the Cantor set to find a way to describe the points in the
fractal (via triadic expansions of numbers).
See the IFS page for examples of fractals drwan with an IFS.
The lenses of the MRCM's we will be considering for the moment will be 'simple' ones, they will be linear contractions; that is, they will shrink, rotate, reflect or shear the image (or a combination of these) in such a way that if you iterate the copying done by one such lens the image will shrink to a point (the fixed point; see below). These lenses can be represented by matrices; see Section 5.2 of the text. To arrange the images of the lenses to prescribed positions we add a translation (a shift) to the final image of each lens. Thus, the MRCM can be represented by a collection of matrices and translations.
Thus, to each lens of the MRCM is associated a (2 by 2) matrix F and a vector Q (a point in R^2); the matrix F represents the linear contraction and the Q represents the translation. F is a contraction, so || F(p) - F(q)|| < c || p - q|| for some c between 0 and 1, and where p and q are any two points in R^2. Note that the same is true for w = F + Q; ||w(p) - w(q)|| < c || p - q || because w(p) - w(q) = F(p) - F(q). We call w's of this form that are contractions affine contractions. We denote this mathematical model of a lens by w; w = F + Q (so if A is a subset of R^2, the image of A by this lens is w(A) = F(A) + Q, where F(A) denotes the set {F(p) as p ranges over all the points in A}, i.e., the image of A under F; see for example Figure 5.3). We can specify one of the w_i's by specifying the 6 numbers a,b,c,d,e,f where a,b,c,d are the entries of the matrix F and e,f are the x,y coordinates of the translation Q (as on page 236 for example; the parameters a,...,e for the functions w for all the fractals in Chapter 5 appear on page 295).
Putting the images made by each lens of the MRCM together means we take the union of all the functions w. So the IFS associated to the MRCM is W = w_1 U w_2 U ... U w_k (k lenses, and U denotes union). Thus, if A is any subset of R^2, then the image of A under one iteration of the MRCM is W(A) = w_1(A) U w_2(A) U ... U w_k(A) (this is formula (5.1) on page 239, for example).
Of course, we don't need to go through 'building' an MRCM just to get at the IFS. We can just define an IFS directly by taking k affine contractions (ie., functions of the form w = F + Q, as above) and put them together; W = w_1 U w_2 U ... U w_k. The blueprint of the IFS (or MRCM) is the image of a square S; blueprint = W(S) (see Figure 5.8). The blueprint tells us how many w_i's the IFS has (this is the number of images of S in the blueprint), and what kind of affine contraction each w_i is (the shape of w_i(S) ).
It follows from the Contraction Mapping Principle (see below) that each IFS has a unique fixed point, ie., a set C such that W(C) = C. If we arrange the lenses of the associated MRCM properly (which means we choose the translations Q for each w_i properly), the fixed point will be a fractal (rather than just a few points or a line). By the Contraction Mapping Principle we also know that W^n(A) "converges" to C as n tends to infinity (see below). Here W^n(A) means the n-fold composition of W with itself; W^2(A) = W(W(A)), W^3(A) = W(W(W(A))), etc, and "converges" means h(C,W^n(A)) tends to zero as n tends to infinity, where h(A,B) is the Hausdorff distance between the sets A and B (see below).
The Contraction Mapping Principle (see Section 5.6 of the text;
in particular page 266)
This is an abstract theorem that states if you have a "contraction"
mapping on a "space" then the contraction has a unique fixed point
and the sequence obtained by iterating the map beginning with any point
in the space converges to the fixed point. The theorem is abstract because
it doesn't care what the particular space is made up of (points or other
things) as long as you have a well-defined notion of distance between
elements of the space (so the 'distance function' d, or metric, must satisfy the
normal properties of a distance function; see properties (1) to (4) on
the bottom of page 263-64). Let's call the space X and the mapping (function)
f. So f takes elements of X to (possibly) different elements of X. We
write this as f: X --> X. Then, f is a contraction on X with respect
to the metric d means d(f(x),f(y)) < c d(x,y) for some c between 0
and 1, where x and y are any two elements of X
and d(x,y) means the distance between x and y according to the
metric d (see the bottom of page 266).
There can be many different metrics d on a space X. For example, if X = R^2 then the four functions d(x,y) defined on page 264 are all metrics on R^2. Each of them gives us a different notion of measuring the distance between two points x and y in R^2. In Figure 5.39 the set of points a distance 1 from the origin (0,0) is drawn for three of the four metrics. In the centre is the usual (Euclidean) metric, so the set of points a distance 1 from the origin in that metric is the unit circle. For the other two metrics the set of points a distance 1 from the origin is not a circle but a diamond or square. Now, depending on the metric choosen, a particular function f: R^2 --> R^2 may or may not be a contraction. This is the subject of Section 5.7. For example, in Figure 5.44 they display a function that is a contraction with respect to the Euclidean metric, but is not a contraction with respect to two of the other metrics they defined on page 264.
We apply the Contraction Mapping Principle to two different cases; that of the w_i's (the 'lenses' of the MRCM) and that of the IFS W. In the case of the w_i's, we are talking about mappings on R^2 with the metric d being the usual (Euclidean) metric d(x,y) = ||x-y|| (see example (2) on page 264). So if w is a contraction on R^2 with respect to the Euclidean metric, then w has a fixed point p (a point in R^2); w(p) = p, and if q is any point in R^2, w^n(q) converges to p as n tends to infinity. This last statement means that ||w^n(q) - p|| tends to zero as n tends to infinity, so if {w^n(q)} is the sequence of points obtained by iterating w starting with q, the sequence converges to p.
In the case of an IFS, we are talking about mappings on the the space X of all subsets of R^2. We need a notion of distance - a metric on X. This we take to be the Hausdorff metric h (see below and pages 267-269). So h(A,B) is the Hausdorff distance between the sets A and B. According to Hutchinson, if the w_i's that make up the IFS are contractions on R^2 with respect to the Euclidean metric, then the IFS is a contraction on X with respect to the Hausdorff metric (see page 270). Therefore, these IFS's W have a fixed point D in X (D is a subset of R^2; it could be a point or something more complicated), and if A is any subset in R^2 (A is any element of X), then W^n(A) converges to D as n tends to infinity; h(W^n(A),D) tends to zero as n tends to infinity. By looking at the definition of the Hausdorff metric, you can see that if h(A,B) is very small, then the two sets A and B will look almost the same. So, for sufficiently large n, W^n(A) will look very much like the fixed point D. The fixed points are the fractals associated to the IFS W. So we can generate these fractals by iterating the IFS enough times beginning with any set A (see Figures 1.10 and 1.11).
The Hausdorff Metric (pages 267-269 of text)
The Hausdorff metric (or Hausdorff distance) gives us a precise way to measure
how much two sets differ. Two sets that look very different will be 'far
apart' in the Husdorff metric, while two sets that look very similar will be
'close together' in the Hausdorff metric (i.e., the Hausdorff distance between
the two sets will be large or small, respectively).
The definition of Hausdorff distance is given on page 268. By considering
the examples on page 269 and the ones done in class, you will convince
yourself that the Hausdorff metric does measure how much two sets look the
same.
There is a subtlety, though. This is easiest to grasp by considering the case where one set is a disc and the other the same disc but with the centre point (or any other point) removed. One verifies that the Hausdorff distance between these two sets is zero. Thus, the Hausdorff metric sees these two sets as the same one. One can think of more sophisticated examples of two sets that are not the same pointwise, but are the the same set as far as the Hausdorff metric is concerned (the Hausdorff distance between the two sets is zero). One such example is the set of end points of the intervals removed during the construction of the Cantor set; let's call this set A, and the Cantor set C. We know that the Cantor set contains plenty of points other than those end points (1/4 and 3/4 are just two examples of such numbers), but the Hausdorff distance between these two sets, h(A,C), is zero (I leave this for you to think about).
One consequence of this feature of the Hausdorff metric is that the images W^n(A) if an IFS (where A is just an arbitrary set) may not converge pointwise to the fixed point D of the IFS (the fractal). The images W^n(A) converge to D in the Hausdorff metric (i.e., h(W^n(A),D) tends to zero as n tends to infinity), which does not necessarily mean that the final image is exactly the fractal (i.e., that they are the same point by point). However, it 'almost' is because the Hausdorff distance between the final image and the fractal is zero ( W^n(A) converges to D in the Hausdorff metric as n tends to infinity; this is the Contraction Mapping Principle as explained above), and sets whose distance apart in the Hausdorff metric is zero look the same to our eye. So for example, if you iterate the IFS for the Cantor set beginning with the set A = [0,1] you will end up with exactly the Cantor set (this was our geometric construction), but if you iterate the IFS beginning with the set A = {0}, a single point, you will not end up with exactly the Cantor set (you will end up with some subset of the set of end points of the intervals removed). But what you end up with will look just like the Cantor set. (Recall the fact stated in class that the set of end points of the intervals removed during the construction of the Cantor set, {0, 1/3, 2/3, 1, 1/9, 2/9, 7/9, 8/9, ...}, is a distance 0 away from the Cantor set in the Hausdorff metric. To convince yourself of this note that it is enough to prove that for any point in the Cantor set there are end points arbitrarily close to it, and thus the Hausdorff distance will be 0 between the two sets.)