## The Newton Method

I kind of think of it as a song, “you put your P(z) in, you take your P'(z) out, you minus all from Zn and you get your Zn+1 out.” Alright, that might be a weak attempt to make an equation into song. Here’s the Newton Method equation (from Wikipedia):

Each time you calculate a new Zn+1 you plug it back into the equation until you find (within a small margin of error) the root of the equation p(z). Here is an image from wikipedia:

This is simple enough to do, however problems can occur if a horizontal asymptote is created by the p(z) or p'(z) equations. Therefore, we must keep that in mind whilst calculating/programming using newtons method.

## Complex Numbers

To understand generates a fractal it is first required to understand the basics of complex numbers. Put simply a complex number is represented as the following, a + *i*b. Where ‘a’ represents a *real* number represented via our normal numerical representations and ‘b’ represents an *imaginary* number, not representable in the real world. Visually (picture taken from wikipedia):

*i*represents √-1. Therefore,

*i * i = -*1. This is all the background knowledge required to understand how a Newton Fractal work.

## Newton Fractals

Now that we have a rudimentary understanding of Newtons Method we would like to venture into the world of fractals. In essence a is a mathematical set that typically displays self-similar patterns, which means it is “the same from near as from far.” Or to paraphrase Benoit Mandelbrot:

Fractals are geometric objects with fractional dimensions rather than integer dimensions.

One of the ways we can display fractional dimensions is by using complex numbers. I’ll forgo the math at this point and leave the gory details for some later post. The following is an example of a fractal which should create a pretty picture, we use the following method:

- Given an equation F(Z), such as f(Z) = z^3 – 1, insert different pixel positions (x, y) into z = x +
*i*y. - Use Newtons method on Z to calculate the root for the given location
- Iterate over every pixel in the x by y image.
- If you pick an equation F(Z) with a given number of roots (such as 3) you can color each root a different color and make interesting pictures.

Here is the some python code to create some fractals, you can run this yourself on github (but not on OSX):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
# Example z^3 - 1 & z^2 - 2z - 2 fractal # Written by Austin Walters from PIL import Image # -1 <= x <= 1 x_min = -1.0 x_max = 1.0 # -i <= y <= i y_min = -1.0 y_max = 1.0 colors = [\ (180, 0, 30), (0, 180, 30), (0, 30, 180), \ (0, 190, 180), (180, 0, 175), (180, 255, 0), \ (155, 170, 180), (70, 50, 0), (255, 255, 255)] def cubed(z): return z * z * z - 1.0 def dcubed(z): return 3.0 * (z*z) def squared(z): return (z*z) - (2.0 * z) + 2.0 def dsquared(z): return 2.0 * z - 2.0 def cubedplus(z): return z * z * z - 2.0 * z + 2.0 def dcubedplus(z): return 3.0 * z * z - 2.0 def fun(z): return (z*z*z*z*z*z) - (z*z*z) + 2.0 def dfun(z): return 6.0 * (z*z*z*z*z) - 3.0 * (z*z) def fifth(z): return (z*z*z*z*z) - (z) def dfifth(z): return 5.0 * (z*z*z*z) - 1 def newtons_method(f, f_prime, z): # Fourty iterations for safe measure for i in range(40): zplus = z - f(z)/f_prime(z) # Checks for Overflow if abs(f(z)) > 10e10: return None # Checks for underflow if abs(f(z)) < 10e-14: return None # Checks for convergence if abs(zplus - z) < 10e-4: return z z = zplus return None # Draws the functions def draw(f, f_prime, img, size, img_name): roots = [] for y in range(size): z_y = y * (y_max - y_min)/(size - 1) + y_min for x in range(size): z_x = x * (x_max - x_min)/(size - 1) + x_min root = newtons_method(f, f_prime, complex(z_x, z_y)) if root: flag = False for test_root in roots: if abs(test_root - root) < 10e-3: root = test_root flag = True break if not flag: roots.append(root) if root: img.putpixel((x, y), colors[roots.index(root)]) print roots img.save(img_name, "PNG") size = 1024 img = Image.new("RGB", (size, size), (255, 255, 255)) draw(lambda z: cubed(z), lambda z: dcubed(z), img, size, "fig1.png"); draw(lambda z: squared(z), lambda z: dsquared(z), img, size, "fig2.png"); draw(lambda z: fun(z), lambda z: dfun(z), img, size, "fig3.png"); draw(lambda z: cubedplus(z), lambda z: dcubedplus(z), img, size, "fig4.png"); draw(lambda z: fifth(z), lambda z: dfifth(z), img, size, "fig5.png"); |

### Output:

**Function: z^3 – 1**

**Function: z^2 – 2z + 2**

**Function: z^6 – z^3 + 2**

**Function: z^3 – 2z + 2**

**Function: z^5 - z**

He blogs, he writes songs, he bathes hairless cats (or at least he will) — what can’t Austin do? I was going to make a very clever comment about Newton’s method being “just binary search,” but the more I think about it, the more confused I become. Such is life.

It is very similar to binary search, however there is not a guarantee of convergence. Meaning it could take an infinitely long time to converge, as opposed to O(logN) worst case runtime for binary search. Further, because you can potentially have a function which produces a VERY squiggly line making it take a VERY long time for convergence.

The Weierstrass function comes to mind — “I recoil with fear and loathing from that deplorable evil, continuous functions with no derivative.”