Fractals for beginners

People often talk about ‘mathematical beauty’. Most of the time I find these conversations boring, pretentious and completely inaccessible to anyone without a mathematical background. Type ‘mathematical beauty’ into google and you’ll get tonnes of results related to Euler’s Identity.

Whether you’re a mathematician or not, it’s just a formula. That’s not beautiful – it’s boring! How about something that actually looks nice? Something that’s generated by a simple process? Something that anyone can understand?

 

What are fractals?

Imagine taking a tree of broccoli and breaking off one of the ‘branches’. It looks like a mini version of the original tree. Break one of the ‘sub branches’ off the branch. It looks like a ‘mini mini’ version of the tree.

That’s all a fractal is – something which you can carry on zooming into and always seeing repeated patterns. However much you zoom in, you never lose detail. Definitions don’t really do justice to the subject – the best way to explain fractals is with pictures -continue reading.

Fractals are a family of shapes which I feel actually qualify as beautiful. Many of them meet the three criteria above:

  • They look incredible. Trees, snowflakes, coastlines, rivers….fractal-like patterns are found all over nature.
  • The three I will study in this post are incredibly easy to generate. Two of them are generated by a single formula and one uses an algorithm a child could follow.
  • There are tonnes of articles about the fractals I will discuss here. Few of them explain where they actually come from in terms anyone can understand. I’ll try to do that here.

The ‘catch’ is that you need a computer to draw fractals in a way where we can appreciate them since they have infinite detail. This post does discuss the programs I wrote but in a manner for beginners to coding (they are very simple programs). The programming side of this post can be ignored for those not interested.

The Sierpinski Gasket

Ignore the weird name, this is one of the easiest fractals to draw. There are many ways to construct it but the simplest can actually be done by hand with a pen and ruler in a day. Here’s how to do it:

chaos game

How to draw the Sierpinski gasket. Once step 4 is reached, we just repeat steps 3 and 4 many times until a pattern emerges.

Why do it by hand when we can just tell a computer to pick the random vertices and plot the points. A computer can do thousands of points per second. Here’s what we get if we plot one million points using the above rules:

results

The Sierpinski Gasket. Plotted using a simple program in R with one million points.

Awesome! The simple procedure above gives that cool pattern if repeated enough times.

A point to stress here is the pattern never ‘ends’. If we keep increasing the number of dots we plot, we can carry on zooming in and the pattern will repeat forever. In other words, it’s a fractal.

 

The Bifurcation Diagram of the Logistic Map

It’s like there’s an unwritten rule somewhere that fractals have to have really complicated names. Again, let’s ignore the name and just dive right in.

There is some maths here but I’ll go through it slowly. It’s nothing you haven’t done already at high school.

  1. Imagine we have a population (ie a number) of animals. Let’s say there is a maximum possible population. Our population is some proportion of the maximum possible population. Let’s call this proportion x.
  2. Over time, we know that x will change due to reproduction and deaths. Every generation we get a new value of x. So we could say right now x=xcurrent. At the next generation we will have xnew.
  3. Let’s pick a number, rThis decides how fast x grows or shrinks.
  4. Now let’s assume the population for the next generation is given by this formula:

xnew=r * xcurrent*(1-xcurrent)

That’s essentially it. Don’t worry where the formula comes from – it was basically just a guess at how to model the population. Note how simple this formula is. It’s hard to imagine anything particularly interesting coming from it.

The next concept we need to get comfortable with is iteration. We can use the above formula to predict the population after 1 generation. How about after 20 generations? Easy, we just re-apply the formula 20 times but we use the value xnew (ie the output) as the value of xcurrent (ie the input) for the next step. We simply repeatedly feed the result back into the formula repeatedly. Let’s do the first 3 iterations for r=3.5 and xcurrent=0.5 to make sure we understand:

  • Iteration 1    xnew=3.5*0.5*(1-0.5)
    •  xnew=0.875…feed this back into the formula:
  • iteration 2    xnew=3.5*0.875*(1-0.875)
    • xnew=0.383…feed this back into the formula:
  • iteration 3    xnew=3.5*0.383*(1-0.383)
    • xnew=0.827….

Simple. It’s still hard to see how anything interesting can come of this though.

Let’s choose r to be 3, and the starting value of x to be 0.5. If we iterate the formula, it soon give the same result every iteration. In other words, the population reaches a steady state and doesn’t change over time. Let’s plot that point:

r=3

The value of x for r=3. x settles to a value of about 0.78 regardless of how many iterations are performed.

Now let’s increase r by 0.001 each time and see what value x takes with 20 iterations for each value of r:

several r values

value of x for several closely spaced values of r

This is still boring. As we increase r, the steady state value of x isn’t changing much. This is pretty much what we’d expect. Why would a small change in r cause x to change much.

OK, let’s try r=3.8 and r=3.801:

bifurcation r 3.8bifurcation r3.001

steady state value of x for r=3.800 (left) and r=3.801 (right)

That’s unexpected. We changed r by just 0.001 and x has completely changed. How could such a small change in r lead to such a large change in x?

Chaos theory side note

What’s happening here is a classic example of ‘chaos theory’. This is where a small change in initial conditions leads to a major change in the eventual outcome. The classic example is weather forecasting – it becomes nearly impossible to predict the weather more than a few day in advance because only a tiny change in the current conditions is needed to completely change the weather a few days later. Chaos theory and fractals are often linked but that’s for another post.

Look back at the three iterations we did for r=3.5. See how the value of xnew was starting to settle between 2 values? It turns out the formula we are using doesn’t necessarily settle on a single population. For different values of r it can settle on multiple populations.That means for a given number of iterations,  a tiny change in r can radically alter the final population after a given number of generations (ie iterations). Let’s plot a dot for each value of r from 2.5 to 4, increasing r by 0.001 each time:

Remember – this plot is a series of dots. It is not a line plot. This is one of the biggest sources of confusion for this plot.

bifurcation frames gif

value of x for increasing values of r

Wow. Let’s take a closer look at the final image:

result plot

The bifurcation diagram of the logistic map. We can see where the name comes from – ‘bifurcate’ means to split in two. The ‘logistic map’ is just the formula we used.

Well this certainly is interesting. Let’s go through things step by step:

  1. We started with r=2.5. As r increases, the value of x increases slightly.
  2. When r=3, the value of x begins to oscillate between two values. Only a tiny change in r is necessary to cause an oscillation.
  3. As r continues to increase, the value of x oscillates between 4, then 8 then 16 values…the number of possible steady state values of x doubles as r increases.
  4. As r continues to increase, things become chaotic. There is little discernible pattern.
  5. However, in this chaotic section (between r=3.6 and r=4) there are zones where the behavior becomes predictable again – with x oscillating between a few values.

Crucially, look at some of the ‘zones of predictability’ between r=3.6 and r=4. There are tiny copies of the entire plot in there. Given enough points, we could zoom in on these and see further tiny copies. In other words….it’s a fractal.

Let’s take a second to reflect. We just used this dead simple formula:

x=r*x*(1-x)

many times with many values of r. It gave us the infinitely complex plot above, which contains infinitely many copies of itself. This is why mathematicians get excited by fractals.

Still bored? Let’s pull out the big guns…

The Mandelbrot Set

The name of this one isn’t quite as scary. It’s named after its discoverer ‘Benoit B Mandelbrot’ who is really the father of fractals. He also holds the brilliant distinction of having a fractal name – the ‘B’ stood for ‘Benoit B Mandelbrot’ (think about it!).

There are a number of ways to generate the Mandelbrot Set but they all use the same formula. We’ll be using one called the ‘escape time method’.

I said I’m writing this post for those without a lot of maths experience. So, I’m going to do the method two ways. The first just uses normal arithmetic that everyone is used to. But, it is actually more difficult to do that way. The second required ‘complex numbers’ – don’t worry I’ll explain them (they aren’t very complex at all), but is really simple once we know how to use them.

The two methods are actually identical but we’ll worry about that at the end.

 

Method 1 – using just real numbers

As I said, this method uses just regular arithmetic. But there are a lot of steps. If you get lost, I suggest just skipping to method 2.

Let’s just go ahead and go through the step by step guide.

  1. Draw a grid and label each point on the grid with x and y coordinates. The minimum value of x and y is -2; the maximum value of x and y is 2. So, the centre of the grid is at point 0,0.
  2. Take a point (x,y) on the grid. Give the point a value ‘z’, which is actually a coordinate. The value of z always starts of as 0,0.
  3. Calculate ‘c’ for the point. c is calculated by applying the following formula to the x and y coordinates:  c=sqrt(x^2 + y^2)
  4. If c is larger than 2, colour the point in.
  5. If c is not larger than 2, recalculate z as follows. The new value of x = (x^2)-(y^2)+x. The new value of y = (2*x*y)+y.
  6. With this new value of z, repeat steps 3-5 until c is larger than 2, or until we have repeated the steps a predetermined number of times. The greater the number of times we need to make c larger than 2, the darker the colour we use to shade the point in.
  7. Repeat steps 2-6 for every point on the grid.

That’s it. You could in theory sit and do that by hand, although it would take years to get anything out that looked anything like a fractal. A computer will do it in seconds though.

Note in step 6, I stated we stop after a ‘predetermined number of times’. This is the number of iterations. Like in the logistic map, we decide a number of iterations before we begin. For the Mandelbrot set, 50 is easily sufficient to give us a detailed image without zooming.

So, what does it look like? Let’s look at the second method first. The above method is clumsy and doesn’t really give an idea how simple it is to generate the set.

 

Method 2 – use complex numbers

The above method isn’t the proper way of generating the set at all. I was using coordinates but imagine if we didn’t have to split ‘z’ up into x and y. Imagine if z could be represented as a single number, then the process would be much simpler.

It can, because in reality z is a complex number

 

Complex Numbers

For those not familiar, here is a crash course in complex numbers. They are sometimes called imaginary numbers. Both are stupid names because they are not imaginary, and they are not particularly complex either. They are generally taught very poorly at school/university level so people understandably get confused by them.

The clip below is my attempt at explaining what a complex number is:

 

If we replace the clumsy coordinates for each point in our grid with a complex number p, the process to generate the Mandelbrot set becomes incredibly simple:

  1. Draw the grid for -2<x<2  and  -2<y<2.
  2. Pick a point,p, on the grid, assign it a complex number z. Initially z= 0+0i
  3. Calculate c for the point where c=abs(p)
  4. If c is larger than 2, colour the point in.
  5. if c is less than 2, apply the formula z=(z^2)+c
  6. Repeat steps 3-5 until we have reached the predetermined number of iterations or until c is greater than 2.
  7. Repeat steps 3-6 for every point on the grid. The higher the number of iterations required to make c greater than 2, the darker the colour used to shade in the point.

So, the entire process is defined by a simple formula: z=(z^2)+c where c=abs(p)

Python deals with complex numbers no problem, so we just write a script using the above algorithm.

And what does this simple formula give us when iterated over the entire grid. Here is the result for 50 iterations over a 10000X10000 grid:

mandelbrotplot

My new desktop background – Mandelbrot set for 50 iterations. There is a link for the full sized image at the end of the post.

 

This picture doesn’t even start to do it justice. Let’s zoom in and take a closer look:

zoom png

Zooming in 10000 times to the Mandelbrot set. Note the details are limited here by the image size – these patterns are all infinitely complex regardless of the level of zoom.

The above series of images is still a pretty shoddy representation of how complex the set is. You can carry on zooming in forever and the patterns never get any less complex. Those blobs you can see are ‘mini Mandelbrot sets’, and they all contain the same infinite detail as the main set.

There are plenty other sites with zoomable Mandelbrot sets. There are also many youtube videos with incredibly deep zooms. I recommend you to go and have a look around. The complexity that arises from such a simple formula is amazing.

And finally, for anyone still not impressed by any of this:

mandelbrot bifurcation

I’ve never managed to get my head around why that happens.

 

My code

I did much of the code for this post whilst away from home.  Unfortunately my laptop does not have all the Python libraries I needed installed. So, I did the Sierpinski Gasket and the bifurcation diagram in R and the Mandelbrot set in Python. I will hopefully get round to uploading Python scripts for the other two in the future.

Note how few lines of code are necessary to generate the images!

Sierpinski Gasket. This uses just 14 lines of code including that to plot the image:

https://www.dropbox.com/s/5tk2og5t9rv5awi/working.R?dl=0

 

Bifurcation diagram. Just 6 lines of code necessary for this!:

https://www.dropbox.com/s/1vcry5euz0dk2kc/non%20recursive.R?dl=0

 

Mandelbrot set. 25 lines of code for this one. It i certainly possible to do it in less though :

https://www.dropbox.com/s/d6qzmeiz24xb8nv/complex%20numbers%20version.py?dl=0

 

 

Advertisements

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