# Iterated function system

﻿
Iterated function system

In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always 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 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.

Definition

Formally,

:

where

:$S subset mathbb\left\{R\right\}^n,$

and

:$f_i:mathbb\left\{R\right\}^n omathbb\left\{R\right\}^n.$

are contraction mappings.The set "S" is thus the fixed set of a Hutchinson operator, which is the union of the functions $f_i$.

Properties

Hutchinson (1981) showed that such a system of functions has a unique compact (closed and bounded) fixed set "S". One way of constructing a fixed set is to start with an initial point or set "S"0 and iterate the actions of the "f""i", taking "S""n"+1 to be the union of the image of "S"n under the "f"i ; then taking "S" to be the closure of the union of the "S""n". Random elements of "S" may be obtained by the "chaos game" below.

The collection of functions $f_i$ together with composition form a monoid. If there are only two such functions, the monoid can be visualized as a binary tree, where, at each node of the tree, one may compose with the one or the other function ("i.e" take the left or the right branch). In general, if there are "k" functions, then one may visualize the monoid as a full k-ary tree, also known as a Cayley tree.

Constructions

[
thumb|right|250px|Construction_of_an_IFS_by_the_chaos game] Sometimes each function $f_i$ is required to be a linear,or more generally an affine transformation and hence represented by a matrix. However, IFSs may also be built from non-linear functions, including projective transformations and Möbius transformations. The Fractal flame is an example of an IFS with nonlinear functions.

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.

Each of these algorithms provides a global construction which generates points distributed across the whole fractal. If a small area of the fractal is being drawn, many of these points will fall outside of the screen boundaries. This makes zooming into an IFS construction normally impractical.

Although the theory of IFS requires each function to be contractive, in practice software that implements IFS only require that the whole system be contractive on average [ cite web | last=Draves | first=Scott | authorlink=Scott Draves | coauthors=Erik Reckase | date=July 2007 | url=http://flam3.com/flame.pdf | title=The Fractal Flame Algorithm | format=pdf | accessdate=2008-07-17 ] .

Example: a fractal "fern"

Here is an example of a fern-like image (Barnsley's fern) computed using an iterated function system.

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

1.:"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.

2.:"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.

3.:"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.

4.:"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. Note: The fern is within the range -2.1818 <= x <= 2.6556 and 0 <= y <= 9.95851.

Example

The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the Hutchinson operator. Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal.

Early examples of fractals which may be generated by an IFS include the Cantor set, first described in 1884; and de Rham curves, a type of self-similar curve described by Georges de Rham in 1957.

History

IFS were conceived in their present form by John Hutchinson in 1981 and popularized by Michael Barnsley's book "Fractals Everywhere".

References

*
*
*

ee also

* L-system
* Fractal compression
* Fractal flame
* Complex base systems

* [http://www.cut-the-knot.org/ctk/ifs.shtml A definition of IFS and a Java illustration with several built-in examples] at cut-the-knot

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Iterated function — In mathematics, iterated functions are the objects of deep study in computer science, fractals and dynamical systems. An iterated function is a function which is composed with itself, repeatedly, a process called iteration.DefinitionThe formal… …   Wikipedia

• Function composition — For function composition in computer science, see function composition (computer science). g ∘ f, the composition of f and g. For example, (g ∘ f)(c) = #. In mathematics, function composition is the application of one function to the resul …   Wikipedia

• L-system — An L system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a …   Wikipedia

• Refinable function — In mathematics, in the area of wavelet analysis, a refinable function is a function which fulfills some kind of self similarity. A function varphi is called refinable with respect to the mask h if:varphi(x)=2cdotsum {k=0}^{N 1} h… …   Wikipedia

• Inverse function — In mathematics, if fnof; is a function from A to B then an inverse function for fnof; is a function in the opposite direction, from B to A , with the property that a round trip (a composition) from A to B to A (or from B to A to B ) returns each… …   Wikipedia

• Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia

• Error function — Plot of the error function In mathematics, the error function (also called the Gauss error function) is a special function (non elementary) of sigmoid shape which occurs in probability, statistics and partial differential equations. It is defined …   Wikipedia

• Measure-preserving dynamical system — In mathematics, a measure preserving dynamical system is an object of study in the abstract formulation of dynamical systems, and ergodic theory in particular. Contents 1 Definition 2 Examples 3 Homomorphisms 4 …   Wikipedia

• Cryptographic hash function — A cryptographic hash function (specifically, SHA 1) at work. Note that even small changes in the source input (here in the word over ) drastically change the resulting output, by the so called avalanche effect. A cryptographic hash function is a… …   Wikipedia

• Fractal compression — is a lossy image compression method using fractals to achieve high levels of compression. The method is best suited for photographs of natural scenes (trees, mountains, ferns, clouds). The fractal compression technique relies on the fact that in… …   Wikipedia