The Sumerian Mathematicians, some 4000 years ago had a way by which they could compute the square root of a number. And guess what, they did it by a one-step feedback iterative process! Given a number a, Öa can be computed by the following iterative process,

xn+1 = 1 2 (xn + a xn ). (1)

For a given initial guess, x₀, iterate the equation and the sequence of iterates soon converges to the square root of a. The above method of finding the square root of a number is a special case of a more general method of finding the roots of a nonlinear equation, discovered 4000 years later, called the Newton's root finding method!

NEWTON'S METHOD

Newton's method is an iterative procedure for finding the solution of the equation F(x) = 0 by successive approximations, given an initial guess. From the initial guess, say x₀, a better approximation to the solution is found by iterating the following equation,

xn+1 = xn - F(xn) F¢(xn) , (2)

where F^¢(x_n) stands for the derivative of the function F(x) whose roots are to be found. Provided, the first derivative exists, the iterates of the feedback process progressively approaches the solution.

Sir Arthur Cayley, in 1879, considered Newton's method and asked, which zero of the equation z³ - 1 = 0 in the complex plane would the method converge towards if one starts with an arbitrary initial guess. Much of Julia's work was motivated by Cayley's paper. Sixty years later, Mandelbrot aware of the work done by Pierre Fatou and Gaston Julia on iterative processes in complex plane laid the foundation of Fractal Geometry.

So much so for 4000 years of history! So what is the deal with determining to which root the Newton's method would converge if one started with an arbitrary initial guess. Sure enough Newton's method works and most 'assuredly' the process leads to one of the three solutions (incidentally the roots of the equation z³ - 1 = 0 are 1, exp^2pi/3 and exp^4pi/3). So, the question is: if one were to start with a large number of points in the complex plane as an initial guess to the Newton's method, how are these initial guess points distributed in the complex plane. Here is a color coded distribution of initial guesses that lead one of the three solutions from a computer experiment of the 500x500 grid in the complex plane, between -2 and 2 both along the real (X-) and imaginary (Y-) axis. The initial guesses are colored red, yellow or blue depending upon whether the initial points approached the solution 1, exp^2pi/3 or exp^4pi/3, respectively. The coordinates of the three roots are marked by the + symbol.

In the language of dynamical systems theory the roots can be considered as point attractors and the regions of the complex plain that asymptote to a particular root is called the basin of attraction of that root. It is clear from the plot above that there is a very complex boundry separating the basins of attraction of the three roots. This complexity continues to exist even when looking at very small differences between initial values of the guess; this boundary never becomes smooth even at very small differences. Thus, if we were to zoom in a close-up the boundaries have a very complicated structure. which has similarity to a Cantor set. In other words, wherever two basins seem to meet, we discover upon closer examination that the third basin of attraction is there in between them, and so on ad infinitum. This complex boundary is a fractal boundary. The competition of the roots over all the points in the plane, is far from simple!

HALLEY'S METHOD