CEMC Banner

Grade 11/12 Math Circles
Dynamical Systems and Fractals Part 2 - Solutions

Exercise Solutions

Exercise 1

Consider the following generator, \(G\).

On the left is a horizontal line segment of length l. In the middle is an arrow labelled G pointing to the right. On the right is the same segment but with its middle third removed leaving a gap. The remaining left and right segments both have length equal to one-third of l.

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.

Four figures placed in a vertical column. Figure E subscript 0 is a horizontal line. Figure E subscript 1 is the previous figure with its middle third removed, leaving a left third and a right third. Figure E subscript 2 is the previous figure with the middle third of each of the left and right thirds removed. The final Figure is E subscript k and shows further segments removed.

Determine an appropriate value of \(r\) and use the scaling relation to find the fractal dimension, \(D\), of the Cantor set.

Exercise 1 Solution

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.

Exercise 2

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\).

Exercise 2 Solution

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\).

Problem Set Solutions

  1. Consider the logistic function \(f(x) = rx(1-x)\) where \(0 < r\leq 4\). In the lesson we saw (by looking at a plot of the iterates) that when \(r > 3\) this function has a two-cycle. Now, let’s show it algebraically. Last week we learned that we can solve for the period two points of \(f(x)\) by solving the expression \(f^{[2]}(\bar{x}) = \bar{x}\), however as \(f(x)\) gets more complicated this can leave us with some messy equations to solve. In this question we will work through an easier way to solve for the two-cycle of \(f(x)\).

    1. Let \(\left\{p_1,p_2\right\}\) be the two-cycle of \(f(x)\). In order for this to be a two-cycle we must have that \(f(p_1) = p_2\) and \(f(p_2) = p_1\). Use this fact to write down two expressions relating \(p_1\) and \(p_2\).

    2. Now subtract the two expressions you found in (a) and use the fact that \(p_1\neq p_2\) to simplify the resulting expression. You should end up with an expression which is linear in both \(p_1\) and \(p_2\).

    3. Finally, substitute this expression back into one of the expressions you found in (a) to solve for either \(p_1\) or \(p_2\). Use this result to show that \(f(x)\) only has a (real-valued) two-cycle when \(r>3\).

    Solution:

    1. Using \(f(p_1) = p_2\) and \(f(p_2) = p_1\) we have the following two expressions \[\begin{align*} r p_1(1-p_1) &= p_2\\ r p_2(1 - p_2) &= p_1\end{align*}\] which relate \(p_1\) and \(p_2\).

    2. Subtracting the two expressions from (a) gives \[\begin{align*} r p_1 (1-p_1) - rp_2(1-p_2) &= p_2 - p_1\\ r(p_1-p_2) - r(p_1^2 - p_2^2) &= p_2 - p_1\\ r(p_1-p_2) - r(p_1-p_2)(p_1+p_2) &= p_2 - p_1.\end{align*}\] Since \(p_2\neq p_1\) (by the definition of a two-cycle) we can divide both sides by \(p_1-p_2\), resulting in \[\begin{align*} r - r(p_1+p_2) &= -1\\ p_1 + p_2 &= \frac{1+r}{r}\\ p_1 &= \frac{1+r}{r} - p_2.\end{align*}\]

    3. Finally, we substitute our result from (b) back into one of our expressions from (a) to solve for \(p_1\) or \(p_2\). Since \(p_1\) and \(p_2\) are interchangeable in our initial formulation it doesn’t matter which one we solve for. \[\begin{align*} r p_2(1 - p_2) &= \frac{1+r}{r} - p_2\\ rp_2 - rp_2^2 &= \frac{1+r}{r} - p_2\\ rp_2^2 - (r+1)p_2 + \frac{1+r}{r} &= 0.\end{align*}\] Using the quadratic formula we get \[\begin{align*} p_2 &= \frac{r+1}{2r} \pm \frac{\sqrt{(r+1)^2 - 4r\frac{1+r}{r}}}{2r}\\ &= \frac{r+1}{2r} \pm \frac{\sqrt{(r+1)(r-3)}}{2r}.\end{align*}\] Since \(r>0\), this has two distinct (real) solutions when \(r>3\). Thus, we have a two-cycle when \(r>3\).

  2. Consider a circle \(C\) which has radius \(1\). Now consider inscribing \(C\) with a regular polygon \(P_n\) which has \(2^n\) equal sides, as shown in the figure below.

    A circle with an 8 sided regular polygon inside it with all of its vertices lying on the circle.

    The idea is that we can consider the length (\(L_n\)) of the perimeter of \(P_n\) as an approximation for the circumference (\(L=2\pi\)) of the circle \(C\).

    1. Write down an expression for \(L_n\) (the length of the perimeter of \(P_n\)).

    2. CHALLENGE (You will need to be familiar with limits in order to solve this next part.) Show that \(\lim_{n\to\infty} L_n = L = 2\pi\).

      Hint: You may work with angles in either degrees or radians (if you are familiar with radians). You will need to use the fact that \(\lim_{x\to 0} \frac{\sin(x)}{x} = 1\) (when \(x\) is in radians) or that \(\lim_{x\to 0} \frac{\sin(x)}{x} = \frac{\pi}{180}\) (when \(x\) is in degrees).

    Solution: Working with angles in degrees (solution using radians is very similar):

    1. To start, we need the length of each side of \(P_n\), which is given by \[\begin{align*} 2\cdot \sin\left(\frac{\theta_n}{2}\right) = 2\cdot \sin\left(\frac{360\degree}{2^{n+1}}\right)\end{align*}\] as seen on the following figure.

      A triangle inside the circle formed by joining both vertices of one side of the inscribed polygon to the centre of the circle. These two segments are radii of length 1. The angle of the triangle at the centre is theta subscript n which is equal to 360 degrees divided by the quantity 2 to the power of n.

      Since \(P_n\) has \(2^n\) sides, the length of its perimeter is given by \[\begin{align*} L_n &= 2^n\cdot 2\cdot \sin\left(\frac{360\degree}{2^{n+1}}\right)\\ &= 2^{n+1}\cdot \sin\left(\frac{360\degree}{2^{n+1}}\right).\end{align*}\]


    2. \[\begin{align*} L = \lim_{n\to\infty} L_n &= \lim_{n\to\infty} 2^{n+1}\cdot \sin\left(\frac{360\degree}{2^{n+1}}\right)\\ &= \lim_{n\to\infty} \frac{\sin\left(\frac{360\degree}{2^{n+1}}\right)}{\frac{1}{2^{n+1}}}\end{align*}\] Now, let \(x_n = \frac{360\degree}{2^{n+1}}\). As \(n\to\infty\), \(x_n\to 0\). \[\begin{align*} \lim_{n\to\infty} L_n &= \lim_{x_n\to 0} \frac{\sin(x_n)}{\frac{x_n}{360\degree}}\\ &= 360\degree \lim_{x_n\to 0} \frac{\sin(x_n)}{x_n}\\ &= 360\degree \cdot \frac{\pi}{180\degree} \\ &= 2\pi\end{align*}\] which gives the desired result.

  3. Consider the generator \(G\) sketched below:

    G transforms a horizontal line segment of length l into a figure of two unequal segments meet forming a tent shape. The first segment goes up to the right, meeting the second segment that then goes down to the right to a point l units from where the first segment started. The first segment has length r subscript 1 times l and the second has length r subscript 2 times l.

    where \(0<r_1 < 1\), \(0<r_2<1\) and \(1 < r_1+r_2 < 2\).

    1. Starting with the set \(J_0 = [0,1]\), sketch \(J_1 = G(J_0)\) and \(J_2 = G(J_1)\).

    2. What is the length of \(J_1\) (\(L_1\))? Of \(J_2\) (\(L_2\))? In general, can you find an expression for the length of \(J_n = G^n(J_0)\)?

    3. What do you expect to happen to the length of \(J_n\) as \(n\) gets infinitely large (i.e. as the set \(J_n\) approaches the attractor)?

    Solution:

    1. \(J_1\) and \(J_2\) are as follows

      J subscript 0 is a horizontal line segment from 0 to 1. J subscript 1 is a tent shape made from two segments: The first segment starts at 0 and has length r subscript 1 and the second has length r subscript 2 and ends ends at 1. J subscript 2 is formed by four connected line segments starting at 0 and ending at 1. Their lengths are r subscript 1 squared, r subscript 1 times r subscript 2, r subscript 1 times r subscript 2, and r subscript 2 squared.

    2. The length of \(J_1\) is \(L_1 = r_1 + r_2\).

      The length of \(J_2\) is \(L_2 = r_1^2 + 2r_1 r_2 + r^2 = (r_1 + r_2)^2\).

      In general, \(G\) scales the length of each line segment by a factor of \(r_1 + r_2\) so we can write \(L_n = (r_1+r_2)^n\).

    3. Since \(r_1 + r_2 > 1\), \(\lim_{n\to\infty} L_n = \lim_{n\to\infty} (r_1 + r_2)^n = \infty\). In other words, as \(n\) gets infinitely large, the length of \(J_n\) will approach infinity (meaning that the attractor has infinite length).

  4. Consider the following two function iterated function system (IFS) on \([0,1]\), \[\begin{align*} f_1(x) = \frac{1}{5}x,\quad f_2(x) = \frac{1}{5}x + \frac{4}{5}.\end{align*}\]

    1. Let \(I_0 = [0,1]\) and \(I_1 = F(I_0)\) where \(F\) is the parallel IFS operator composed of the two functions \(f_1\) and \(f_2\). Sketch \(I_1\) on the real number line.

    2. Let \(I_2 = F(I_1)\). Sketch \(I_2\) on the real number line.

    3. Let \(I\) denote the limiting set (or attractor) of this IFS. Use the scaling relation to determine the fractal dimension \(D\) of \(I\).

      Hint: \(D\) will be a ratio of two logarithms.

    Solution:

    1. \(I_1\) is as follows

      Two intervals: the first is the interval from 0 to one-fifth, which is the function lowercase f subscript 1 applied to I subscript 0; the second is the interval from four-fifths to 1, which is the function lowercase f subscript 2 applied to I subscript 0.

    2. \(I_2\) is as follows

      Four intervals: the first two are 0 to one twenty-fifth and four twenty-fifths to one fifth, which is the function lowercase f subscript 1 applied to I subscript 1; the second two are four fifths to twenty-one twenty-fifths and twenty-four twenty-fifths to 1, which is the function lowercase f subscript 2 applied to I subscript 1.

    3. Letting \(r = \frac{1}{5}\) we see that \(N(r\epsilon) = 2N(\epsilon)\) (one measuring stick of length one, two of length \(\frac{1}{5}\), four of length \(\frac{1}{25}\), etc...). Putting this into the scaling relation we get \[\begin{align*} N\left(\frac{1}{5}\epsilon\right) = 2N(\epsilon) = N(\epsilon)\left(\frac{1}{5}\right)^{-D}\end{align*}\] which implies \[\begin{align*} 2N(\epsilon) &= N(\epsilon)\left(\frac{1}{5}\right)^D\\ 2 &= 5^D\\ D &= \frac{\log(2)}{\log(5)}\approx 0.43.\end{align*}\]

  5. Show that the function \(f(x) = x^2\) is a contraction mapping on the domain \([0,\frac{1}{4}]\). Determine the contraction factor of \(f\).

    Solution: Let \(x,y\in\left[0,\frac{1}{4}\right]\). Then \[\begin{align*} |f(x) - f(y)| &= |x^2 - y^2|\\ &= |x + y||x - y|\\ &\leq \frac{1}{2} |x-y|.\end{align*}\] Therefore \(f\) is a contraction mapping with contraction factor \(\frac{1}{2}\) on the domain \(\left[0,\frac{1}{4}\right]\).

  6. Consider the image of the Sierpinski carpet, \(S\), shown below. The Sierpinski carpet is a self-similar fractal which means that is a union of contracted copies of itself.

    1. Show (by circling them on the figure) that \(S\) is made up of eight contracted copies of itself. What is the contraction factor of these copies?

    2. Determine the similarity dimension of \(S\).

    Solution:

    1. We see that there are eight contracted copies of \(S\), as shown on the following figure. We can also see from the figure that each copy of \(S\) is scaled down by \(\frac{1}{3}\), or has a contraction factor of \(\frac{1}{3}\).