Newton’s method and fractals

Many of you would have come across the Newton-Raphson iterative technique of finding the root of a single non-linear equation, $f(x)=0$ in high-school.

The iterative method of solution is essentially given by,

$x_{k+1}= x_{k} - \frac{f(x_k)}{f'(x_k)}, \quad k=0,1,2,....$

Newton’s method can also be extended to find solutions to a set of simultaneous non-linear equations for functions of many variables.

For example, let’s say you need to find a solution to the equations,

$\begin{cases} f_1(x_1,x_2,...,x_n)=0 \\ f_2(x_1,x_2,...,x_n)=0 \\ ... \\ f_n(x_1,x_2,...,x_n)=0 \end{cases}$

with an initial guess, $\bf{x} = (x^0_1,x^0_2,...,x^0_n)$

The recursion which is used to find the solution is now given by

$\bf{x}^{(k+1)} = \bf{x}^{(k)} - [\bf{J}(\bf{x}^{(k)}]^{-1} f(\bf{x}^{(k)}), \quad k=0,1,2,...$

That is,

$\left(\begin{array}{c} x^{(k+1)}_1 \\ x^{(k+1)}_2 \\ . \\x^{(k+1)}_n \end{array} \right) = \left( \begin{array}{c} x^{(k)}_1 \\ x^{(k)}_2 \\ . \\x^{(k)}_n \end{array} \right) - \left( \begin{array}{cccc} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & . & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & . & \frac{\partial f_2}{\partial x_n} \\ . & . & . & . \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & . & \frac{\partial f_n}{\partial x_n} \end{array} \right)^{-1} \left(\begin{array}{c} f_1(\bf{x}^{(k)}) \\ f_2(\bf{x}^{(k)}) \\ . \\ f_n(\bf{x}^{(k)}) \end{array}\right)$

Note that you’ll have to evaluate the Jacobian matrix at $\bf{x} = \bf{x^{(k)}}$ during each iteration. For a proof of when the method converges, and some modifications to make it converge faster, check the references which are given at the end of this post.

There’s something interesting which happens when you apply this technique to an equation in the complex plane. For a complex number $z=x+iy$ , any polynomial equation $f(z) = 0$ can be written as two equations in the variables x and y. For example, if $f(z) = z^2 + 1 = 0$ , then,

$(x+iy)^2 + 1 = 0$

$(x^2 -y^2 + 1) + i(2xy) = 0$ ,

which means

$f(x,y)=x^2-y^2+1=0$ and $g(x,y)=2xy=0$

Also, note that for every (x,y) we have a corresponding point in the complex plane.

Now consider this question. Let’s say we have a polynomial equation $z^n - 1 = 0$ . Given an arbitrary initial guess of the root to this equation

a) Will the algorithm converge to give a solution for that particular initial guess?
b) If so, how long does it take to converge to a solution for that particular initial guess?

An attempt to answer to these questions leads to fractal patterns. In the color scheme I’ve used, the bluer regions correspond to where the initial guesses converge faster. The yellow/red regions is where the initial guesses converge slowly or do not converge.

- z^3+1=0,

- z^4+1=0

- z^5+1=0

As you can see, while some initial guesses converge without much fuss (the basin regions), others can show remarkable behavior (guesses near the “boundary”) and can lead to a number of intricate patterns for various functions. I’ve linked to some websites which contain a gallery of such images for various functions. Some of them are truly remarkable!

References and External Links
- A Class of Methods for Solving Nonlinear Simultaneous Equations, C. G. Broyden, Mathematics of Computation, Vol. 19, No. 92 (Oct., 1965), pp. 577-593
- An Introduction to Numerical Analysis, Endre Suli and David Mayers, Cambridge University Press,Pg 104-125
- Fractals from Newton’s Method
- Newton Basins
- Newton’s method and Newton basin fractals
- Newton’s Method gallery
- Another Newton’s Method Gallery

Like this:

Be the first to like this post.

Written by parseval

September 20, 2007 at 1:23 pm

Posted in mathematics

One Response

Subscribe to comments with RSS.

Very nice post. I remember being absolutely fascinated when I saw a similar example (for z^6 + 1 = 0, coincidentally!) in Thomas and Finney’s book on Calculus. It’s amazing how chaos lurks right below our noses everywhere

Mohan

September 21, 2007 at 4:57 pm

Reply

M	T	W	T	F	S	S
« Aug				Oct »
					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

A Candle in the Dark