Newton Fractal¶

Newton Fractal is generated by iterating Newton-Raphson method of finding roots in the complex plane. [Sahari2006]

Newton-Raphson Method of Finding Roots¶

The Newton-Raphson method (also known as Newton’s method) is a way to quickly find a good approximation for the root of a real-valued function \(f(x) = 0\) It uses the idea that a continuous and differentiable function can be approximated by a straight line tangent to it.

To perform a Newton-Raphson approximation, suppose you have a function \(f(x)\), with derivative \(f′(x)\), and you have an approximation \(x_0\) to a root of the function. The Newton-Raphson procedure is to calculate:

\[x_1 = x_0 − \frac{f(x_0)}{f′(x_0)}\]

which is a closer approximation to the root. Typically you would then iterate this again, and again, until the successive values were extremely close together, at which point you would conclude that you had a very good approximation to the actual value \(r\) for which \(f(r)=0\).

The iteration performed is:

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

Using Newton-Raphson Method for Generating Fractal¶

If we used this method to start iteration at each point on the real-line, run the iteration until it converged to within tolerance level of a root, and then colour the starting point according to which root it ended up at, what we get is a fractal.

But Fractal in 1 Dimension is not that intuitive, so taking this process to complex plane i.e. performing Newton-Raphson Method at each point in complex plane and colour that point according to the root to which it converged, would give us colourful fractals.

Algorithm used in the Code¶

Choose a function \(f(z)\), remember how interesting the fractal looks depends on this choice.
Find the roots of \(f(z)\) and find the function required for the iteration i.e. \(\frac{f(z)}{f'(z)}\).
Choose the range of the complex plane, and divide the x-axis and y-axis into m and n points respectively (assuming the dimensions of the image to be generated is (m X n)).
Run the iteration for each point on the plance with given tolerance and max number of iterations.
Assign the colour to each point according to the root to which it converged.
Plot the resulting colour for each grid point.

Precautions¶

As generating fractals requires some heavy computation (can take minutes depending on your configuration), it is recommended to start with generating a low-resolution image and once you are sure everything works as expected, generate the final high-resolution image.
The tolerance you choose should be small enough so that if roots lie really close to one another, the program can correctly assign the colour.
Choose the initial range of the graph such that it covers almost majority of the roots, so as to see the interesting things happening, and then focus on the part you want.