Namespaces
Variants
Actions

Difference between revisions of "Iterated function system"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101101.png" /> of mappings, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101102.png" /> is a [[Complete metric space|complete metric space]]. Usually, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101103.png" /> is a finite set, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101104.png" />. An iterated function system is called hyperbolic if all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101105.png" /> are contracting (cf. [[Contraction(2)|Contraction]]) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101106.png" />. An iterated function system induces a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101107.png" /> from the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101108.png" /> to itself by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i1101109.png" />. If the iterated function system is hyperbolic and one restricts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011010.png" /> to the space of non-empty closed bounded sets equipped with the [[Hausdorff metric|Hausdorff metric]], then it follows from the [[Contracting-mapping principle|contracting-mapping principle]] that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011011.png" /> has a unique fixed point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011012.png" />; moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011013.png" /> is compact ([[#References|[a8]]], [[#References|[a7]]]). The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011014.png" /> is called the attractor, or invariant set, of the iterated function system. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011015.png" /> is a Euclidean space and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011016.png" /> are similitudes, then the attractor is called a self-similar set. These sets are usually fractals (cf. [[Fractals|Fractals]]); an example is the triadic Cantor set (cf. also [[Cantor set|Cantor set]]), which is the attractor of the iterated function system
+
<!--
 +
i1101101.png
 +
$#A+1 = 43 n = 0
 +
$#C+1 = 43 : ~/encyclopedia/old_files/data/I110/I.1100110 Iterated function system
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011017.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
A generalization is the concept of a recurrent self-similar (or mixed self-similar) set generated by a recurrent iterated function system. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011018.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011019.png" />-matrix of zeros and ones satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011020.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011021.png" />, and let contracting mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011022.png" /> be given for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011023.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011024.png" />. Then (see [[#References|[a3]]] or [[#References|[a1]]]) there is a unique vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011025.png" /> of non-empty compact sets such that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011026.png" />,
+
A family  $  \{ { {f _ {i} } : X \rightarrow X } : {i \in I } \} $
 +
of mappings, where  $  ( X, \rho ) $
 +
is a [[Complete metric space|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(2)|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|Hausdorff metric]], then it follows from the [[Contracting-mapping principle|contracting-mapping principle]] that $  F $
 +
has a unique fixed point  $  K $;
 +
moreover,  $  K $
 +
is compact ([[#References|[a8]]], [[#References|[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|Fractals]]); an example is the triadic Cantor set (cf. also [[Cantor set|Cantor set]]), which is the attractor of the iterated function system
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011027.png" /></td> </tr></table>
+
$$
 +
\left \{ x \mapsto {
 +
\frac{1}{3}
 +
} x,  x \mapsto {
 +
\frac{1}{3}
 +
} x + {
 +
\frac{2}{3}
 +
} \right \} .
 +
$$
  
An iterated function system with probabilities is an iterated function system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011028.png" /> together with a probability vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011029.png" /> (i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011031.png" />). This induces a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011032.png" /> on the space of Borel probability measures by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011033.png" /> for all Borel sets (cf. also [[Borel set|Borel set]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011034.png" />. If the iterated function system is hyperbolic, then there is a unique fixed point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011035.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011036.png" />, i.e. an invariant measure, whose topological support is the attractor of the iterated function system [[#References|[a7]]]. Convergence to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011037.png" /> is also obtained by associating a random dynamical system with the iterated function system via the [[Markov chain|Markov chain]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011038.png" />, where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011039.png" /> form a sequence of independent random variables with distributions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011040.png" /> [[#References|[a2]]]. The same type of result holds for recurrent iterated function systems, taking for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011041.png" /> a Markov chain on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011042.png" /> whose transition probabilities are positive if and only if the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110110/i11011043.png" /> are positive [[#References|[a3]]], [[#References|[a4]]]. Iterated function systems are applied for approximation purposes (see, e.g., [[#References|[a5]]]) and the construction of wavelets (see, e.g., [[#References|[a6]]]).
+
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 [[#References|[a3]]] or [[#References|[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|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 [[#References|[a7]]]. Convergence to $  \nu $
 +
is also obtained by associating a random dynamical system with the iterated function system via the [[Markov chain|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} $[[#References|[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 [[#References|[a3]]], [[#References|[a4]]]. Iterated function systems are applied for approximation purposes (see, e.g., [[#References|[a5]]]) and the construction of wavelets (see, e.g., [[#References|[a6]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Bandt,  "Self similar sets I. Topological Markov chains and mixed self-similar sets"  ''Math. Nachr.'' , '''142'''  (1989)  pp. 107–123</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.F. Barnsley,  D. Demko,  "Iterated function systems and the global construction of fractals"  ''Proc. Roy. Soc. London A'' , '''399'''  (1985)  pp. 243–275</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M.F. Barnsley,  J.H. Elton,  D.P. Hardin,  "Recurrent iterated function systems"  ''Constr. Approx.'' , '''5'''  (1989)  pp. 3–31</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Elton,  "An ergodic theorem for iterated maps"  ''Ergodic Th. &amp; Dynamical Systems'' , '''7'''  (1987)  pp. 481–488</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.E. Hutchinson,  "Fractals and self-similarity"  ''Indiana Univ. Math. J.'' , '''30'''  (1981)  pp. 713–747</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  R.F. Williams,  "Composition of contractions"  ''Bol. Soc. Brasil. Mat.'' , '''2'''  (1971)  pp. 55–59</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Bandt,  "Self similar sets I. Topological Markov chains and mixed self-similar sets"  ''Math. Nachr.'' , '''142'''  (1989)  pp. 107–123</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.F. Barnsley,  D. Demko,  "Iterated function systems and the global construction of fractals"  ''Proc. Roy. Soc. London A'' , '''399'''  (1985)  pp. 243–275</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M.F. Barnsley,  J.H. Elton,  D.P. Hardin,  "Recurrent iterated function systems"  ''Constr. Approx.'' , '''5'''  (1989)  pp. 3–31</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Elton,  "An ergodic theorem for iterated maps"  ''Ergodic Th. &amp; Dynamical Systems'' , '''7'''  (1987)  pp. 481–488</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.E. Hutchinson,  "Fractals and self-similarity"  ''Indiana Univ. Math. J.'' , '''30'''  (1981)  pp. 713–747</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  R.F. Williams,  "Composition of contractions"  ''Bol. Soc. Brasil. Mat.'' , '''2'''  (1971)  pp. 55–59</TD></TR></table>

Latest revision as of 22:13, 5 June 2020


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