What is Newton's Method?
Newton's Method is an algorithm for finding the roots and/or zeros of a function. Most commonly it is used to find the roots (and consequently zeros) of a polynomial function. Therefore it is also very useful for factoring complicated polynomial equations. It can be applied to almost any polynomial and only fails under a few rare circumstances. It works in both the real and complex numbers. So one can also find the imaginary roots of a function, which many polynomials have.
How Does it Work?
Newton's Method is a rather simple algorithm which can be used by anyone who knows a little calculus. One uses the equation f(x1) = x0 - f(x0) / f '(x0) . Starting with an initial point or guess x0 one can now find x1 using the previous equation. This can be repeated n times until xn is found and it is within the desired accuracy of the actual root or in other words f(x0) close enough to zero. This can also be thought of graphically. Starting at x0 draw a line up or down to f(x) then compute the the tangent at that point and draw the tangent to f(x) at x0 . Where the tangent intersects the x-axis this is x0 , now draw a line up or down to f(x0) and repeat the process. See picture below.
Given that x0 is sufficiently close enough to the root it will eventually converge on the root. If x0 is not sufficiently close enough to guarantee convergence then Newton's Method may jump around erratically until it lands on some point xn that will converge on some root. So many points on the real line or complex plane Newton's method will converge on a root that is determined by the starting point, however in certain regions it is impossible to tell what root will be found.
Newton's Method is not perfect, there are cases where it fails. Both the f(x) and f '(x) must be continuous and smooth, since my program will only examine polynomials this is not a problem. One case where it fails is when f '(x) is zero. This causes the formula to fail, because dividing by zero is very bad. If f '(x) is infinite then it also fails because xn+1 = xn and the algorithm stops finding new points. There are also some functions or regions of functions that will cause the algorithm to shoot off to infinity. See picture of the function x1/3 below.
There are also regions where the algorithm will land on a point which send it to another point. Due to the slope and position of the new point the algorithm now jumps back to the previous point. This continues forever. Lastly the algorithm may fail due to laziness, it may just take more iterations than someone is willing or a computer is programmed to compute, for it to come close enough to a root.
In the Complex Plane
Newton's method is very useful for finding roots but is not to terribly complicated, right? Well not exactly. If you were to take a polynomial, for example f(x) = x3 - x , which has the roots -1, 0, 1, and applied Newton's Method between -1 and 1 on the real number line moving in very small increments, you would find something that may not expect. Instead of finding 3 distinct regions where the algorithm always converges to the same root it suddenly changes. If you were to divide up those regions into smaller increments and apply Newton's method again you would find that between the first two points where it changed there are even more boundaries where it changes. Infact there are infinitely more regions between every two regions. So what used to be a boundary between two regions of convergence is now a mini universe of more boundaries and regions. Upon close examination you may notice some pattern or self similarity, something fractal perhaps?
It is indeed fractal, but it is hard to recognize until you examine Newton's Method over the complex plane. As I said before Newton's Method can be used in the complex plane just as it is used with real numbers. Functions over the complex plane, f(x,yi) = z, create a surface similar to f(x,y) = z with real numbers. Derivatives can be taken with complex arguments and real algebraic computations all have parallels with complex numbers. In the complex plane where all of polynomials roots exist and the regions of convergence, called basins hereafter, are two dimensional areas, the fractal nature of Newton's Method becomes very obvious. Every border between the basins has an infinite number of other basins in it.
Fractal Behavior
There is no proof on this site that Newton's Method is indeed fractal on the complex plane but I will discuss some of the fractal characteristics that many fractals share. Self similarity. If you were to pick a spot on a fractal and zoom in again and again you would notice that on every level the fractal has similar features. Sometimes slightly changed, sometimes a perfect copy, but always recognizable. Like standing on a coastline and zooming out. A small rock is an island to a big rock, the big rock to boulder, the boulder an island, to a continent. Many fractals, especially fractals like Julia sets and Newton's method, exhibit "infinite" boundaries. In a border between two basins there exists infinitely more basins and and borders with again more basins and so on. The Wada Property is a parallel of this idea derived from topology. Newton's Method is also an perfect example of sensitive dependence on initial conditions, which is the cause of much fractal behavior. At one point you converge to a certain root but move over 1E-15 units and it will converge to a different root. These sudden changes may seem random but when examining a larger area a pattern emerges. An analogy is rain falling on the Rockies, which ocean a drop ends up in is dependent on exactly where it lands. Some areas it obviously flows one way and so do the drops around it. But at ridge line the slightest change in position will determine its final ocean.
More on Newton's Method - These links should fill in any gaps I missed