Iterated function systems

Section 4.3 Iterated function systems

We now provide a careful mathematical definition of one of the central tools of fractal geometry - the iterated function system or IFS. The idea behind the IFS technique is to focus on how the parts of a set might fit together to create the whole. Thus, we focus on what makes two sets similar; we do this with the notion of a similarity. An IFS is a collection of similarities and a self-similar set is the attractor of an IFS. Thus, we actually need to make several definitions, which we will illustrate with examples afterwards.

🔗

Subsection 4.3.1 IFS definitions

🔗

We assume we are working in

R^{n},

n

-dimensional Euclidean space. The dimension

n

will almost always be

2

in this text, although

n = 1

might be the natural setting for the Cantor set. Our sets will generally be subsets of the plane. Given

x

R^{n},

| x |

will refer to the distance from

x

to the origin. Thus,

| x - y |

represents the distance from

x

y .

🔗

Definition 4.3.1.

A function $f : R^{n} \to R^{n}$ will be called a contraction if there is a real number $r$ such that $0 < r < 1$ and $| f (x) - f (y) | \leq r | x - y |$ for all $x, y$ in $R^{n} .$ If $| f (x) - f (y) | = r | x - y |$ for all $x, y$ in $R^{n},$ then $f$ is called a similarity and the number $r$ is called its contraction ratio.

🔗

Definition 4.3.2.

An iterated function system on $R^{n},$ or IFS, is a non-empty, finite collection of contractions of $R^{n} .$ We will usually express an IFS in the form

{f_{i}}_{i = 1}^{m},

where $m$ is the number of functions in the IFS.

🔗

We will often be interested in the case where all functions in the IFS are similarities, but that's not a requirement not is it a hypothesis in the following theorem.

🔗

Theorem 4.3.3. Existence of invariant sets.

For any IFS

{f_{i}}_{i = 1}^{m},

there is a unique non-empty, closed, bounded subset $E$ of $R^{n}$ such that

\begin{matrix} (4.3.1) & E = \underset{i = 1}{⋃^{m}} f_{i} (E) . \end{matrix}

The set $E$ defined is called the invariant set or attractor of the IFS. If the IFS consists entirely of contractive similarities, then $E$ is called self-similar.

🔗

Subsection 4.3.2 Interpretation

🔗

We will make frequent use of Theorem 4.3.3, so let’s make sure we understand what it is saying. First, the notation

f_{i} (E)

refers to the image of the set

E

under the action of the function

f_{i} .

For the general function

f : R^{n} \to R^{n}

and set

E \subset R^{n},

f (E) = {f (x) : x \in E} .

🔗

If the function

f

happens to be a similarity, then application of

f

transforms

E

into a set which is geometrically similar to

E .

This idea is illustrated in figure Figure 4.3.4.

🔗
Figure 4.3.4. The action of a contractive similarity on a set $E$ in the plane

🔗

If a set is self-similar, then it can be decomposed into several parts - each of which is geometrically similar to the whole. The decomposition of the Sierpinski triangle, for example, is shown if Figure 4.3.5

🔗
Figure 4.3.5. Decomposition of the Sierpinski triangle