19 January 2009

Newton's method fractals

Simon Tatham has produced fractals derived from Newton-Raphson iteration which are quite interesting to look at.

The main idea here is that if you want to find a root of some function f, then you start from a guess a0; then compute a1 = a0 - f(a0)/f'(a0); geometrically this corresponds to replacing the graph of the function with its tangent line at (a0, f(a)0) and finding the root of the tangent line. Then starting from a1 we find a2 and so on. If you're already close to a root you'll get closer. But if you're far away from a root unexpected things can happen; the set of all starting points a0 for which the sequence (a0, a1, a@, a3, ...) converges to a given root of f is fractal.

(I've mentioned this before, and so has John Armstrong, but Tatham's pictures are better.)

No comments: