The Unapologetic Mathematician

Mathematics for the interested outsider

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 x where f(x)=0 for some function f. 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 x_0 we have the point (x_0,f(x_0)) 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 y=f'(x_0)(x-x_0)+f(x_0). Now we want to find the x_0 where this line crosses the x-axis. That is: 0=f'(x_0)(x_1-x_0)+f(x_0). Some algebra tells us that x_1=x_0-\frac{f(x_0)}{f'(x_0)}.

Now I’m not saying that x_1 is our desired zero, but hopefully it’s closer. Then we just run this again. If we define g(x)=x-\frac{f(x)}{f'(x)} we can write x_1=g(x_0). And then we continue by writing x_2=g(g(x_0))=g^2(x_0), where the exponent means we evaluate the function g twice. This goes on, defining an infinite sequence of points x_n=g^n(x_0), and the hope is that this will zoom in on a zero of the function.

Well, zeroes of the function f are fixed points of this map. Indeed, if f(\xi)=0 then g(\xi)=\xi-\frac{0}{f'(\xi)}=\xi. We have other tools that tell us a fixed point \xi of a function will attract nearby points if |g'(\xi)|<1. And here, g'(x)=\frac{f(x)f''(x)}{f'(x)^2}. Since f(\xi)=0, we see that g'(\xi)=0<1, so near these fixed points the map g does indeed pull points closer.

But there’s a problem. What happens when f'(x)=0? Then the function g 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 f(x)=x^3-1, so we’re trying to find the three points on the complex plane that have cube 1. We know that one is 1 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 1, 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 z=0 where all three basins touch each other, leading to the famous self-similarity that is characteristic of fractal geometries.

About these ads

September 19, 2007 - Posted by | Uncategorized

11 Comments »

  1. The post is getting a lot of “Formula does not parse”.

    Comment by Michael | September 19, 2007 | Reply

  2. My instinct is that the fractal (i. e. self-similar) nature of the picture comes from the fact that it has to be its own image under the map c -> c – f’(c)/f(c), which is analytic when f(c) is nonzero.

    Comment by Isabel | September 19, 2007 | Reply

  3. Nifty! How was the picture constructed? I’d like to try plugging in different functions and seeing what I get.

    Comment by Charles | September 19, 2007 | Reply

  4. Wow! Cool conference title! Real physics with category theory! I think that’s a first.

    Comment by Kea | September 20, 2007 | Reply

  5. Isabel, you’re exactly right — except for accidentally putting the derivative over the function rather than the other way around. I decided not to explain exactly why every neighborhood of every boundary point contains points from each basin of attraction. Partly it’s because I’m not an analyst, partly because I was a bit pressed for time, and partly because this is also a Carnival submission, and I wanted to keep the level down a bit.

    Charles, to be honest I constructed the picture by doing a Google image search and looking for something that looked free. It shouldn’t be that hard, though.

    Pick an \epsilon where if a point is closer to a zero than that you know it gets pulled in. Then make a lattice of complex points and start iterating. If you land within \epsilon of a zero in n iterations, convert 255-n to hexadecimal xx and color the point #xx0000, #00xx00, or #0000xx, depending on which zero it’s near. At 255 iterations, just color it black.

    Comment by John Armstrong | September 20, 2007 | Reply

  6. Hi John,

    1 – I first saw Newton’s Method for x^4-1 in the color slide section of James Gleick, ‘Chaos: making a new science’, 1987, Penguin Books.
    ISBN 0 14 00.9250 1

    This is an image of Newton’s Method for x^6-1.
    [Be sure to look below the title, since the picture above is for Pendulum and Magnets simulation.]

    http://www.math.cornell.edu/~dynamics/FA/FA2.html

    I always thought that the exponent was related to the number of “dimensions” or degrees of freedom?

    2- RE: your September 19th, 2007 at 6:21 pm comment in post ‘The crossing number inequality’ at What’s new.

    I agree with you if all “dimensions” always have to be spatial.

    However, what if some “dimensions” or degrees of freedom are not spatial, such as strategies [or even scalars], as one sometimes finds in mathematical game theory?

    Comment by Doug | September 20, 2007 | Reply

  7. This is so funny; I made my master’s degree essay or presentation on this topic years ago. I don’t remember too much of the details; I made pictures on the computer and it was very easy to do. All of the polynomials I tried produced pretty fractals. And then when you look closer, for some polynomials it produces totally black areas. In those areas the Newton’s method totally fails and is cyclic, or for those initial points, the iterative sequence just “jumps” from one area to another and another in a cyclical manner.

    Copying from my old dissertation, here’s one such polynomial;

    z -> z^3 + (0.275 – 1 + 1.65i)z – 0.275 + 1 – 1.65i

    Don’t ask me how I found it; I can’t remember. Probably just playing around on the computer. Anyway it should produce a Julia set that has these black areas.

    There has to be an easy tool on the internet where you just plug in the Newton’s method function to iterate it and make the pictures.

    Comment by Maria Miller | September 22, 2007 | Reply

  8. I found an online tool for generating them!

    http://aleph0.clarku.edu/~djoyce/newton/newtongen.html

    You have to enter the roots of the polynomial to it, and not a general equation.

    Comment by Maria Miller | September 22, 2007 | Reply

  9. [...] a Paper Long-time readers may remember that back in September I went to a conference at the University of Texas at Tyler. Well, it turns [...]

    Pingback by Drafting a Paper « The Unapologetic Mathematician | February 22, 2008 | Reply

  10. [...] is sort of like Newton’s method, where we express the point we’re looking for as the fixed point of a function, and then find [...]

    Pingback by The Picard Iteration « The Unapologetic Mathematician | May 5, 2011 | Reply

  11. [...] a different proof that the Picard iteration converges — one which is closer to the spirit of Newton’s method. In that case, we proved that Newton’s method converged by showing that the derivative of the [...]

    Pingback by Another Existence Proof « The Unapologetic Mathematician | May 10, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 392 other followers

%d bloggers like this: