Iterated Function System
Introduction
An Iterated Function System (IFS) is a method used in mathematics to construct fractals; the resulting fractals are often self-similar. IFS fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractals are made up of copies of a basic shape, each copy being transformed by a function (hence "function system"). The canonical example is the Sierpinski triangle.
Mathematical Definition
An Iterated Function System is defined by a finite set of contraction mappings \(w_i: X \rightarrow X\), where \(X\) is a complete metric space. Each mapping \(w_i\) is associated with a probability \(p_i\), such that \(\sum_{i=1}^{N} p_i = 1\). The probabilities \(p_i\) may be used to define a random iteration algorithm, which in turn can be used to generate fractals.
Contraction Mappings
A contraction mapping, or contraction, on a metric space \(X\) is a function \(f: X \rightarrow X\) such that there exists a real number \(k < 1\) called the Lipschitz constant of \(f\), where for all \(x\) and \(y\) in \(X\), the distance \(d(f(x), f(y))\) is at most \(k\) times the distance \(d(x, y)\).
Fractals and Self-Similarity
In the context of IFS, a fractal is a detailed, infinitely self-similar set. Self-similarity in this context means that the whole has the same shape as one or more of the parts, when magnified. Fractals can be deterministic (all the functions \(w_i\) are deterministic) or random (each function \(w_i\) is chosen randomly with a probability \(p_i\)).
Random Iteration Algorithm
The random iteration algorithm (also known as the chaos game) is an algorithm for creating a sequence of points in a metric space, based on the functions of an IFS and their associated probabilities. The algorithm is as follows:
1. Choose an initial point \(x_0\) in \(X\). 2. For \(n = 1, 2, 3, \ldots\), choose a function \(w_i\) randomly, with probability \(p_i\), and let \(x_n = w_i(x_{n-1})\).
The sequence \(x_0, x_1, x_2, \ldots\) is often visualized by plotting the points in \(X\).
Applications
Iterated Function Systems have been used in a variety of fields. In computer graphics, they are used to generate fractals, which are used in turn for procedural textures, image compression, and in the generation of special effects. In mathematics, they are used to construct fractals and to study the properties of such fractals.