Inmathematics,iterated function systems (IFSs) are a method of constructingfractals; the resulting fractals are oftenself-similar. IFS fractals are more related toset theory than fractal geometry.^[1] They were introduced in 1981.

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 theSierpiński triangle. The functions are normallycontractive, 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, aniterated function system is a finite set ofcontraction mappings on acomplete metric space.^[2] Symbolically,

${\displaystyle \{f_i:X\to X\mid i=1,2,\dots ,N\},N\in \mathbb{N}}$

is an iterated function system if each${\displaystyle f_i}$ is a contraction on the complete metric space${\displaystyle X}$.

Hutchinson showed that, for the metric space${\displaystyle {\mathbb{R}}^n}$, or more generally, for a complete metric space${\displaystyle X}$, such a system of functions has a unique nonemptycompact (closed and bounded) fixed setS.^[3] One way of constructing a fixed set is to start with an initial nonempty closed and bounded setS₀ and iterate the actions of thef_i, takingS_n+1 to be the union of the images ofS_n under thef_i; then takingS to be theclosure of the limit${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{S}_n}$. Symbolically, the unique fixed (nonempty compact) set${\displaystyle S\subseteq X}$ has the property

${\displaystyle S=\overline{\bigcup _{i=1}^N{f}_i(S)}.}$

The setS is thus the fixed set of theHutchinson operator${\displaystyle F:2^X\to 2^X}$ defined for${\displaystyle A\subseteq X}$ via

${\displaystyle F(A)=\overline{\bigcup _{i=1}^N{f}_i(A)}.}$

The existence and uniqueness ofS is a consequence of thecontraction mapping principle, as is the fact that

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{F}^n(A)=S}$

for any nonempty compact set${\displaystyle A}$ in${\displaystyle X}$. (For contractive IFS this convergence takes place even for any nonempty closed bounded set${\displaystyle A}$). Random elements arbitrarily close toS may be obtained by the "chaos game," described below.

Recently it was shown that the IFSs of non-contractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric inX) can yield attractors.These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.^[4]

The collection of functions${\displaystyle f_i}$generates amonoid undercomposition. If there are only two such functions, the monoid can be visualized as abinary 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 arek functions, then one may visualize the monoid as a fullk-ary tree, also known as aCayley tree.

Sometimes each function${\displaystyle f_i}$ is required to be alinear, or more generally anaffine, transformation, and hence represented by amatrix. However, IFSs may also be built from non-linear functions, includingprojective transformations andMöbius transformations. TheFractal 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 to transform the point to get a next 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 drawn in this manner 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.^[5]

PIFS (partitioned iterated function systems), also called local iterated function systems,^[6] give surprisingly good image compression, even for photographs that don't seem to have the kinds of self-similar structure shown by simple IFS fractals.^[7]

Very fast algorithms exist to generate an image from a set of IFS or PIFS parameters. It is faster and requires much less storage space to store a description of how it was created, transmit that description to a destination device, and regenerate that image anew on the destination device, than to store and transmit the color of each pixel in the image.^[6]

Theinverse problem is more difficult: given some original arbitrary digital image such as a digital photograph, try to find a set of IFS parameters which, when evaluated by iteration, produces another image visually similar to the original.In 1989, Arnaud Jacquin presented a solution to a restricted form of the inverse problem using only PIFS; the general form of the inverse problem remains unsolved.^[8][9][6]

As of 1995, allfractal compression software is based on Jacquin's approach.^[9]

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 theHutchinson 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 theCantor set, first described in 1884; andde Rham curves, a type of self-similar curve described byGeorges de Rham in 1957.

IFSs were conceived in their present form byJohn E. Hutchinson in 1981^[3] and popularized byMichael Barnsley's bookFractals Everywhere.

IFSs provide models for certain plants, leaves, and ferns, by virtue of the self-similarity which often occurs in branching structures in nature.

• Complex-base system
• Collage theorem
• Infinite compositions of analytic functions
• L-system
• Fractal compression

• Draves, Scott; Erik Reckase (July 2007)."The Fractal Flame Algorithm"(PDF). Archived fromthe original(PDF) on 2008-05-09. Retrieved2008-07-17.
• Falconer, Kenneth (1990).Fractal geometry: Mathematical foundations and applications. John Wiley and Sons. pp. 113–117, 136.ISBN 0-471-92287-0.
• Barnsley, Michael; Andrew Vince (2011). "The Chaos Game on a General Iterated Function System".Ergodic Theory Dynam. Systems.31 (4):1073–1079.arXiv:1005.0322.Bibcode:2010arXiv1005.0322B.doi:10.1017/S0143385710000428.S2CID 122674315.
• For an historical overview, and the generalization :David, Claire (2019)."fractal properties of Weierstrass-type functions".Proceedings of the International Geometry Center.12 (2):43–61.doi:10.15673/tmgc.v12i2.1485.S2CID 209964068.

• A Primer on the Elementary Theory of Infinite Compositions of Complex Functions

• Iterated function system fractals
• 1981 introductions

• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata