Newton fractal

Fatou sets (blue, red and green) and Julia set (their boundary) for the rational function associated to Newton's method for Template:Math.

The Newton fractal is a boundary set in the complex plane which is characterized by Newton's method applied to a fixed polynomial Template:Math$ℂ$Template:Math or transcendental function. It is the Julia set of the meromorphic function Template:Math which is given by Newton's method. When there are no attractive cycles (of order greater than 1), it divides the complex plane into regions Template:Math, each of which is associated with a root Template:Math of the polynomial, Template:Math. In this way the Newton fractal is similar to the Mandelbrot set, and like other fractals it exhibits an intricate appearance arising from a simple description. It is relevant to numerical analysis because it shows that (outside the region of quadratic convergence) the Newton method can be very sensitive to its choice of start point.

Almost all points of the complex plane are associated with one of the Template:Math roots of a given polynomial in the following way: the point is used as starting value Template:Math for Newton's iteration Template:Math, yielding a sequence of points Template:Math If the sequence converges to the root Template:Math, then Template:Math was an element of the region Template:Math. However, for every polynomial of degree at least 2 there are points for which the Newton iteration does not converge to any root: examples are the boundaries of the basins of attraction of the various roots. There are even polynomials for which open sets of starting points fail to converge to any root: a simple example is Template:Math, where some points are attracted by the cycle Template:Math rather than by a root.

An open set for which the iterations converge towards a given root or cycle (that is not a fixed point), is a Fatou set for the iteration. The complementary set to the union of all these, is the Julia set. The Fatou sets have common boundary, namely the Julia set. Therefore, each point of the Julia set is a point of accumulation for each of the Fatou sets. It is this property that causes the fractal structure of the Julia set (when the degree of the polynomial is larger than 2).

To plot images of the fractal, one may first choose a specified number Template:Mvar of complex points Template:Math and compute the coefficients Template:Math of the polynomial

$p(z)=z^d+p_1{z}^{d-1}+\cdots +p_{d-1}z+p_d:=(z-{\zeta }_1)(z-{\zeta }_2)\cdots (z-{\zeta }_d)$.

Then for a rectangular lattice

$z_{mn}=z_{00}+m\Delta x+in\Delta y;m=0,\dots ,M-1;n=0,\dots ,N-1$

of points in $ℂ$, one finds the index Template:Math of the corresponding root Template:Math and uses this to fill an Template:Math raster grid by assigning to each point Template:Math a color Template:Math. Additionally or alternatively the colors may be dependent on the distance Template:Math, which is defined to be the first value Template:Mvar such that Template:Math for some previously fixed small Template:Math.

Generalization of Newton fractals

A generalization of Newton's iteration is

$z_{n+1}=z_n-a\frac{p(z_n)}{p^{\prime }(z_n)}$

where Template:Mvar is any complex number. The special choice Template:Math corresponds to the Newton fractal. The fixed points of this map are stable when Template:Mvar lies inside the disk of radius 1 centered at 1. When Template:Mvar is outside this disk, the fixed points are locally unstable, however the map still exhibits a fractal structure in the sense of Julia set. If Template:Mvar is a polynomial of degree Template:Mvar, then the sequence Template:Mvar is bounded provided that Template:Mvar is inside a disk of radius Template:Mvar centered at Template:Mvar.

More generally, Newton's fractal is a special case of a Julia set.

• 
  Newton fractal for three degree-3 roots Template:Math, coloured by number of iterations required
• 
  Newton fractal for three degree-3 roots Template:Math, coloured by root reached
• 
  Newton fractal for Template:Math. Points in the red basins do not reach a root.
• 
  Newton fractal for a 7th order polynomial, colored by root reached and shaded by rate of convergence.
• 
  Newton fractal for Template:Math
• 
  Newton fractal for Template:Math, coloured by root reached, shaded by number of iterations required.
• 
  Newton fractal for Template:Math, coloured by root reached, shaded by number of iterations required
• 
  Another Newton fractal for Template:Math
• 
  Generalized Newton fractal for Template:Math, Template:Math. The colour was chosen based on the argument after 40 iterations.
• 
  Generalized Newton fractal for Template:Math, Template:Math.
• 
  Generalized Newton fractal for Template:Math, Template:Math.
• 
  Generalized Newton fractal for Template:Math, Template:Math.
• 
  Template:Math
• 
  Template:Math
• 
  Template:Math
• 
  Template:Math
• 
  Template:Math
• 
  Template:Math

Serie : Template:Math

• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center

Other fractals where potential and trigonometric functions are multiplied. Template:Math

• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center
• 
  Template:Center

Nova fractal

The Nova fractal invented in the mid 1990s by Paul Derbyshire, is a generalization of the Newton fractal with the addition of a value Template:Mvar at each step:

$z_{n+1}=z_n-a\frac{p(z_n)}{p^{\prime }(z_n)}+c=G(a,c,z)$

The "Julia" variant of the Nova fractal keeps Template:Mvar constant over the image and initializes Template:Math to the pixel coordinates. The "Mandelbrot" variant of the Nova fractal initializes Template:Mvar to the pixel coordinates and sets Template:Math to a critical point, where

$\frac{\partial }{\partial z}G(a,c,z)=0.$

Commonly-used polynomials like Template:Math or Template:Math lead to a critical point at Template:Math.

• 
  Animated "Julia" Nova fractal for Template:Math with Template:Mvar going from −1 to 1, colored by root reached.
• 
  Animated "Julia" Nova fractal for Template:Math with Template:Math and Template:Mvar going from 0 to 2Template:Pi, colored by root reached.

Implementation

In order to implement the Newton fractal, it is necessary to have a starting function as well as its derivative function:

$\begin{array}{cc}f(z)& =z^3-1\\ f^{\prime }(z)& =3z^2\end{array}$

The three roots of the function are

$z=1,-\frac{1}{2}+\frac{\sqrt{3}}{2}i,-\frac{1}{2}-\frac{\sqrt{3}}{2}i$

The above-defined functions can be translated in pseudocode as follows:

//z^3-1 
float2 Function (float2 z)
{
	return cpow(z, 3) - float2(1, 0); //cpow is an exponential function for complex numbers
}

//3*z^2
float2 Derivative (float2 z)
{
	return 3 * cmul(z, z); //cmul is a function that handles multiplication of complex numbers
}

It is now just a matter of implementing the Newton method using the given functions.

float2 roots[3] = //Roots (solutions) of the polynomial
{
	float2(1, 0), 
	float2(-.5, sqrt(3)/2), 
	float2(-.5, -sqrt(3)/2)
};
	
color colors[3] =  //Assign a color for each root
{
    red,
    green,
    blue
}

For each pixel (x, y) on the target, do:
{
	zx = scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))
    zy = scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-2, 1))

    float2 z = float2(zx, zy); //z is originally set to the pixel coordinates

	for (int iteration = 0;
	     iteration < maxIteration;
	     iteration++;)
	{
		z -= cdiv(Function(z), Derivative(z)); //cdiv is a function for dividing complex numbers

        float tolerance = 0.000001;
        
		for (int i = 0; i < roots.Length; i++)
		{
		    float2 difference = z - roots[i];
		    
			//If the current iteration is close enough to a root, color the pixel.
			if (abs(difference.x) < tolerance && abs (difference.y) < tolerance)
			{
				return colors[i]; //Return the color corresponding to the root
			}
		}
		
    }
    
    return black; //If no solution is found
}

See also

• Julia set
• Mandelbrot set

Further reading

• J. H. Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton's Method, Inventiones Mathematicae vol. 146 (2001) – with a discussion of the global structure of Newton fractals
• On the Number of Iterations for Newton's Method by Dierk Schleicher July 21, 2000
• Newton's Method as a Dynamical System by Johannes Rueckert
• Newton's Fractal (which Newton knew nothing about) by 3Blue1Brown, along with an interactive demonstration of the fractal on his website, and the source code for the demonstration