# Iterated function system > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Iterated_function_system > Markdown URL: https://mediated.wiki/source/Iterated_function_system.md > Source: https://en.wikipedia.org/wiki/Iterated_function_system > Source revision: 1353176386 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Method for the construction of fractals [Sierpiński triangle](/source/Sierpi%C5%84ski_triangle) created using IFS (colored to illustrate self-similar structure) Colored IFS designed using [Apophysis](/source/Apophysis_(software)) software and rendered by the [Electric Sheep](/source/Electric_Sheep) In [mathematics](/source/Mathematics), **iterated function systems** (**IFSs**) are a method of constructing [fractals](/source/Fractal); the resulting fractals are often [self-similar](/source/Self-similar). IFS fractals are more related to [set theory](/source/Set_theory) than fractal geometry.[1] They were introduced in 1981. **IFS** fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the [Sierpiński triangle](/source/Sierpi%C5%84ski_triangle). The functions are normally [contractive](/source/Contraction_mapping), which means they bring points closer together and make shapes smaller. Hence, the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, [ad infinitum](/source/Ad_infinitum). This is the source of its self-similar fractal nature. ## Definition Formally, an [iterated function](/source/Iterated_function) system is a finite set of [contraction mappings](/source/Contraction_mapping) on a [complete metric space](/source/Complete_metric_space).[2] Symbolically, - { f i : X → X ∣ i = 1 , 2 , … , N } , N ∈ N {\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} } is an iterated function system if each fi is a contraction on the complete metric space X. ## Properties Construction of an IFS by the [chaos game](/source/Chaos_game) (animated) IFS being made with two functions Hutchinson showed that, for the metric space ℝ*n*, or more generally, for a complete metric space X {\displaystyle X} , such a system of functions has a unique nonempty [compact](/source/Compact_space) (closed and bounded) fixed set S.[3] One way of constructing a fixed set is to start with an initial nonempty closed and bounded set *S*0 and iterate the actions of the *f**i*, taking *S**n*+1 to be the union of the images of *S**n* under the *f**i*; then taking S to be the [closure](/source/Closure_(topology)) of the limit lim*n*→∞ *Sn*. Symbolically, the unique fixed (nonempty compact) set *S* ⊆ *X* has the property - S = ⋃ i = 1 N f i ( S ) ¯ . {\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.} The set S is thus the fixed set of the [Hutchinson operator](/source/Hutchinson_operator) *F* : 2*X* → 2*X* defined for *A* ⊆ *X* via - F ( A ) = ⋃ i = 1 N f i ( A ) ¯ . {\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.} The existence and uniqueness of S is a consequence of the [contraction mapping principle](/source/Contraction_mapping_principle), as is the fact that - lim n → ∞ F n ( A ) = S {\displaystyle \lim _{n\to \infty }F^{n}(A)=S} for any nonempty compact set A in X. (For contractive IFS this convergence takes place even for any nonempty closed bounded set A). Random elements arbitrarily close to S may be obtained by the "chaos game", described below. Recently it was shown that the IFSs of non-contractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in X) can yield attractors. These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.[4] The collection of functions fi [generates](/source/Generating_set) a [monoid](/source/Monoid) under [composition](/source/Function_composition). If there are only two such functions, the monoid can be visualized as a [binary tree](/source/Binary_tree), where, at each node of the tree, one may compose with the one or the other function (*i.e.* take the left or the right branch). In general, if there are k functions, then one may visualize the monoid as a full [k-ary tree](/source/K-ary_tree), also known as a [Cayley tree](/source/Cayley_tree). ## Constructions [Barnsley's fern](/source/Barnsley's_fern), an early IFS [Menger sponge](/source/Menger_sponge), a 3-dimensional IFS IFS "tree" constructed with non-linear function Julia Sometimes each function fi is required to be a [linear](/source/Linear_transformation), or more generally an [affine](/source/Affine_transformation), transformation, and hence represented by a [matrix](/source/Matrix_(mathematics)). However, IFSs may also be built from non-linear functions, including [projective transformations](/source/Projective_transformation) and [Möbius transformations](/source/M%C3%B6bius_transformation). The [Fractal flame](/source/Fractal_flame) is an example of an IFS with nonlinear functions. The most common algorithm to compute IFS fractals is called the "[chaos game](/source/Chaos_game)". It consists of picking a random point in the plane, then iteratively applying one of the functions chosen at random from the function system to transform the point to get a next point. An alternative algorithm is to generate each possible sequence of functions up to a given maximum length, and then to plot the results of applying each of these sequences of functions to an initial point or shape. Each of these algorithms provides a global construction which generates points distributed across the whole fractal. If a small area of the fractal is being drawn, many of these points will fall outside of the screen boundaries. This makes zooming into an IFS construction drawn in this manner impractical. Although the theory of IFS requires each function to be contractive, in practice software that implements IFS only require that the whole system be contractive on average.[5] ## Partitioned iterated function systems PIFS (partitioned iterated function systems), also called local iterated function systems,[6] give surprisingly good image compression, even for photographs that do not seem to have the kinds of self-similar structure shown by simple IFS fractals.[7] ## The inverse problem Main article: [Fractal compression](/source/Fractal_compression) Very fast algorithms exist to generate an image from a set of IFS or PIFS parameters. It is faster and requires much less storage space to store a description of how it was created, transmit that description to a destination device, and regenerate that image anew on the destination device, than to store and transmit the color of each pixel in the image.[6] The [inverse problem](/source/Inverse_problem) is more difficult: given some original arbitrary digital image such as a digital photograph, try to find a set of IFS parameters which, when evaluated by iteration, produces another image visually similar to the original. In 1989, Arnaud Jacquin presented a solution to a restricted form of the inverse problem using only PIFS; the general form of the inverse problem remains unsolved.[8][9][6] By 1995, all [fractal compression](/source/Fractal_compression) software was based on Jacquin's approach.[9] ## Examples The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the [Hutchinson operator](/source/Hutchinson_operator). Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal. Early examples of fractals which may be generated by an IFS include the [Cantor set](/source/Cantor_set), first described in 1884; and [de Rham curves](/source/De_Rham_curve), a type of self-similar curve described by [Georges de Rham](/source/Georges_de_Rham) in 1957. ## History IFSs were conceived in their present form by [John E. Hutchinson](https://en.wikipedia.org/w/index.php?title=John_E._Hutchinson&action=edit&redlink=1) in 1981[3] and popularized by [Michael Barnsley](/source/Michael_Barnsley)'s book *Fractals Everywhere*. IFSs provide models for certain plants, leaves, and ferns, by virtue of the self-similarity which often occurs in branching structures in nature. — Michael Barnsley *et al.*[10] ## See also - [Mathematics portal](https://en.wikipedia.org/wiki/Portal:Mathematics) - [Complex-base system](/source/Complex-base_system#Base_.E2.88.921.C2.B1i) - [Collage theorem](/source/Collage_theorem) - [Infinite compositions of analytic functions](/source/Infinite_compositions_of_analytic_functions) - [L-system](/source/L-system) - [Fractal compression](/source/Fractal_compression) ## Notes 1. **[^](#cite_ref-picg_1-0)** Zobrist, George Winston; Chaman Sabharwal (1992). [*Progress in Computer Graphics: Volume 1*](https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC). Intellect Books. p. 135. [ISBN](/source/ISBN_(identifier)) [9780893916510](https://en.wikipedia.org/wiki/Special:BookSources/9780893916510). Retrieved 7 May 2017. 1. **[^](#cite_ref-2)** Michael Barnsley (1988). *Fractals Everywhere*, p.82. Academic Press, Inc. [ISBN](/source/ISBN_(identifier)) [9780120790623](https://en.wikipedia.org/wiki/Special:BookSources/9780120790623). 1. ^ [***a***](#cite_ref-hutchinson_3-0) [***b***](#cite_ref-hutchinson_3-1) Hutchinson, John E. (1981). ["Fractals and self similarity"](https://maths-people.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf) (PDF). *Indiana Univ. Math. J*. **30** (5): 713–747. [doi](/source/Doi_(identifier)):[10.1512/iumj.1981.30.30055](https://doi.org/10.1512%2Fiumj.1981.30.30055). 1. **[^](#cite_ref-4)** M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System 1. **[^](#cite_ref-5)** [Draves, Scott](/source/Scott_Draves); Erik Reckase (July 2007). ["The Fractal Flame Algorithm"](https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf) (PDF). Archived from [the original](http://flam3.com/flame.pdf) (PDF) on 2008-05-09. Retrieved 2008-07-17. 1. ^ [***a***](#cite_ref-lacroix_6-0) [***b***](#cite_ref-lacroix_6-1) [***c***](#cite_ref-lacroix_6-2) Bruno Lacroix. ["Fractal Image Compression"](http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp01/MQ36939.pdf). 1998. 1. **[^](#cite_ref-SIGGRAPH'92_7-0)** Fischer, Yuval (1992-08-12). Przemyslaw Prusinkiewicz (ed.). [*SIGGRAPH'92 course notes - Fractal Image Compression*](https://web.archive.org/web/20170912012035/https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf) (PDF). [SIGGRAPH](http://www.siggraph.org/). Vol. Fractals - From Folk Art to Hyperreality. [ACM SIGGRAPH](/source/ACM_SIGGRAPH). Archived from [the original](https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf) (PDF) on 2017-09-12. Retrieved 2017-06-30. 1. **[^](#cite_ref-8)** Dietmar Saupe, Raouf Hamzaoui. ["A Review of the Fractal Image Compression Literature"](https://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/SaHa94.pdf). 1. ^ [***a***](#cite_ref-kominek_9-0) [***b***](#cite_ref-kominek_9-1) John Kominek. ["Algorithm for Fast Fractal Image Compression"](https://web.archive.org/web/20181123231446/https://pdfs.semanticscholar.org/d77b/ffac2560c92771d3756c0e29863a44919d6f.pdf). [doi](/source/Doi_(identifier)):[10.1117/12.206368](https://doi.org/10.1117%2F12.206368). 1. **[^](#cite_ref-V-variable_10-0)** [Michael Barnsley](/source/Michael_Barnsley), *et al.*,["V-variable fractals and superfractals"](https://www.maths.anu.edu.au/~barnsley/pdfs/V-var_super_fractals.pdf) (PDF). (2.22 MB) ## References - [Draves, Scott](/source/Scott_Draves); Erik Reckase (July 2007). ["The Fractal Flame Algorithm"](https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf) (PDF). Archived from [the original](http://flam3.com/flame.pdf) (PDF) on 2008-05-09. Retrieved 2008-07-17. - [Falconer, Kenneth](/source/Kenneth_Falconer_(mathematician)) (1990). [*Fractal geometry: Mathematical foundations and applications*](https://archive.org/details/fractalgeometrym0000falc/page/113). John Wiley and Sons. pp. [113–117, 136](https://archive.org/details/fractalgeometrym0000falc/page/113). [ISBN](/source/ISBN_(identifier)) [0-471-92287-0](https://en.wikipedia.org/wiki/Special:BookSources/0-471-92287-0). - [Barnsley, Michael](/source/Michael_Barnsley); Andrew Vince (2011). "The Chaos Game on a General Iterated Function System". *Ergodic Theory Dynam. Systems*. **31** (4): 1073–1079. [arXiv](/source/ArXiv_(identifier)):[1005.0322](https://arxiv.org/abs/1005.0322). [Bibcode](/source/Bibcode_(identifier)):[2010arXiv1005.0322B](https://ui.adsabs.harvard.edu/abs/2010arXiv1005.0322B). [doi](/source/Doi_(identifier)):[10.1017/S0143385710000428](https://doi.org/10.1017%2FS0143385710000428). [S2CID](/source/S2CID_(identifier)) [122674315](https://api.semanticscholar.org/CorpusID:122674315). - David, Claire (2019). ["Fractal properties of Weierstrass-type functions"](https://journals.onaft.edu.ua/index.php/geometry/article/view/1485). *Proceedings of the International Geometry Center*. **12** (2): 43–61. [doi](/source/Doi_(identifier)):[10.15673/tmgc.v12i2.1485](https://doi.org/10.15673%2Ftmgc.v12i2.1485). [S2CID](/source/S2CID_(identifier)) [209964068](https://api.semanticscholar.org/CorpusID:209964068). ## External links - [A Primer on the Elementary Theory of Infinite Compositions of Complex Functions](https://www.researchgate.net/publication/362010262_A_Primer_on_the_Elementary_Theory_of_Infinite_Compositions_of_Complex_Functions_Images) v t e Fractal software Digital art Graphics software Fractal art Open-source Apophysis Blender Fractint Fyre Kalles Fraktaler MilkDrop Sterling GNU Electric Sheep GIMP openPlaG XaoS Freeware BoleemanSoftware Retail Cross-platform Bryce Maple Ultra Fractal Wolfram Mathematica Windows only VisSim Scenery generator MojoWorld Generator Picogen Terragen VistaPro Found objects Burning Ship fractal Jerusalem cube Julia set Mandelbox Mandelbrot set Mandelbulb Related Computer-generated imagery Fractal compression Fractal landscape Fractal flame Iterated function system Mathematical visualization Orbit trap Category v t e Fractals Characteristics Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity Iterated function system Barnsley fern Cantor set Koch snowflake Menger sponge Sierpiński carpet Sierpiński triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Gosper curve Pythagoras tree Weierstrass function Strange attractor Multifractal system L-system Fractal canopy Space-filling curve H tree Escape-time fractals Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb Rendering techniques Buddhabrot Orbit trap Pickover stalk Random fractals Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk People Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Niels Fabian Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński Other Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory Authority control databases GND --- Adapted from the Wikipedia article [Iterated function system](https://en.wikipedia.org/wiki/Iterated_function_system) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Iterated_function_system?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.