Iterated functions


Martin McBride, 2020-10-28
Tags iterated function system ifs
Categories generativepy generative art

Many fractals are based on the idea of an iterated function. In this article we will look at what an iterated function is. Here are some articles that explore well known fractals that can be craeted in ths way with generativepy:

Iterated functions

The idea on an iterated function is quite simple. Let's illustrate it with the function:

xnext = x * 2

If we start with a value x of 1, and apply the function, we get a value xnext of 2.

To iterate this function, we take the previous result, 2, and feed it back into the equation as x. This gives us a new xnext value of 4.

If we iterate again we will get a value of 8, the n 16, then 32, and so on. On each iteration, the value gets exponentially bigger, without bounds.

Here is some Python code to illustrate an iterated function:

x = 1
for i in range(10):
    xnext = x * 2
    x = xnext

This iterates the function 10 times. We don't really need the variable xnext, we can simply do this (the result will be the same):

x = 1
for i in range(10):
    x = x * 2

Different equations give different behaviours. In the one above the value grows larger and larger. If we tried the function x * 0.5, starting with a value of 1 we would get the sequence 0.5, 0.25, 0.125 etc. The value gradually decreases towards 0 (but never actually reaches 0). This value is bounded, all the values are in the range 0 to 1.

The equation x * -1 gives another different behaviour. Starting from 1 we would et the sequence -1, 1, -1, 1 etc. The value alternates between 1 and -1.

Iterated functions in 2 dimensions

Many fractals use iterated functions in two dimensions. Here is an example:

xnext = 1.4*x*x + y - 1
ynext = 0.3*x

From a starting value (x, y), the equations calculate new values (xnext, ynext). This values can be fed back into the equations iteratively to craete a sequence of (x, y) values, as in this loop:

x = 1
y = 1
for i in range(10):
    xnext = 1.4*x*x + y - 1
    ynext = 0.3*x
    x = xnext
    y = ynext

Notice that it is important that we calculate xnext and ynext before we change either x or y. We can't do this:

x = 1
y = 1
for i in range(10):
    x = 1.4*x*x + y - 1  # WRONG!!!
    y= 0.3*x

This won't work because we are changing the value of x before we have calculated y. But we can use this neat bit of Python syntax to avoid using temporary variables:

x = 1
y = 1
for i in range(10):
    x, y = 1.4*x*x + y - 1, 0.3*x

With this code, the values 1.4*x*x + y - 1 and 0.3*x are calculated first, and packed into a tuple. The assignment then unpacks the tuple and puts the values into x and y. This means that both calculations are done before x and y are updated.

Fractals based on iterated functions

There are several ways that a 2D iterated function can be used to create a fractal.

  • In some cases a sequence of points can be joined to form a curve. For example, in the Lorenz Attractor, the points form a curve that goes round and round in a double loop (a little like a figure of 8). But despite the equations being quite simple, the exact curve is always slightly different each time round.
  • In many cases each iteration creates a value (x, y) that is in an almost a random place compared to the previous value. Rather than joining the points, we simply place a small dot at each point that occurs. After plotting thousands of points, we see that the points aren't completely random, but actually form interesting and often beautiful patterns - these are called strange attractors. The equations above create the Henon Attractor and the King's Dream attractor but there are many other fractals of this kind.
  • For some fractals, we aren't concerned with the actual values of (x, y), we only care about whether the value is bounded or unbounded (that is, do x and y stay small forever, or do they grow to huge values). We create a map based on the initial conditions, and the number of iterations before the values exceed some value. These are called escape-time fractals and the famous Mandelbrot Set is an example.

Iterated function systems

An iterated function system (IFS) is a another type of fractal created when the functions of x and y from an affine transformation.

An affine transformation is a way to transform one set of (x, y) coordinates onto another. Starting with out initial coordinate space, we can translate the space, rotate it, scale it to be larger of smaller, flip it over, or skew it, or any combination of those things. That is called an affine transformation.

In an IFS we use two or more different affine transformations and do the following:

  1. Pick a random point.
  2. Apply one of the transforms, at random to get the next point.
  3. Repeat step 2 a fixed number of times.
  4. Plot the final point.

We do this procedure thousands of times, using a random start point each time, and the resulting distribution of points will create a shape.

The useful thing about an IFS is that we can use a technique called the collage theorem to actually design a set of affine transformations that will create a specific fractal shape.

Copyright (c) Axlesoft Ltd 2020