Newton's Method Fractal

Sat, 22 Sep 2007

I'm not sure if this falls under my usual definition of graph (but my usual definition of graph doesn't agree with answers.com either, so meh). So, you can decide for yourself if it is a graph or not. In any case, it is about as useful as my other graphs.

In highschool we were taught a way of finding the roots of an equation using Newton's Method. For the non-mathsy people, if you have an equation, like y = x + 5, then you can draw it as a picture, where all the points where the 'y' coordinate is 5 more than the 'x' coordinate are black and everything else is white. In this case, it would be a diagonal line. A root is a place where y is 0 (so x = -5 in this case). Newton's method is a method for taking a guess at where a root might be, and then (hopefully) improving that guess. It looks at the slope of the line at the point you have guessed, and then assumes that the line doesn't get any steeper or shallower, and finds where it would hit the point where y = 0. This is the revised guess. In the case of y = x + 5, it will find the exact root straight away (because the slope doesn't change). For more complicated functions, it will usually just get closer and closer to the actual root (as you keep on guessing, using the last revised guess as the starting point).

When you have a function that has multiple roots (a squigly line that goes through the y = 0 line multiple times, you can theoretically end up converging towards any of the roots, though you are more likely to end up at one close to where you start from.

The final piece of the puzzle you need to know is that Newton's method works for complex numbers too (for the non-mathsy people... complex numbers aren't complex as long as you don't think too hard about them. If you think of numbers as having a left (negative) and a right (positive), complex numbers give them an up and a down, so a number is a point in 2D space, rather than a point on a 1D number line).

So, if we take a function with lots of roots - cos (which has an infinite number of roots) and find where we converge to from different starting points, we can get a cool picture. We just need some way to show which point goes to which root. Since the roots are spread apart by 3 and a bit, I just chopped off all the stuff after the decimal point, and then found the remainer when dividing by some constant:

Picture of which root Newton's method resolves to for cos(z), z near 0

I'm not the first to do this. This person has done it, and made this cool picture for y = x^3 - 1, which has 3 roots, which they have coloured red, green, and blue).

One thing which I thought would be fun to do though was to zoom in on it, and make an animation, so this is that animation:

What is especially cool is the frames that have purple in them, which I have no idea about (they are a bug), the thumbnail (if you can find it) (which also has the crazy purple), and the fact that it chopped off the end of the video. Actually, the last one isn't cool. Sometimes failure can be interesting (where did this purple come from?), and sometimes it can be boring (where did the last bit of the animation go?). I don't think I know enough about making these videos to fix it, so I'll just leave it as is.

Name & email are optional. Email will not be obfuscated.
HTML tags will be removed except hyperlinks.
 

About

I'm a nerd living in Sydney. This is a place where I can write stuff about my interests and not care that no one else is reading.

I like music, maths, programming, pretty pictures, filters and other good things.

(more info)

It should be fairly obvious that this isn't connected to my employer at all.

Email me (not a catchpa)

Email policy

Subscribe

RSS Feed RSS

Get an aggregator

Liferea (Linux)

Vienna (OSX)

Feedreader (Windows)

Google Reader (Web based)

I've only used Liferea, so I can't vouch for the other ones.

About this site

This site runs a (modified) version of blosxom.

The host is GeekISP, and they seem to do an excellent job.