Fractals V: Iterated Function Systems I

So just what are fractals?

In this blog, we’ve looked at a few examples of fractals so far — the Koch snowflake, for example — and informally called images created by the same algorithm “fractal images.”   But what makes the Koch snowflake a fractal?

Regardless of which definition you find on the internet, you’ll find ideas about self-similarity which keeps being repeated at ever smaller scales.  Truly rigorous definitions require some truly advanced mathematics…but we’ll illustrate the idea with another classic fractal, the Sierpinski triangle.

Begin with any triangle, and then remove the triangle formed by connecting the midpoints of the sides, as shown below.

Sierp1

Now repeat — in each triangle, remove the triangle formed by connecting the midpoints of the sides.  Two more iterations results in the following image.

Sierp2.png

And five more iterations gives the Sierpinski triangle.

Sierp3

Of course, in a mathematical sense, this process goes on infinitely — you still keep getting triangles on each iteration, so you’re never done.  But as far as creating computer graphics is concerned, you can just stop when the iterations start looking the same.

The self-similarity of the Sierpinski triangle should now be fairly evident.  The way it’s constructed, you’ll notice that each of the three smaller triangles shown in the first iteration looks identical to the entire Sierpinski triangle, except that it’s shrunk by a factor of two along all dimensions.  This is self-similarity:  one can say that the Sierpinski triangle is, in a mathematical sense, built up of smaller copies of itself.

Now how can we describe this self-similarity?  Using affine transformations.  (If the notations and functions below aren’t familiar to you, study up on linear and affine transformations, and how you use matrices to represent them.)

First, we’ll color code parts of the Sierpinski triangle for easy reference.

Sierp4.png

Next, we’ll introduce a coordinate system.  Let the origin be the vertex of the right angle of the triangle, with the usual x– and y-axes.  If you apply the transformation

F_1\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}0.5&0\\0&0.5\end{matrix}\right] \left(\begin{matrix}x\\y\end{matrix}\right)

to the entire Sierpinski triangle, you get the red “shrunk by half” triangle at the right angle of the Sierpinski triangle.

Now if you apply the transformation

F_2\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}0.5&0\\0&0.5\end{matrix}\right] \left(\begin{matrix}x\\y\end{matrix}\right)+\left(\begin{matrix}1\\0\end{matrix}\right)

to the Sierpinski triangle, you’ll get the blue portion — shrunk by a factor of two, and moved over one unit.  Finally, if you apply the transformation

F_3\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}0.5&0\\0&0.5\end{matrix}\right] \left(\begin{matrix}x\\y\end{matrix}\right)+\left(\begin{matrix}0\\1\end{matrix}\right),

you’ll get the orange part, shrunk by a factor of two and moved up one unit.  (Note that the choice of moving one unit is arbitrary — you’ll get something that looks like the Sierpinski triangle as long as you move the same amount in each direction.)

What all this means is that the functions F_1, F_2, and F_3 mathematically describe the self-similarity of the Sierpinski triangle, and so they may be used to generate the Sierpinski triangle.  You can see where the term iterated function system comes from by thinking about using these functions iteratively to generate a fractal image.

Now here’s the amazing part.  If you look at the very first iteration we did, you’ll see three triangles, each representing one of these transformations.  So imagine beginning with a different object — say a unit square — and perform these three transformations; that is, shrink by half, shrink and move to the right, and shrink and move up.  You’ll get something like this:

Sierp21

After two more iterations, here is what you’ll see.

Sierp22

Notice the self-similarity.  If we keep going another six iterations, we get…

Sierp23

…the Sierpinski triangle again!

If you start out with a small circle, you get the following after five iterations.

Sierp31

What this means is that the Sierpinski triangle — in a very real, rigorously mathematical sense — is completely determined by the transformations which describe its self-similarity.  Yes, the final result is always a triangle, independent of what shape you start out with!  Filled squares, circles, whatever object you choose — the result will always be the Sierpinski triangle.

If you really want to know why, read Michael Barnsley’s Fractals Everywhere.  But be forewarned — you need to know a lot of mathematics to completely understand what’s going on.  But it really is amazing.

In order to create your own fractals, you don’t need to know all the mathematical details.  You just need to understand the nature of self-similarity, and how to represent it using affine transformations.

Another famous fractal is the Sierpinski carpet.

Carpet

You can see the self-similarity here as well.  Note that there are eight smaller, identical copies of the Sierpinski carpet which make up the fractal.  So you would need eight affine transformations, one of which would be

G\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}1/3&0\\0&1/3\end{matrix}\right] \left(\begin{matrix}x\\y\end{matrix}\right)+\left(\begin{matrix}1\\0\end{matrix}\right).

Notice that the scaling is only by a factor of 1/3 here, and that the choice of units to move is arbitrary (as with the Sierpinski triangle).  Further, it doesn’t matter what object you begin with — you’ll always end up with the Sierpinski carpet when your done.

Where do we go from here?  Next week, we’ll look at how different choices of affine transformations affect the fractal image.  For example, suppose we return to the Sierpinski triangle example, but replace F_1 with the transformation

F_1\left(\begin{matrix}x\\y\end{matrix}\right)=\left[\begin{matrix}0.25&0\\0&0.5\end{matrix}\right] \left(\begin{matrix}x\\y\end{matrix}\right).

How should this affect the fractal?  Look at the result, and see if you can figure it out.

NewSierp

Can you see the two identical copies, each shrunk by half, generated by F_2 and F_3?  But note that the copy at the right angle is actually shrunk by one-fourth along the x direction — but this is expected as a result of the scaling by 0.25 along the x direction in F_1.

In other words, when we change the description of the self-similarity (that is, when we change the affine transformations), we change what the fractal looks like — because, in a mathematical sense, the fractal is the set of affine transformations.  But here’s the difficult question — can you predict what the fractal will look like only by looking at the affine transformations?

Well, if you can, then you’re a lot better at this than I am!  It’s not an easy task — but it is what makes creating fractals fun.  Usually, you don’t know what the result will be.  That’s the adventure!  You often surprise yourself by what you discover.

In the next few posts, we’ll consider different types of affine transformations (like rotations, shears, etc.), and then discuss an algorithm which can generate approximations to fractals.  Stay tuned!

Two.png

P.S.  This fractal was created using only two affine transformations.  Next week we’ll see how.

Published by

Vince Matsko

Mathematician, educator, consultant, artist, puzzle designer, programmer, blogger, etc., etc. @cre8math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s