Newton Basin Fractals

Newton's method provides an efficient way to approximate solutions to equations of the form $f(x)=0$. Suppose you start with a value $x_1$ that you believe to be close to a root. The line tangent to the curve $y=f(x)$ through the point $(x_1,f(x_1))$ is pretty close to the curve, so wherever that line crosses the $x$ axis should be pretty close to the root. Suppose we call this point $x_2$. The tangent line's equation, of course, can be found using the derivative of $f(x)$, and is given by:

$$y=f'(x_1)(x - x_1) +f(x_1)$$

To find $x_2$, we let $y=0$ and solve for $x$, yielding:

$$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}$$

So now we have $x_2$, a value which hopefully is even closer to the root than $x_1$. By repeating the process above on $x_2$, we can find $x_3$, which is likely to be closer still:

$$x_3 = x_2 - \frac{f(x_2)}{f'(x_2)}$$

In a similar manner, we can produce $x_4$, $x_5$, etc... which should provide better and better approximations for the actual root we seek.


Newton's method works great, provided our initial value of $x_1$ is "close enough" to the root in question - much like water poured in a water basin is guaranteed to run straight towards the drain. However, when the initial value of $x_1$ isn't close enough to the root, what happens can be a little strange. For example, we might end up a an entirely different root altogether - or worse yet, we might never converge to a root at all!

Newton's method isn't limited to functions that only operate on real values -- functions with complex domains will work too. We could, for example, use Newton's method to approximate the four roots of $f(z) = z^4-1$ (i.e., $\pm 1$ and $\pm i$), by picking appropriate initial values of $z_1$ that are "close enough" to the roots. Finding the complex roots of this function is not the interesting piece, however -- they are easy enough to find by hand for this function. Instead, we would like to get a better understanding of what goes on at the edges of the "Newton basins", where we aren't really close to any one root.

Write a Java class named Newton to examine a uniform distribution of points in the section of the complex plane where the real part and the complex coefficient are bound between -2 and 2. Each of the points examined should successively be used as the initial value in a sequence $\{z_i\}$ where

$$z_{i+1} = z_i - \frac{f(z_i)}{f'(z_i)}$$

Recall, if $f(z)=z^4-1$, then $f'(z) = 4z^3$.

If the sequence approaches $1$, color the initial point red; if it approaches $-1$, color it blue; if $i$ is approached, color it yellow; and if $-i$ is approached, color the initial point green. If everything goes as planned, you should end up with an image like this: