Iterative Function System

http://www.calresco.org/lucas/classify.htm

from the site ...

An iterated system departs from the linear input -> process -> output chain common to most scientific thinking and loops the output back into the input. Thus the same process occurs repeatedly (recursively). As the process can modify the system variables this allows the results to cover a wide range or to map out a path or orbit in state space. Fractal equations like the MandelbrotSet and Julia sets are systems of this type. In IFS Fractals the system consists generally of a set of mathematical equations (usually contractive affine transformations) one of which is chosen (usually probabilistically) for each iteration. This process generates such famous constructions as the Koch snowflake, Sierpinski triangle and Barnsley fern.

Mathematically speaking (and very loosely) the theory of IFS is a corollary of the Banach Contraction Mapping Theorem (also known as the Banach-Caccioppoli fixed point theorem). It turns out that you can take a finite union of contractive (in the Lipschitz sense) maps on a complete metric space, and come up with a contractive map. Thus by the CMT, this map has a unique fixed point, and iterating the map on any input from the space will get you to the fixed point (it is even guaranteed to converge fairly quickly). The resulting sets are often fractals.

True but inaccessible to those who don't already get the point.

The translation is, roughly, systems in general have a solution iff it has a "fixed point": a solution is a point that maps to itself under the transformation in question. The transformation is the iterated (or recursive; same thing, here) sequence of operations that supposedly gives the solution.

For instance, Newton's method for finding a root (e.g. third root). It works well precisely because each iterated step is (highly) contractive (converges to a smaller interval on each step) and has a fixed point over the reals (is guaranteed to yield a solution, neglecting side issues).

However it is more problematic over the complex numbers, because the solutions are surrounded by fractal basins; an iterated initial point may oscillate between regions surrounding each of the three roots on each iteration, which makes for pretty fractal pictures but lousy convergence if you just want a numeric answer.

CategoryMath