Last edited 12mar03 by andy schwieter
Find this document at http://www.ncsa.uiuc.edu/Classes/MATH198/schwietr
Jump to public
Jump to quarterly report.
Jump to abstract.
Andy Schwieter's Endeavor into Fractals
Abstract
Fractals can be generated in many different ways, one of which is the iterated function system (IFS). There are two main methods of drawing the attractor of the IFS, the fractal: the deterministic algorithm and the random iteration algorithm. I use the somewhat more computation intensive deterministic algorithm in my program. With it, many common fractals can be drawn from a small amount of information, usually 24 or less numbers.
It can be proven that if two IFS's have values "close" to each other, then their attractors (fractals) are also "close" to each other. I have programs which demonstrate this by transforming one well-known fractal, such as the Sierpinski Gasket, Barnsley's fern, or the tree, into another in a given number of steps.
The knowledgeable programmer could, with relative ease, use my algorithm to create fractals in three dimensions, such as the tetrahedral analog to the Sierpinski Gasket. Unfortunately, I am currently unable to do this. Also, one could vary the speed with which the fractals are drawn so as to better show the process of their creation.
Narrative
Fractals can be generated in many different ways, one of which is the iterated function system (IFS). An IFS is a finite set of contraction mappings on a vector space, in my case R2. More specifically, the contraction maps I use are also affine transformations (the composition of a linear transformation and a translation). It can be proven that any contraction map on a compact set has a fixed point, generally referred to as an attractor. This attractor is what is commonly referred to as the fractal of the IFS.
There are two main methods of drawing the attractor of the IFS: the deterministic algorithm and the random iteration algorithm. The deterministic algorithm is a simpler, more straightforward method of visualizing the fractal. It uses the notion that a sequence xn+1=f(xn) formed by a contraction map f necessarily converges to the attractor. Basically, it takes a set of points S and applies the IFS f repeatedly, Sn+1=f(Sn), displaying either each S or simply waiting until n is sufficiently large and displaying Sn. The random iteration algorithm, on the other hand, uses a more sophisticated notion, sometimes called the chaos game. It begins with a single point, then chooses, based on given probabilities, one of the functions of the IFS to apply to it. The resulting point is used as the next input point, and the iterative process continues. Slowly, the form of the attractor appears out of the scattering of points. One complication of this method is choosing the probability distribution. Barnsley states pn is approximately equal to the determinant of An (where An is the matrix of the linear transformation associated with fn) divided by the sum of the determinants of An for 0 < n < N+1, where N is the total number of functions in the IFS. This approximately equal to leads to problems in determining exactly what the attractor looks like using this method, yet it is much less computational than the deterministic algorithm.
In my program, I use the deterministic algorithm in spite of its computational intensity. This allows me to avoid the problem of choosing appropriate probabilities for the IFS's, but also affords a better view of what is actually happening. If one were to slow down my algorithm so that the fractal was drawn step by step, the different transformations involved can actually be seen.
Michael Barnsley, the pioneer of drawing fractals with IFS's, in his book Fractals Everywhere proved that if two IFS's have values "close" to each other, then their attractors (fractals) are also "close" to each other. This means that one can slowly change a fractal by slowly changing the IFS which creates it. Another implication is that one can smoothly change one fractal into another. I have programs which demonstrate this by transforming one well-known fractal, such as the Sierpinski Gasket, Barnsley's fern, or the tree, into another in a given number of steps.
The knowledgeable programmer could, with relative ease, use my algorithm to create fractals in three dimensions, such as the tetrahedral analog to the Sierpinski Gasket. Unfortunately, I am currently unable to do this. Also, one could vary the speed with which the fractals are drawn so as to better show the process of their creation.