Self-similarity

Intuition

Intuitively, a self-similar set is one that is composed of smaller copies of itself.

Koch curve

The Koch curve is composed of four subsets, each scaled by $1/3$.

Koch zoom

As we zoom into the Koch curve, we see details at all levels - an observed property of natural objects that fractals are meant to capture.

Sierpinski triangle

The Spierpinski triangle is composed of three subsets, each scaled by $1/2$.

Barnsley's fern

A semi-realistic fern

Square?

A square is made of four pieces, each scaled by $1/2$

Iterated function systems

Self-similar sets are described mathematically by iterated function systems - which are simply lists of functions that specify how the whole maps onto the parts.

Defintions

• A function \(f:\mathbb{R}^n\to \mathbb{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 \(\mathbb{R}^n.\)
  • If \(|f(x)-f(y)| = r|x-y|\) for all \(x,y\) in \(\mathbb{R}^n,\) then \(f\) is called a similarity and the number \(r\) is called its contraction ratio.
• An iterated function system (or IFS) on \(\mathbb{R}^n\) is simply a non-empty, finite collection of contractions of \(\mathbb{R}^n.\) We will usually express an IFS in the form \(\left\{f_i\right\}_{i=1}^m\) where \(m\) is the number of functions in the IFS.
• If \(\left\{f_i\right\}_{i=1}^m\) is an IFS of similarities, the list \(\left\{r_i\right\}_{i=1}^m\) of corresponding contraction ratios is called the contraction ratio list of the IFS.

Main Theorem

Let \(\left\{f_i\right\}_{i=1}^m\)be an IFS of contractions defined on \(\mathbb{R}^n.\) Then there is a unique non-empty, closed, bounded set \(E\) in \(\mathbb{R}^n\) such that \[E= \underset{i=1}{\overset{m}{\bigcup }}f_i(E).\]

That set is called the attractor or invariant set of the IFS.

Square

The solid unit square is the invariant set of

Sierpinski triangle

The Sierpinski triangle is the invariant set of

Koch curve

The Koch curve is the invariant set of

where $R_{\theta}$ is the rotation matrix we studied when discussing complex eigenvalues.

More complicated examples

Most often, iterated function systems on $\mathbb R^n$ are defined using affine functions - i.e., functions of the form $$f(\vec{x}) = A\,\vec{x}+\vec{b},$$ where $A\in\mathbb R^{n\times n}$. Thus, we need an understanding of the geometric action of matrices to understand these things.

Spiral

This interactive spiral consists of 2 pieces - a larger black one scaled down a tiny bit and rotated together with a smaller blue one scaled down by $1/10$ and shifted to the right.

Koch with reflection

$\displaystyle M = \begin{pmatrix}1&0\\0&-1\end{pmatrix}$ adds reflection:

Different compression ratios

$\displaystyle M = \begin{pmatrix}1/3&0\\0&2/3\end{pmatrix}$ scales by different amounts in different directions

Barnsley's IFS

The IFS for Barnsley's fern:

Barnsley's approximation

The effect of 1 application of Barnsley's IFS to an initial set, together with the attractor.

Iteration

Images of self-similar sets are typically generated with an iterative procedure.

Iteration of an IFS

Given an iterated function system \(\left\{f_i\right\}_{i=1}^m,\) we define a function \(T\) that maps the collection of closed, bounded subsets of \(\mathbb{R}^n\) to itself by \[T(K) = \underset{i=1}{\overset{m}{\bigcup }}f_i(K).\] It turns out that if we start with an arbitrary non-empty, closed, bounded subset of \(\mathbb{R}^n\) and iterate \(T,\) then the generated sequence of sets converges in a natural sense to the invariant set of the IFS.

An odd initial set

The initial approximation has no bearing on the attractor, which is determined only by the IFS.

An IFS app

IFS app (cont)

You specify an affine function using input like [M,v], where M is a 2 by 2 array representing a matrix and v is a an array of length 2 representing a vector. An IFS is then an array of affine functions. Here, for example, is a representation of the Sierpinski triangle:

							M = [[1/2,0],[0,1/2]];
							[
							  [M,[0,0]],
							  [M,[1/2,0]],
							  [M,[1/4,sqrt(3)/4]]
							]