Even professional mathematicians often claim that the terms of mathematics may be confusing. For example, spaces and sets contain points. Yet there are spaces whose "points" are themselves sets. Functions map points to points but also comprise (function) spaces where each is considered an indivisible entity. From the mathematician's point of view, the advantage in abstracting a point from its diverse incarnations lies in the resulting generality. A statement is proven only once and then applied repeatedly in various disguises.

Case in point - contraction mappings and the related convergence theorems. Contraction mappings between metric spaces are defined by the property that they decrease the distance between points. In a complete space, any contraction mapping has a unique fixed point that can be found by (necessarily) convergent iterations. Convergence estimates relate proximity of iterations to the selection of the initial point. These general estimates apply as much to the solutions of integral and differential equations, matrices, and more general operators. Iterated Function Systems (IFSs) is another rewarding topic that capitalizes on the general theory.

An Iterated Function System is a finite collection of contractions F_i: XX defined on a metric space X. Each extends to a mapping (different but denoted by the same letter) F_i: H(X)H(X), where H(X) is the space whose points are nonempty compact subsets of X. When endowed with the Hausdorff metric, H(X) is complete if X is. In addition, contractions F_iXX remain contractions as mappings of H(X). Together, the F_i define another contraction F: H(X)H(X), by the following formula: for every AH(X), F(A) = F_i(A). Since we are working in a complete metric space, the general theory says that F has a fixed point (set!) A_F, so that F(A_F) = A_F, and this point can be reached by successive approximations from any starting location. Fixed points of IFSs are variously called attractors or invariant sets.

Two problems arise. One is to find the fixed point of a given IFS. The other is the inverse of the first: for a given set AH(X), find an IFS {F_i} that has A as its fixed point. In the general framework, the first problem is solved by what is known as the deterministic algorithm. Start with a set A₀H(X) and compute successively A_k = F_i(A_k-1) = F(A_k-1), k > 1. The sequence {A_k) converges to the fixed point A_F of {F_i} as k. The mathematics of the second, random iteration algorithm, is more complex but implementation is more straightforward. Assign positive frequencies p_i to the mappings F_i. Start with an arbitrary point x₀X. At every step k+1, select x_k+1 from the set {F_i(x_k)}. F_j(x_k) is selected with the probability p_j /p_i. In a sense that is made precise in [Barnsley], the sequence {x_k} converges to A_F. In practical terms, to depict an approximation of A_F on a computer, the points of the sequence are displayed starting with a reasonably large index. The numbers {p_i} have no effect on the fixed point A_F but influence significantly the rendering of its approximations.

The inverse problem is solved approximately by the Collage Theorem. In the words of M. Barnsley, the theorem tells us that to find an IFS whose attractor is "close to" or "looks like" a given set, one must endeavor to find a set of transformations - contraction mappings on a suitable set within which the given set lies - such that the union, or collage, of the images of the given set under transformations is near to the given set.

The applet below was inspired by Barnsley's celebrated depiction of the Black Spleenwort fern. Three parallelograms almost covering a fourth and bigger parallelogram seemed to be naturally associated with the fern and each of its smaller branches. There was another parallelogram - a smallish and a degenerate one - that is often omitted in reproductions.

Parallelograms lead to affine transformations, which map parallel lines onto parallel lines. Affine transformations can be uniquely determined from images of any three distinct points - in particular, three consecutive vertices of a parallelogram.

The applet consists of two parts. The first is the display area with several controls. First of all, there are several predefined IFSs to select from. For a given IFS, Start starts the iterations of the random iteration algorithm; Stop stops them. The applet attempts to optimally exploit the visual estate. The algorithm is heuristic and sometimes is off by an iteration or two. If needed, Shrink the emerging image and Clear the area. Often, the component sets F_i(A_F) intersect only over sets of lower dimension. In such a case, the Color option, that randomly assigns a color to each F_i(A_F), may create an unusually beautiful effect. Reset restores the original state of the IFS.

The simple observation that the two IFSs {F_i} and {F_iF_j} have exactly the same fixed point leads to a representation of A_F as a union of a growing number of sets. To see how this works use the Iterate button.

When the Transforms box is checked, the second portion of the applet (the Affine Basis Manipulator) appears in a separate window. This is the place to apply the Collage theorem. The Which buttons designate one of the parallelograms to manipulate. The selected parallelogram is displayed in red-blue-white colors whereas all others are entirely gray. Red and blue edges can be changed independently or the whole structure can rotate around their common vertex. The first parallelogram is the most basic. All others are considered its images under affine transformations. Please bear in mind that the number of transformations is, therefore, one fewer than the number of parallelograms.

Apply the Iterate button with the Affine Basis Manipulator on. The regions will multiply and become smaller. As a bonus, this gives a demonstration of the deterministic algorithm with the first parallelogram as the starting point.

Each of the parallelograms is an image of the unit square (0,0)-(1,1) under an affine mapping (x,y)(ax+by+e, cx+dy+f). Two rows of edit controls give you a direct access to the values of a,b,e (the first row) and c,d,f (the second row.) Beware: the coordinate system is the usual one for computer graphics: the Y axis grows downwards.

Using parallelograms to define affine transformations may be a mixed blessing. For one, parallelograms may not resemble the resulting sets in the least. Even overlapping parallelograms may sometimes lead to a perfect tiling of the resulting set (see Sierpinski 2). Further, two parallelograms can be mapped onto each other in 8 different ways. (Pick a vertex as the origin and the order of the two adjacent vertices.) So, while a parallelogram remains the same geometric region, it can be associated with several transformations. Each such selection leads to a different IFS with a different fixed point. Bring up the second window and compare the Twindragon, Dragon, Monster, and Surprise IFSs. They all start with the same regions. But Iterate and watch the deterministic algorithm at work.

References

1. M.Barnsley, Fractals Everywhere, Academic Press, 1988
2. Chaos and Fractals, R.L.Devaney and L.Keen (eds), AMS, 1989
3. D.M.Davis, The Nature and Power of Mathematics, Princeton University Press, 1993
4. P.Hilton, D.Holton, J.Pederson, Mathematical Reflections, Springer Verlag, 1997
5. The Science of Fractal Images, H.-O.Peitgen and D.Daupe (eds), Springer-Verlag, 1988

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com

Copyright © 1997 Alexander Bogomolny