TOPICS
Search

Iterated Function System


An iterated function system is a nonempty finite set of contraction mappings w_i for i=1, 2, ..., N, where N>=1, each with a contractivity factor s_i<1, mapping a nonempty compact metric space into itself. It is the basis for fractal image compression techniques.

The system has a unique nonempty compact set K, called its attractor, satisfying

 K= union _(i=1)^Nw_i(K).

Repeatedly applying all the maps to a nonempty compact set converges to K in the Hausdorff metric (Hutchinson 1981).

IteratedFunctionSystemFixedAttractor

For the three vertices v of an equilateral triangle, the maps w_v(x)=(x+v)/2 have the Sierpiński sieve as their attractor. The illustration shows the three images of the initial triangle and a seventh-stage approximation, colored by the first map. The golden gaskets use the same three centers with specially chosen contraction ratios greater than 1/2, producing overlapping images (Broomhead et al. 2004).

The chaos game samples the same fixed system by choosing an index I_n independently at each step and setting x_(n+1)=w_(I_n)(x_n). For positive probabilities p_i with sum_(i)p_i=1, the stationary probability measure satisfies

 mu(A)=sum_(i=1)^Np_imu(w_i^(-1)(A)),

where A is a Borel set and w_i^(-1)(A) denotes its pre-image. Changing these probabilities can change the measure while leaving its support K unchanged (Hutchinson 1981). When the maps are similarities, this is a self-similar measure.


See also

Barnsley's Fern, Chaos Game, Contraction Mapping, Exact Overlaps Conjecture, Koch Curve, Self-Similar Measure, Self-Similarity, Sierpiński Sieve

Explore with Wolfram|Alpha

References

Barnsley, M. Fractals Everywhere, 2nd ed. Boston, MA: Academic Press, 1993.Barnsley, M. F. "Fractal Image Compression." Not. Amer. Math. Soc. 43, 657-662, 1996.Barnsley, M. F. and Demko, S. G. "Iterated Function Systems and the Global Construction of Fractals." Proc. Roy. Soc. London, Ser. A 399, 243-275, 1985.Barnsley, M. F. and Hurd, L. P. Fractal Image Compression. Wellesley, MA: A K Peters, 1993.Bogomolny, A. "The Collage Theorem." https://www.cut-the-knot.org/ctk/ifs.shtml.Broomhead, D.; Montaldi, J.; and Sidorov, N. "Golden Gaskets: Variations on the Sierpiński Sieve." Nonlinearity 17, 1455-1480, 2004. https://doi.org/10.1088/0951-7715/17/4/017.Diaconis, P. M. and Shashahani, M. "Products of Random Matrices and Computer Image Generation." Contemp. Math. 50, 173-182, 1986.Fisher, Y. Fractal Image Compression. New York: Springer-Verlag, 1995.Hutchinson, J. E. "Fractals and Self-Similarity." Indiana Univ. Math. J. 30, 713-747, 1981. https://doi.org/10.1512/iumj.1981.30.30055.Trott, M. The Mathematica GuideBook for Graphics. New York: Springer-Verlag, 2004. §1.1.1. https://www.mathematicaguidebooks.org/.Wagon, S. "Iterated Function Systems." §5.2 in Mathematica in Action. New York: W. H. Freeman, pp. 149-156, 1991.

Referenced on Wolfram|Alpha

Iterated Function System

Cite this as:

Weisstein, Eric W. "Iterated Function System." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IteratedFunctionSystem.html

Subject classifications