en>BG19bot: /* Examples */WP:CHECKWIKI error fix for #99. Broken sup tag. Do general fixes if a problem exists. -, replaced: ^{2 → ² using AWB (9957)}

2014-03-01T08:47:25Z

Examples: WP:CHECKWIKI error fix for #99. Broken sup tag. Do general fixes if a problem exists. -, replaced: 2 → 2 using AWB (9957)

Show changes

en>BTotaro at 18:16, 19 April 2013

2013-04-19T18:16:47Z

New page

[[Image:Sierpinski1.png|thumb|right|250px|[[Sierpinski gasket]] created using IFS (colored to illustrate self-similar structure)]]
[[Image:Chris Ursitti fractal 0000.png|thumb|right|200px|Colored IFS designed using [[Apophysis (software)|Apophysis]] software and rendered by the [[Electric Sheep]].]]
In [[mathematics]], '''iterated function systems''' or '''IFS'''s are a method of constructing [[fractal]]s; the resulting constructions are always [[self-similar]].

'''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 [[Sierpinski gasket]] also called the Sierpinski triangle. The functions are normally [[contraction mapping|contractive]] 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]]. This is the source of its self-similar fractal nature.

==Definition==
Formally, an [[iterated function]] system is a finite set of [[contraction mapping]]s on a [[complete metric space]].<ref>Michael Barnsley, "Fractals Everywhere", Academic Press, Inc., 1988.</ref> Symbolically,

:<math>\{f_i:X\to X|i=1,2,\dots,N\},\ N\in\mathbb{N}</math>

is an iterated function system if each <math>f_i</math> is a contraction on the complete metric space <math>X</math>.

==Properties==
Hutchinson (1981) showed that, for the metric space <math>\mathbb{R}^n</math>, such a system of functions has a unique [[Compact space|compact]] (closed and bounded) fixed set ''S''. One way of constructing a fixed set is to start with an initial point or set ''S''0 and iterate the actions of the ''f''''i'', taking ''S''''n''+1 to be the union of the image of ''S''''n'' under the ''f''''i'' ; then taking ''S'' to be the [[Closure (topology)|closure]] of the union of the ''S''''n''. Symbolically, the unique fixed (nonempty compact) set <math>S\subseteq X</math> has the property

:<math>S = \bigcup_{i=1}^N f_i(S).</math>

The set ''S'' is thus the fixed set of the [[Hutchinson operator]]

:<math>H(A)=\bigcup_{i=1}^Nf_i(A).</math>

The existence and uniqueness of ''S'' is a consequence of the [[contraction mapping principle]] as is the fact that

:<math>\lim_{n\to\infty}H^{\circ n}(A)=S</math>

for any nonempty compact set <math>A</math> in <math>X</math>. (For contractive IFS this convergence takes place even for any nonempty closed bounded set <math>A</math>). Random elements of ''S'' may be obtained by the "chaos game" below.

Recently it was shown that the IFSs of noncontractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in ''X'') can yield attractor.

These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.<ref>M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System</ref>

The collection of functions <math>f_i</math> [[Generating set|generates]] a [[monoid]] under [[Function composition|composition]]. If there are only two such functions, the monoid can be visualized as a [[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|''k''-ary tree]], also known as a [[Cayley tree]].

==Constructions==
[[Image:Chaosgame.gif|thumb|right|250px|Construction of an IFS by the [[chaos game]] (animated)]]

Sometimes each function <math>f_i</math> is required to be a [[Linear transformation|linear]],
or more generally an [[affine transformation]] and hence represented by a [[matrix (mathematics)|matrix]]. However, IFSs may also be built from non-linear functions, including [[projective transformation]]s and [[Möbius transformation]]s. The [[Fractal flame]] is an example of an IFS with nonlinear functions.

The most common algorithm to compute IFS fractals is called the [[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 and drawing the 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 normally 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.<ref>{{ cite web | last=Draves | first=Scott | authorlink=Scott Draves | coauthors=Erik Reckase | date=July 2007 | url=http://flam3.com/flame.pdf | title=The Fractal Flame Algorithm | format=pdf | accessdate=2008-07-17 }}</ref>

==Examples==
[[Image:Ifs-construction.png|thumb|right|400px|IFS being made with two functions.]]

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]]. 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]], first described in 1884; and [[de Rham curve]]s, a type of self-similar curve described by [[Georges de Rham]] in 1957.

[[Image:Fractal fern explained.png|thumb|right|150px|[[Barnsley's fern]] an early IFS.]]

==History==
IFS were conceived in their present form by [[John E. Hutchinson]] in 1981 <ref>{{cite journal | last=Hutchinson | first=John E. | title=Fractals and self similarity | journal=Indiana Univ. Math. J. | volume=30 | year=1981 | pages=713–747 | doi=10.1512/iumj.1981.30.30055 | url=http://wwwmaths.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf | issue=5 }}
</ref> and popularized by [[Michael Barnsley]]'s book ''Fractals Everywhere''. 

{{quote|"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.''<ref name=V-variable>[[Michael Barnsley]], ''et al.'',{{PDF|[http://www.maths.anu.edu.au/~barnsley/pdfs/V-var_super_fractals.pdf "V-variable fractals and superfractals"]|2.22 MB}}</ref>

==See also==
[[Image:Menger sponge (IFS).jpg|thumb|200px|[[Menger sponge]], a 3-Dimensional IFS.]]

* [[L-system]]
* [[Fractal compression]]
* [[Fractal flame]]
* [[Complex_base_systems#Base_.E2.88.921.C2.B1i|Complex base systems]]
* [[Infinite compositions of analytic functions]]

==Notes==
{{Reflist}}

==References==
* {{ cite web | last=Draves | first=Scott | authorlink=Scott Draves | coauthors=Erik Reckase | date=July 2007 | url=http://flam3.com/flame.pdf | title=The Fractal Flame Algorithm | format=pdf | accessdate=2008-07-17 }}
* {{ cite book | last=Falconer | first=Kenneth | authorlink=Kenneth Falconer (mathematician) | title=Fractal geometry: Mathematical foundations and applications | publisher=John Wiley and Sons | year=1990 | isbn=0-471-92287-0 | pages=113–117, 136 }}
* {{ cite news | last=Barnsley | first=Michael | authorlink=Michael Barnsley | coauthors=Andrew Vince | year=2010 | url=http://arxiv.org/pdf/1005.0322v1 | title=The Chaos Game on a General Iterated Function System | journal=Ergodic Theory Dynam. Systems 31 (2011), no. 4, 1073–1079| format=pdf | accessdate=2013-06-05 }}

{{Fractals}}

{{DEFAULTSORT:Iterated Function System}}
[[Category:Fractals]]

Regular sequence - Revision history

en>BG19bot: /* Examples */WP:CHECKWIKI error fix for #99. Broken sup tag. Do general fixes if a problem exists. -, replaced: 2 → 2 using AWB (9957)

en>BTotaro at 18:16, 19 April 2013

en>BG19bot: /* Examples */WP:CHECKWIKI error fix for #99. Broken sup tag. Do general fixes if a problem exists. -, replaced: ^{2 → ² using AWB (9957)}