Concept

Iterated function system

Summary
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. Formally, an iterated function system is a finite set of contraction mappings on a complete metric space. Symbolically, is an iterated function system if each is a contraction on the complete metric space . Hutchinson showed that, for the metric space , or more generally, for a complete metric space , 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 . Symbolically, the unique fixed (nonempty compact) set has the property The set S is thus the fixed set of the Hutchinson operator defined for via The existence and uniqueness of S is a consequence of the contraction mapping principle, as is the fact that for any nonempty compact set in . (For contractive IFS this convergence takes place even for any nonempty closed bounded set ). 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.