Iterated function systems or IFSs are a method of constructing fractals which were conceived in their present form by John Hutchinson in 1981 and popularized by Michael Barnsley's book Fractals Everywhere.

IFS fractals as they are normally called can be of any number of dimensions, but are commonly computed and drawn in 2D. An IFS fractal is a solution to a recursive set equation. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the Sierpinski gasket. The functions are normally contractive which means they bring points closer together and make shapes smaller. Hence the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, ad infinitum. This is the source of its self-similar fractal nature.

Formally, $S\; =\; \backslash bigcup\_i\; f\_i(S)$ where $S\; \backslash subset\; \backslash mathbb\{R\}^n$ and $f\_i:\backslash mathbb\{R\}^n\backslash to\backslash mathbb\{R\}^n.$

Sometimes each function $f\_i$ is required to be linear, or more accurately an affine transformation and hence can be represented by a matrix. However, IFSs may also be built from non-linear functions, including projective transformations and Möbius transformations.

The most common algorithm to compute IFS fractals is called the chaos game. It consists of picking a random point in the plane, then iteratively applying one of the functions chosen at random from the function system and drawing the point. An alternative algorithm is to generate each possible sequence of functions up to a given maximum length, and then to plot the results of applying each of these sequences of functions to an initial point or shape.

Both of these algorithms generate the whole fractal, even the parts that are outside of the screen boundaries. Hence unlike the more common Mandelbrot fractals, you cannot easily zoom into most IFS fractals.

Example: Computation of a fractal "fern" using an iterated function system

Here is an example of a fern-like image computed using an Iterated function system

The first point drawn is at the origin (x₀=0, y₀=0) and then the new points are iteratively computed by randomly applying one of the following 4 coordinate transformations:

x_n+1=0
y_n+1=0.16 y_n
This coordinate transformation is chosen 1% of the time and maps any point to a point in the line segment shown in green in the figure.

x_n+1=0.2 x_n-0.26 y_n
y_n+1=0.23 x_n+0.22 y_n+1.6
This coordinate transformation is chosen 7% of the time and maps any point inside the black rectangle to a point inside the red rectangle in the figure.

x_n+1=-0.15 x_n+0.28 y_n
y_n+1=0.26 x_n+0.24 y_n+0.44
This coordinate transformation is chosen 7% of the time and maps any point inside the black rectangle to a point inside the dark blue rectangle in the figure.

x_n+1=0.85 x_n+0.04 y_n
y_n+1=-0.04 x_n+0.85 y_n+1.6
This coordinate transformation is chosen 85% of the time and maps any point inside the black rectangle to a point inside the light blue rectangle in the figure.

The first coordinate transformation draws the stem. The second draws the bottom frond on the left. The third draws the bottom frond on the right. The fourth generates successive copies of the stem and bottom fronds to make the complete fern. The recursive nature of the IFS guarantees that the whole is a larger replica of each frond.

See also

• L-system
• Fractal compression
• Fractal flame

External links

• A definition of IFS and a Java illustration with several built-in examples at cut-the-knot
• Interactive 3D fractal polyhedra in Java
• Xenodream - a 3d IFS modeling program
• IFS Fractal fern and Sierpinski triangle - JAVA applet
• The Fractal Flame Algorithm

Fractals

Iteriertes Funktionensystem | Iteratitaj sistemoj de funkcioj | Système de fonctions itérées | Itererande funktionssystem