A Candle in the Dark

A look on science, politics, religion and events

Newton’s method and fractals

with one comment

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,

nis3.png

z^4+1=0

nis4.png

z^5+1=0

nis5.png

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

Advertisements

Written by parseval

September 20, 2007 at 1:23 pm

Posted in mathematics

One Response

Subscribe to comments with RSS.

  1. 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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: