Section 4.4 Applying iterated function systems
We turn now to the question of how to generate self-similar images. Ultimately, we will consider several algorithms for this purpose. It turns out they are all related to theoretical questions presented in the next chapter. For example, we will present a constructive proof that any IFS yields a unique closed, bounded invariant set. This construction is essentially our first algorithm, which we call the basic deterministic algorithm.
Given an iterated function system \(\left\{f_i\right\}_{i=1}^m,\) we can define a function \(T\) which maps the collection of closed, bounded subsets of \(\mathbb{R}^n\) to itself by
We can use the function \(T\) to generate the invariant set using iteration, an important theme in fractal geometry. To iterate a function \(f\) which maps a set \(X\) into itself, start with a some point \(x_0\) in \(X,\) set \(x_1 = f\left(x_0\right),\) and for larger natural numbers \(n\) set \(x_n = f\left(x_{n-1}\right).\) Equivalently, we can write \(x_n = f^n\left(x_0\right),\) the result of \(n\)-fold composition of \(f\) applied to \(x_0.\) In the current situation, the set \(X\) is the set of all non-empty, closed, bounded subsets of \(\mathbb{R}^n\) and the function is the transformation \(T\) defined in equation (4.4.1). It turns out that if we start with an arbitrary non-empty, closed, bounded subset of \(\mathbb{R}^n\) and iterate the function \(T,\) then the generated sequence of sets converges in a natural sense to the invariant set of the IFS. We’ll examine this statement more carefully in the next chapter, but in this chapter we’ll demonstrate the statement visually through experimentation.
Figure Figure 4.2.1, for example, was generated in exactly the manner described above. The initial set \(F\) was taken to be the solid equilateral triangle with vertices \((0,0), (1,0),\) and \(\left(1/2,\left.\sqrt{3}\right/2\right).\) The transformation \(T\) is obtained by applying equation (4.4.1) to the Sierpinski IFS. The subsequent images correspond to application of \(T\) up to 5 times.
The previous example might be misleading, since the relationship between the initial approximation and the fractal attractor is so close. Indeed, the choice of initial approximation has no effect on the final attractor, although the images illustrating convergence can be affected. Figure Figure 4.4.1, for example, illustrates the sequence of sets generated by applying this same IFS to the initial approximation consisting of the single point at the origin. Successive approximations fill the set out more and more completely. Figure Figure 4.4.2 illustrates the algorithm taking the initial set to be the shape from figure Figure 4.3.4.
The point of this demonstration bears repeating: the iterated function system determines the self-similar set and the initial approximation has no effect on the final outcome.