Last week we looked at discrete dynamical systems of the form \(x_{n+1} = f(x_n)\) where \(x_n\) represents the state of some physical system at time point \(n\). We saw that such systems can have fixed points (when the state of the system reaches a certain value and stays there indefinitely) and periodic points (when the state of the system oscillates between some finite number of values). Dynamical systems (specifically non-linear dynamical systems) can also exhibit some really interesting aperiodic behaviour where the state of the system is attracted to a set of iterates (an orbit) which appears to be completely random and unpredictable.
One of the most well-known examples of this phenomenon systems is the logistic map - which is used as a model for the population growth and decline of a species. The logistic map is a dynamical system defined as follows: \[\begin{align*} x_{n+1} = f(x_n) = r x_n (1-x_n),\end{align*}\] where \(x_n\) is a number between zero and one which represents the ratio of an existing population to the maximum possible population which can be supported by the environment. The constant \(r\) represents the growth rate of the population. Typically we consider growth rates \(0 < r \leq 4\) as values outside of this range lead to negative populations (which doesn’t make much physical sense!). For these values of \(r\), the system is always attracted to some sort of stable orbit, which we call the attractor of the system and the properties of the attractor depend on the value of \(r\).
When \(r\) is less than one, the population rapidly dies off to zero (an attractive fixed point), regardless of the initial population. Then, as \(r\) is increased we begin to see more interesting behaviour. When \(r\) is between \(1\) and \(3\), the iterates are attracted towards a non-zero fixed point, i.e. the population approaches a stable value. This can be seen on the following figure, a plot of the first one hundred values of \(x_n\) for \(r = 2.5\).
When \(r\) is between \(3\) and \(1 + \sqrt{6}\), the iterates are attracted to a stable two-cycle. As seen below (for \(r = 3.2\)), this means that for large values of \(n\), the population oscillates between two fixed values.
When \(r\) is made even larger, we see that for values of \(r\) between approximately \(3.44949\) and \(3.54409\) a four-cycle emerges, as shown on the following figure.
If we continued to increase \(r\), we would see the emergence of an attractive \(8\)-cycle, \(16\)-cycle, etc... This is referred to as period-doubling. Eventually, \(r\) surpasses a critical value of approximately \(3.56995\) and the behaviour changes dramatically. For values of \(r\) near this critical value most initial populations lead to orbits which are never periodic and appear random, and unpredictable, like the orbit shown in the next figure.
Although the iterates look like they could be randomly generated, the process is entirely deterministic (if we start with the same \(x_0\) we will always get the exact same set of points). This type of behaviour is referred to as chaotic and the entire field of chaos theory is devoted to the study of such systems. In this lesson we will focus on one aspect of chaotic systems, that being the interesting geometric properties of the sets which they are attracted to (called strange attractors). For example, if we plot a large number of iterates \(x_n\) on the real number line we can visualize the space occupied by the attractor of the logistic map in its chaotic regime (\(r=3.7\)). This is shown in the figure below.
At first glance, it seems like the orbit fills in most of the space on the real line. However, if we zoom in on a smaller region of the set, we see that more small gaps emerge. If we continue to zoom in, we would continue to see the emergence of more and more gaps. Although the attractor contains an infinite number of points (since the orbit never repeats itself), these points are all disconnected from each other (even if we zoom in REALLY close).
In multiple dimensions, strange attractors can look very visually striking. An example in two dimensions is the Hénon attractor, shown below.
Strange attractors have some unique mathematical properties, one being that they have fractional dimensions and are thus called fractal sets. Briefly, fractal sets are those which are too irregular to be described by our usual ideas of Euclidean geometry.
The precise definition of a fractal set is difficult to pinpoint - in fact, Benoît Mandelbrot (the mathematician who proposed the term fractal) is said to have proposed multiple definitions himself. One thing fractal sets do have in common is the idea of possessing detail at all scales like we saw in the previous example. This means that as we zoom in on part of a fractal set more detail continues to emerge. This strange property of fractal sets makes it difficult to measure their sizes. As a motivating example, let’s consider the coastline paradox - which refers to the counterintuitive observation that the coastline of a landmass does not have a well-defined length.
First, let’s imagine that we want to measure the length of a well-defined curve. The length of a curve can be approximated by adding the sum of the straight lines which connect points on the curve, as shown in the figure below.
If we use only a few straight lines to approximate the length of the curve, the result is an estimate which is lower than the true length. As the we make the lines increasingly short (and thus use more of them) our estimate becomes more accurate and the sum approaches the curve’s true length (you may have seen this in calculus).
Let’s now consider applying the same procedure to measure the length of a coastline. The figure below shows the result of attempting to estimate the length of the coastline of Britain with increasingly small measuring sticks. The shape of the coastline is highly irregular and we see that as the size of the measuring sticks is decreased, more and more detail is picked up, increasing the length estimate. It turns out that, unlike the smooth curve shown above, in the case of coastlines, the length estimates do not stabilize, instead they continue increasing as we use smaller and smaller measuring sticks.
What we have seen is that for irregular curves, the higher the resolution you use to measure their length (i.e. the smaller the measuring sticks) the more detail you measure, leading to increasingly large length estimates. Now, in reality there is a limit to how small we can make our measuring sticks and thus to the level of detail we can measure when it comes to physical object like coastlines. On the other hand, mathematically we can study fractal sets which are infinite in nature. The simplest type of fractal sets which we can study are self-similar. This means that when we zoom in on any portion of the set, it looks similar to the original set. In other words, the set is made up a number of scaled down copies of itself. Let’s take a look at an example of a self-similar fractal.
The von Koch curve can be constructed by a simple iterative geometric procedure. Consider the following generator \(G\) which takes a line segment and removes the middle third, replacing it with two line segments one third the length of the original.
We can think of \(G\) as a special type of function - only instead of taking numbers as inputs and outputs, \(G\) takes sets of points as inputs and transforms them in a particular way. On its own, this is not all that interesting, but let’s consider what happens when we apply \(G\) iteratively.
The curve which results when we let \(n\) go to infinity is called the von Koch curve. We see from the figure above that is made up of four copies of itself, each scaled by a factor of one third.
Let’s now imagine that we want to measure the size of the von Koch curve. Since it is a curve, our first instinct would be to measure it’s length. Using the same approach we used for the coastline, we can approximate the length of the von Koch curve using finite measuring sticks. If we use measuring sticks of length \(\epsilon_n\), then our length estimate is given by \(L_n = N(\epsilon_n)\epsilon_n\) where \(N(\epsilon_n)\) is the number of measuring sticks of length \(\epsilon_n\) which are required.
Let us assume that the length of the line we started out with in the construction of the von Koch curve is one (i.e. \(\ell = 1\) in Example 2). Then if we use measuring sticks of length \(\frac{1}{3}\) we will clearly need \(4\) measuring sticks to cover the set. Setting \(\epsilon_1 = \frac{1}{3}\) we have \(L_1 = 4\cdot\frac{1}{3}\). If we shrink the rod further, letting \(\epsilon_2 = \frac{1}{3^2} = \frac{1}{9}\) then we will require \(4^2 = 16\) measuring sticks to cover the set, resulting in \(L_2 = 16\cdot\frac{1}{9}\). A pattern is clearly emerging. If we let \(\epsilon_n = \frac{1}{3^n}\), then \[\begin{align*} L_n = 4^n\cdot\frac{1}{3^n} = \left(\frac{4}{3}\right)^n.\end{align*}\] Since \(\frac{4}{3} > 1\) if we let \(n\) go to infinity (i.e. make the measuring rods really tiny), the length estimates will get larger and larger, never settling on a finite value. Just like the coastline example, the von Koch curve does not have a finite length!
So how can we measure the size of the von Koch curve? We could try measuring its area instead. We can estimate the area of an object in a similar way to length, but instead of measuring sticks we cover the set with \(\epsilon\)-tiles, squares of side length \(\epsilon\), and let \(A_n = N(\epsilon_n)\epsilon_n^2\). As we let \(\epsilon\) get very small, we require approximately the same number of \(\epsilon\)-tiles to cover the set as we needed measuring sticks of length \(\epsilon\). Thus for large \(n\) we have \[\begin{align*} A_n \approx 4^n\left(\frac{1}{3^n}\right)^2 = \left(\frac{4}{9}\right)^n.\end{align*}\] Since \(\frac{4}{9} < 1\), if we let \(n\) go to infinity, our estimates of the area will get smaller and smaller, approaching zero.
The von Koch curve has infinite length, but zero area!
In order to measure the size of the von Koch curve, it turns out we need some other type of measurement instead, a D-dimensional measurement, if you will. Consider the estimate \[\begin{align*} L^D(S) \approx N(\epsilon)\epsilon^D\end{align*}\] where \(\epsilon\) is the number of \(\epsilon\)-tiles required to cover the set. We can also write this as \[\begin{align*} L^D(S) = \lim_{\epsilon\to 0} N(\epsilon)\epsilon^D.\end{align*}\] This definition is actually consistent with our usual ideas of measurement. If we let \(D = 1\) then we recover our definition of length (how we measure one-dimensional objects) and if \(D=2\), we recover the definition of area (how we measure two-dimensional objects). We know that for the von Koch curve when \(D = 1\) we get an infinite measurement (length), and yet when \(D = 2\) we get a measurement (area) of zero, neither of which is particularly meaningful. Perhaps there is some fractional measure of \(D\) (between one and two) which yields a finite measurement.
Let’s once again consider covering the von Koch curve with tiles of side length \(\epsilon_n = \frac{1}{3^n}\). Now the \(D\)-dimensional estimate of its size is \[\begin{align*} L^D(\epsilon_n) = N(\epsilon_n)\epsilon_n^D = 4^n\left(\frac{1}{3^n}\right)^D = \left(\frac{4}{3^D}\right)^n.\end{align*}\] As we consider letting \(n\) go infinity, we see that if \(\frac{4}{3^D} < 1\), the result will be zero and if \(\frac{4}{3^D} > 1\), the result will be infinite. The only way we will have a finite measurement is if \(\frac{4}{3^D} = 1\). Solving for \(D\) we have \[\begin{align*} \frac{4}{3^D} &= 1\\ 4 &= 3^D\\ \log(4) &= D\log(3)\\ D & = \frac{\log(4)}{\log(3)}\\ &\approx 1.26\end{align*}\] which is a number between one and two, as expected. This fractional number \(D\approx 1.26\) is called the fractal dimension of the von Koch curve. For self-similar fractals like the von Koch curve we can compute this number exactly - in the real world we use numerical methods to estimate this number.
The result above can be written in another way, in terms of the scaling relationship between the number of \(\epsilon\)-tiles (or measuring sticks) needed to cover the set and the number of \(r\epsilon\)-tiles (or measuring sticks) needed to cover the set (where \(r\) is a scale factor which adjusts the size of the tiles/measuring sticks).
Given a self-similar fractal set \(S\) with dimension \(D\) the size of \(S\) is given by the \(D\)-dimensional measurement \[\begin{align*} L^D(S) = \lim_{\epsilon\to 0} N(\epsilon)\epsilon^D\end{align*}\] assuming that this limit exists. This means that when \(\epsilon\) is very small (close to zero) the size of \(S\) is very closely approximated by \[\begin{align*} N(\epsilon)\epsilon^D = N(r\epsilon)(r\epsilon)^D\end{align*}\] where \(r < 1\) is some scaling factor. Dividing both sides by \((r\epsilon)^D\) we are left with the following important result \[\begin{align*} N(r\epsilon) = N(\epsilon)r^{-D}\end{align*}\] which we can use to solve for the dimension, \(D\).
Going back to the von Koch curve briefly, it makes sense to let \(r = \frac{1}{3}\). Then we see that if \(N(\epsilon)\) is the number of measuring sticks of length \(\epsilon\) required to cover the von Koch curve, then \(N(r\epsilon) = N\left(\frac{1}{3}\epsilon\right) = 4N(\epsilon)\). Putting this into the scaling relation we get \[\begin{align*} N\left(\frac{1}{3}\epsilon\right) = 4N(\epsilon) = N(\epsilon)\left(\frac{1}{3}\right)^{-D}.\end{align*}\] Dividing both sides by \(N(\epsilon)\) and rearranging gives \[\begin{align*} 3^D = 4 \rightarrow D = \frac{\log(4)}{\log(3)}\end{align*}\] which is in agreement with the dimension we found previously. Okay, now it’s your turn!
Consider the following generator, \(G\).
which acts by removing the middle third of line segments. Repeated application of \(G\) results in the following fractal set, referred to as the Cantor set.
Determine an appropriate value of \(r\) and use the scaling relation to find the fractal dimension, \(D\), of the Cantor set.
Letting \(r = \frac{1}{3}\) we see that if it takes \(N(\epsilon)\) measuring sticks of length \(\epsilon\) (or \(\epsilon\)-tiles if you prefer) to cover the Cantor set, then it will take \(N\left(\frac{1}{3}\epsilon\right) = 2N(\epsilon)\) measuring sticks of length \(\frac{1}{3}\epsilon\) to cover the Cantor set.
Putting this into the scaling relation we get \[\begin{align*} N\left(\frac{1}{3}\epsilon\right) = 2N(\epsilon) = N(\epsilon)\left(\frac{1}{3}\right)^{-D}.\end{align*}\] Solving for \(D\) yields \(D = \frac{\log(2)}{\log(3)}\approx 0.63\). The Cantor set is somewhere between zero-dimensional and one-dimensional.
As we saw in the previous section, self-similar fractal sets can be constructed by a recursive procedure starting with a generator which we have thus far defined graphically. We can make this construction more precise mathematically using functions. Let’s take another look at the Cantor set from the previous exercise.
Consider the following two functions which map the interval \(I = [0,1]\) onto itself, \(f_1(x) = \frac{1}{3}x\) and \(f_2(x) = \frac{1}{3}x + \frac{2}{3}\). We will now examine the repeated action of \(f_1\) and \(f_2\) on the interval \(I = [0,1]\). Instead of looking at where each function sends a single point \(x\in[0,1]\), we will consider the action of each function sends sets of points in \(I = [0,1]\).
For instance, we see that \(f_1\) maps the point \(x = 0\) to \(x = 0\) and \(x = 1\) to \(x = \frac{1}{3}\), and all other \(x\in [0,1]\) somewhere inside this interval. We can write this as \(f_1([0,1]) = [0,\frac{1}{3}]\). In other words, \(f_1\) shrinks the interval \([0,1]\) to \([0,\frac{1}{3}]\). Similarly, we find that \(f_2([0,1]) = [\frac{2}{3},1]\).
Now, instead of considering the action of \(f_1\) and \(f_2\) separately, let’s consider them acting in unison as a parallel operator, which we will call \(F\). We define the action of \(F\) on any subset \(S\) of \([0,1]\) as follows, \[\begin{align*} F(S) = f_1(S) \bigcup f_2(S)\end{align*}\] where \(\bigcup\) denotes taking the union of two sets, i.e. joining them together. To illustrate:
The parallel operator \(F\) performs the same middle thirds dissection procedure used to produce the Cantor set. As a result, if we let \(n\) go to infinity, the limiting set will be the Cantor set.
What we just saw is an example of an iterated function system. Before we can properly define an iterated function system, we first need the definition of a contraction mapping.
Let \(D\subset \mathbb{R}\) and \(f:D\rightarrow D\) (\(f\) is a function which maps \(D\) to \(D\)). We say that \(f\) is a contraction mapping on \(D\) if there exists a constant \(0 \leq C < 1\) such that \[\begin{align*} |f(x) - f(y)| \leq C|x - y|\quad \textrm{for all }x,y\in D\end{align*}\] The smallest value of \(C\) for which the above inequality holds is called the contraction factor of \(f\).
What this definition means is that a contraction mapping \(f\) maps any two distinct points \(x\) and \(y\) in its domain closer to each other.
Consider \(f_1(x) = \frac{1}{3}x\)
and \(f_2(x) = \frac{1}{3}x +
\frac{2}{3}\) from the previous example. These are both
contraction mappings on the domain \([0,1]\). To see this, consider \(x\) and \(y\in
[0,1]\). We see that \[\begin{align*}
|f_1(x) - f_1(y)| &= |\frac{1}{3}x - \frac{1}{3}y|\\
&= \frac{1}{3}|x - y|\\
&\leq \frac{1}{3} |x - y|.\end{align*}\] So \(f_1\) is a contraction mapping with
contraction factor \(C =
\frac{1}{3}\).
Using the same approach we can show that \(|f_2(x) - f_2(y)|\leq \frac{1}{3}|x-y|\).
Thus, both \(f_1\) and \(f_2\) are contraction mappings with
contraction factor \(C =
\frac{1}{3}\).
Linear functions, like \(f_1\) and \(f_2\) above (also called affine transformations) represent familiar geometrical transformations including scaling, reflection, translation, and rotation (in two dimensions). In our construction of self-similar fractal sets we will only consider affine transformations.
Consider the linear function \(f(x) = ax + b\). Show that when \(0 < a < 1\), \(f(x)\) is a contraction mapping on the domain \([0,1]\). Determine the contraction factor of \(f\).
To show that \(f\) is a contraction
mapping, consider \(x\) and \(y\in [0,1]\). We see that \[\begin{align*}
|f(x) - f(y)| &= |ax + b - (ay+b)|\\
&= |ax - ay + b - b|\\
&= |ax - ay|\\
&= a|x-y|\\
&\leq a|x - y|.\end{align*}\] Since \(0 < a < 1\), \(f\) is a contraction mapping. The
contraction factor of \(f\) is \(a\).
Now that we are familiar with the idea of contraction mappings we can define an iterated function system (IFS) properly.
Let \(\left\{f_1,f_2,\ldots,f_n\right\}\) be a set of \(n\) linear contraction mappings on a closed and bounded subset \(D\subset\mathbb{R}\), i.e. for each \(k\in\left\{1,2,\ldots,N\right\}\), \(f_k:D\rightarrow D\) and there exists a constant \(0\leq C_k < 1\) such that \[\begin{align*} |f_k(x) - f_k(y)| \leq C_k |x-y|\quad\textrm{for all }x,y\in D.\end{align*}\] Associated with this set of contraction mappings is the parallel operator \(F\) defined as \[\begin{align*} F(S) = \bigcup_{k=1}^{n}f_k(S)\quad\textrm{for any subset }S\subset D.\end{align*}\] The set of maps \(\left\{f_1,f_2,\ldots,f_n\right\}\) with parallel operator \(F\) defines an \(n\)-map iterated function system (IFS) on the set \(D\subset\mathbb{R}\).
The parallel operation of the functions \(f_1\) and \(f_2\) defined at the beginning of this section is an IFS which when iterated indefinitely generates the Cantor set.
There exists a unique set \(A \subset D\) which is the fixed point of the parallel IFS operator \(F\) (as defined above), i.e. \[\begin{align*} A = F(A) = \bigcup_{k=1}^{n}f_k(A).\end{align*}\] Moreover, if you start with any set \(S_0\in D\) (even a single point), and form the iteration sequence \[\begin{align*} S_{n+1} = F(S_n)\end{align*}\] the sequence of sets \(S_n\) converges to the fixed-point set \(A\), which is known as the attractor.
Practically, this means that given a set of contraction maps, we can quickly construct the attractor set \(A\), allowing us to generate images of many interesting fractal sets. We have defined iterated function systems in one dimension, however we can also generalize the definition to multiple dimensions to generate more interesting pictures which lie in two and three-dimensional space. We won’t formally define this, but we will look at an example of what this looks like graphically.
The Sierpinski triangle is constructed by starting with an equilateral triangle and applying three contraction maps. The first map shrinks the triangle by a factor of \(\frac{1}{2}\), creating a smaller triangle which lines up with the leftmost corner of the original. The second map also shrinks the triangle by \(\frac{1}{2}\) and translates it to the right so that it lines up with the right most corner of the original. Finally, the third map also shrinks the triangle by a factor of \(\frac{1}{2}\) and translates it to the right and upwards so that it lines up with the top corner of the original. The result of the first few iterations of this process is shown in the figure below. From the figure, we see that the Sierpinski triangle is self-similar. It is made up of three copies of itself, each scaled by a factor of \(\frac{1}{2}\).
We could use the scaling relation to determine the dimension of the Sierpinski triangle, but it will be a little bit more difficult to work out a covering of the Sierpinski triangle with measuring sticks or tiles. Instead, we can compute something called the similarity dimension, which for a self-similar fractal set gives us the same dimensions we would get from the scaling relation.
If we consider a self-similar set which is the union of \(N\) non-overlapping copies of itself such that each copy is scaled down by a factor of \(r < 1\) , then the similarity dimension of the set is
\[\begin{align*} D &= \dfrac{\log (N)}{\log\left(\frac{1}{r}\right)} \tag{1}\end{align*}\]
Using the above definition, the dimension of the Sierpinski triangle is \[\begin{align*} D = \dfrac{\log (3)}{\log(2)}\approx 1.56.\end{align*}\] This is between one and two, as we might have expected.
