# 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]).

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