Hutchinson operator

In mathematics, in the study of fractals, a Hutchinson operator^[1] is the collective action of a set of contractions, called an iterated function system.^[2] The iteration of the operator converges to a unique attractor, which is the often self-similar fixed set of the operator.

Definition

Let [math]\displaystyle{ \{f_i : X \to X\ |\ 1\leq i \leq N\} }[/math] be an iterated function system, or a set of contractions from a compact set [math]\displaystyle{ X }[/math] to itself. The operator [math]\displaystyle{ H }[/math] is defined over subsets [math]\displaystyle{ S\subset X }[/math] as

[math]\displaystyle{ H(S) = \bigcup_{i=1}^N f_i(S).\, }[/math]

A key question is to describe the attractors [math]\displaystyle{ A=H(A) }[/math] of this operator, which are compact sets. One way of generating such a set is to start with an initial compact set [math]\displaystyle{ S_0\subset X }[/math] (which can be a single point, called a seed) and iterate [math]\displaystyle{ H }[/math] as follows

[math]\displaystyle{ S_{n+1} = H(S_n) = \bigcup_{i=1}^N f_i(S_n) }[/math]

and taking the limit, the iteration converges to the attractor

[math]\displaystyle{ A = \lim_{n \to \infty} S_n . }[/math]

Properties

Hutchinson showed in 1981 the existence and uniqueness of the attractor [math]\displaystyle{ A }[/math]. The proof follows by showing that the Hutchinson operator is contractive on the set of compact subsets of [math]\displaystyle{ X }[/math] in the Hausdorff distance.

The collection of functions [math]\displaystyle{ f_i }[/math] together with composition form a monoid. With N functions, then one may visualize the monoid as a full N-ary tree or a Cayley tree.

References