Chaos and Fractals

We start with \(f(x)=x^2-2\text{.}\) Of course, \(f\) has two roots, namely \(\pm\sqrt{2}\text{.}\) Thus, we might think, of the application of Newton's method to \(f\) as a tool to find good approximations to \(\sqrt{2}\text{.}\)

First, we compute \(N\text{:}\)

Now, suppose that \(x_0=1\text{.}\) Then,

Note that

so that third iterate is quite close to \(\sqrt{2}\text{.}\)

Note that we've obtained a rational approximation to \(\sqrt{2}\text{.}\) At the same time, it's clear that it would be nice to perform these computations on a computer. In that context, we might generate a decimal approximation to \(\sqrt{2}\text{.}\) Here's how this process might go in Sage:

Of course, \(f\) has two roots. How can we choose \(x_0\) so that the process converges to \(-\sqrt{2}\text{?}\) You'll explore this question computationally in Exercise 1.3.1. It's worth noting, though, that a little geometric understanding can go a long way. Figure 1.1.4, for example, shows us that if we start with a number \(x_0\) between zero and \(\sqrt{2}\text{,}\) then \(x_1\) will be larger than \(\sqrt{2}\text{.}\) The same picture shows us that any number larger than \(\sqrt{2}\) leads to a sequence that converges to \(\sqrt{2}\text{.}\)

We now take a look at \(f(x)=x^2+3\text{.}\) A simple look at the graph of \(f\) shows that it doesn't even hit the \(x\)-axis; thus, \(f\) has no roots. It's not at all clear what to expect from Newton's method.

A simple computation shows that the Newton's method iteration function is

Note that \(N(1)=-1\) and \(N(-1)=1\text{.}\) In the general context of iteration that we'll consider later, we'll say that the points \(1\) and \(-1\) lie on an orbit of period 2 under iteration of the function \(N\text{.}\)

Sequences of other points seem more complicated so we turn to the computer. Suppose that we change the initial seed \(x_0=1\) just a little tiny bit and iterate with Sage.

Well, there appears to be no particular pattern in the numbers. In fact, if we generate 1000 iterates an plot those that lie within 10 units of the origin on a number line, we get Figure 1.1.6. This is our first illustration of chaotic behavior. Not just because we see points spread all throughout the interval but also because we appeared to have a stable orbit when \(x_0=1\text{.}\) Why should the behavior be so different when we change that initial seed to \(x_0=0.99\text{?}\)

Newton's original example had one real root, Example 1.1.3 had two real roots and Example 1.1.5 had no real roots. Let's take a look at an example with lots real roots, namely \(f(x)=\cos(x)\text{.}\)

Generally, the closer your initial seed is to a root, the more likely the sequence starting from that seed is to converge to that root. What happens, though, if we start some place that's not so close to a root? What if we start close to the maximum - near zero? Let's investigate in code.

OK, let's pick this code apart. The inner for loop looks like so:

xi = random()/10
for i in range(8):
    xi = N(xi)

Figure 1.1.8 gives some clue as to what's going on. Recall that we can envision a Newton step for a function \(f\) from a point \(x_i\) by drawing the line that is tangent to the graph of \(f\) at the point \((x_i,f(x_i))\text{.}\) The value of \(x_i\) is then the point of intersection of this line with the \(x\)-axis. Because the slope at the maximum is zero, the value of this point of intersection is very sensitive to small changes. In fact, there are infinitely many roots of the cosine any one of which could be hit by some initial seed in this tiny interval.

Let \(p(z)=z^2+3\text{.}\) We already played with this function in the real case back in Example 1.1.5 and the computer indicated that there might be chaos on the real line. When we allow complex inputs, though, there are two roots - one at \(\sqrt{3}i\) (above the real axis) and one at \(-\sqrt{3}i\) (below the real axis). If the process always converges to the root that is closest to the initial seed, then seeds in the upper half plane should converge to \(\sqrt{3}i\) while seeds in the lower half plane should converge to \(-\sqrt{3}i\text{.}\) We don't have the tools to prove this yet, but we can investigate with Algorithm 1.1.9. The result is shown in Figure 1.1.11.

Let \(p(z)=z^3 - 1\text{.}\) As a complex, cubic polynomial, we expect \(p\) to have three roots. It's easy to see that \(z=1\) is a root. This means that \(z-1\) is a factor, which makes it easier to find that

We can then apply the quadratic formula to find that the other two roots are

Note that all three roots can be clearly seen in Figure 1.1.13, which shows the result of Algorithm 1.1.9.

Let \(f(z)=\cos(z)\text{.}\) Of course, we played with the real cosine back in Example 1.1.7. There, we saw that in any tiny interval containing zero, an initial seed might converge to any of infinitely many roots. In the complex case, the basins of attraction are shown in Figure 1.1.15, and a zoom is shown in Figure 1.1.16.

Two more incredible pictures! Note the periodicity in Figure 1.1.15. Each root seems to have its own column of attraction. The boundaries between the basins are again very complicated. In the zoom of Figure 1.1.16, t looks like there's an infinite sequence of circles collapsing on either side of the origin. This agrees with our observations in the real case of Example 1.1.7.