In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. 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 the Sierpiński triangle. 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, an iterated function system is a finite set of contraction mappings on a complete metric space. Symbolically,
{ f i : X → X ∣ i = 1 , 2 , … , N } , N ∈ N {\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }
is an iterated function system if each fi is a contraction on the complete metric space X.
Properties
Hutchinson showed that, for the metric space ℝn, or more generally, for a complete metric space X {\displaystyle X} , such a system of functions has a unique nonempty compact (closed and bounded) fixed set S. One way of constructing a fixed set is to start with an initial nonempty closed and bounded set S0 and iterate the actions of the fi, taking Sn+1 to be the union of the images of Sn under the fi; then taking S to be the closure of the limit limn→∞ Sn. Symbolically, the unique fixed (nonempty compact) set S ⊆ X has the property
S = ⋃ i = 1 N f i ( S ) ¯ . {\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.}
The set S is thus the fixed set of the Hutchinson operator F : 2X → 2X defined for A ⊆ X via
F ( A ) = ⋃ i = 1 N f i ( A ) ¯ . {\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.}
The existence and uniqueness of S is a consequence of the contraction mapping principle, as is the fact that
lim n → ∞ F n ( A ) = S {\displaystyle \lim _{n\to \infty }F^{n}(A)=S}
for any nonempty compact set A in X. (For contractive IFS this convergence takes place even for any nonempty closed bounded set A). Random elements arbitrarily close to S 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 in X) can yield attractors. These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too. The collection of functions fi generates a monoid under composition. 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
Sometimes each function fi 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 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.
Partitioned iterated function systems PIFS (partitioned iterated function systems), also called local iterated function systems, give surprisingly good image compression, even for photographs that do not seem to have the kinds of self-similar structure shown by simple IFS fractals.
The inverse problem
… excerpt ends here. Continue reading the full article.
