Newton Fractals

As soon as I’m done teaching today, I’m heading on the road to scenic Tyler, TX for the Conference on Representation Theory, Quantum Field Theory, Category Theory, Mathematical Physics and Quantum Information Theory. And so something light, that I actually presented to my students last week.

Many of you may be familiar with this from calculus, but at least it’s more interesting than L’Hôpital’s rule. For those who haven’t seen it, this post is outside the main line. Accordingly, I’m willing to leave some of the calculus unmotivated and unexplained.

Newton’s Method is an attempt to find a point where for some function . The basic idea is that we pick a point near where we think there’s a zero of the function and assume that the graph of the function is sort of sloping towards the zero. Functions on their own are sort of hard to work with, but we know how to deal with linear functions pretty well. We’ll try to pretend the function is just linear and work from there.

So if we start at the point we have the point on the graph above it. Then we draw a straight line that just touches the graph at that point. Calculus tells us that this line has the equation . Now we want to find the where this line crosses the -axis. That is: . Some algebra tells us that .

Now I’m not saying that is our desired zero, but hopefully it’s closer. Then we just run this again. If we define we can write . And then we continue by writing , where the exponent means we evaluate the function twice. This goes on, defining an infinite sequence of points , and the hope is that this will zoom in on a zero of the function.

Well, zeroes of the function are fixed points of this map. Indeed, if then . We have other tools that tell us a fixed point of a function will attract nearby points if . And here, . Since , we see that , so near these fixed points the map does indeed pull points closer.

But there’s a problem. What happens when ? Then the function is undefined, and the method breaks down. Almost as bad, near those points the tangent line is almost flat, and so the next point in the sequence ends up very far away, possibly nearer a different zero than the one we were trying to find.

Here’s a picture to show how complicated this can get. In this picture, we’re moving from calculus over the real numbers to calculus over the complex numbers, but the mechanics of Newton’s Method work the same. We consider the function , so we’re trying to find the three points on the complex plane that have cube . We know that one is itself, and the other two are situated a third of a rotation around the unit circle in either direction.

We get the picture by picking a complex number to start with, and running the method until we’re within some very small distance of one of our zeroes, so we know we’re going to get to that one in the limit. If we end up at , we color the point blue. The points which go to the other two zeroes we color green and red, respectively. We color a point darker if it takes longer to get near one of the zeroes.

We’d hope that starting at a given point would land us at the closest of the three zeroes, but borders here are tricky. We can never have a boundary between two of these basins of attraction without having the third one there too. So along the line separating the blue basin from the red one we have a chain of green islands. Similarly, we have red islands between blue and green, and blue islands between red and green. And then along the boundary a green island shares with the big blue basin we have a chain of smaller red islands, and so on. The upshot is that every boundary point looks like the point at where all three basins touch each other, leading to the famous self-similarity that is characteristic of fractal geometries.