# Iterated function system

A family $\{ { {f _ {i} } : X \rightarrow X } : {i \in I } \}$ of mappings, where $( X, \rho )$ is a complete metric space. Usually, $I$ is a finite set, $I = \{ 1 \dots N \}$. An iterated function system is called hyperbolic if all $f _ {i}$ are contracting (cf. Contraction) for $i = 1 \dots N$. An iterated function system induces a mapping $F$ from the space $2 ^ {X}$ to itself by $F ( A ) = f _ {1} ( A ) \cup \dots \cup f _ {N} ( A )$. If the iterated function system is hyperbolic and one restricts $F$ to the space of non-empty closed bounded sets equipped with the Hausdorff metric, then it follows from the contracting-mapping principle that $F$ has a unique fixed point $K$; moreover, $K$ is compact ([a8], [a7]). The set $K$ is called the attractor, or invariant set, of the iterated function system. If $X$ is a Euclidean space and the $f _ {i}$ are similitudes, then the attractor is called a self-similar set. These sets are usually fractals (cf. Fractals); an example is the triadic Cantor set (cf. also Cantor set), which is the attractor of the iterated function system

$$\left \{ x \mapsto { \frac{1}{3} } x, x \mapsto { \frac{1}{3} } x + { \frac{2}{3} } \right \} .$$

A generalization is the concept of a recurrent self-similar (or mixed self-similar) set generated by a recurrent iterated function system. Let $M = ( m _ {ij } )$ be an $( N \times N )$- matrix of zeros and ones satisfying $M ^ {n} > 0$ for some $n > 0$, and let contracting mappings ${f _ {ij } } : X \rightarrow X$ be given for each $( i,j )$ such that $m _ {ij } = 1$. Then (see [a3] or [a1]) there is a unique vector $( K _ {1} \dots K _ {N} )$ of non-empty compact sets such that for $i = 1 \dots N$,

$$K _ {i} = \cup _ {\left \{ j : {m _ {ij } = 1 } \right \} } f _ {ij } ( K _ {j} ) .$$

An iterated function system with probabilities is an iterated function system $\{ f _ {1} \dots f _ {N} \}$ together with a probability vector $( p _ {1} \dots p _ {N} )$( i.e., $p _ {i} > 0$ and $p _ {1} + \dots + p _ {N} = 1$). This induces a mapping $G$ on the space of Borel probability measures by $G \mu ( B ) = \sum ^ {N} _ {i = 1 } p _ {i} \mu ( f _ {i} ^ {- 1 } B )$ for all Borel sets (cf. also Borel set) $B$. If the iterated function system is hyperbolic, then there is a unique fixed point $\nu$ for $G$, i.e. an invariant measure, whose topological support is the attractor of the iterated function system [a7]. Convergence to $\nu$ is also obtained by associating a random dynamical system with the iterated function system via the Markov chain $X _ {n + 1 } = f _ {Y _ {n} } ( X _ {n} )$, where the $( Y _ {n} )$ form a sequence of independent random variables with distributions ${\mathsf P} [ Y _ {n} = i ] = p _ {i}$[a2]. The same type of result holds for recurrent iterated function systems, taking for $( Y _ {n} )$ a Markov chain on $\{ 1 \dots N \}$ whose transition probabilities are positive if and only if the $m _ {ij }$ are positive [a3], [a4]. Iterated function systems are applied for approximation purposes (see, e.g., [a5]) and the construction of wavelets (see, e.g., [a6]).

#### References

 [a1] C. Bandt, "Self similar sets I. Topological Markov chains and mixed self-similar sets" Math. Nachr. , 142 (1989) pp. 107–123 [a2] M.F. Barnsley, D. Demko, "Iterated function systems and the global construction of fractals" Proc. Roy. Soc. London A , 399 (1985) pp. 243–275 [a3] M.F. Barnsley, J.H. Elton, D.P. Hardin, "Recurrent iterated function systems" Constr. Approx. , 5 (1989) pp. 3–31 [a4] J. Elton, "An ergodic theorem for iterated maps" Ergodic Th. & Dynamical Systems , 7 (1987) pp. 481–488 [a5] B. Forte, E.R. Vrscay, "Solving the inverse problem for measures using iterated function systems: a new approach" Adv. Appl. Probab. , 27 (1995) pp. 800–820 [a6] J.S. Geronimo, D.P. Hardin, P.R. Massopust, "Fractal functions and wavelet expansions based on several scaling functions" J. Approx. Th. , 78 (1994) pp. 373–401 [a7] J.E. Hutchinson, "Fractals and self-similarity" Indiana Univ. Math. J. , 30 (1981) pp. 713–747 [a8] R.F. Williams, "Composition of contractions" Bol. Soc. Brasil. Mat. , 2 (1971) pp. 55–59
How to Cite This Entry:
Iterated function system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Iterated_function_system&oldid=47448
This article was adapted from an original article by F.M. Dekking (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article