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