TheNewton fractal is aboundary set in thecomplex plane which is characterized byNewton's method applied to a fixedpolynomialp(z) ∈${\displaystyle \mathbb{C}}$[z] ortranscendental function. It is theJulia set of themeromorphic functionz ↦z −⁠p(z)/p′(z)⁠ which is given by Newton's method. When there are no attractive cycles (of order greater than 1), it divides the complex plane into regionsG_k, each of which is associated with arootζ_k of the polynomial,k = 1, …, deg(p). In this way the Newton fractal is similar to theMandelbrot set, and like other fractals it exhibits an intricate appearance arising from a simple description. It is relevant tonumerical analysis because it shows that (outside the region ofquadratic 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 thedeg(p) roots of a given polynomial in the following way: the point is used as starting valuez₀ for Newton's iterationz_{n + 1} :=z_n −⁠p(z_n)/p'(z_n)⁠, yielding a sequence of pointsz₁,z₂, …, If the sequence converges to the rootζ_k, thenz₀ was an element of the regionG_k. 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 isz³ − 2z + 2, where some points are attracted by the cycle0, 1, 0, 1… 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 aFatou 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 numberd of complex points(ζ₁, …,ζ_d) and compute the coefficients(p₁, …,p_d) of the polynomial

${\displaystyle 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

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

of points in${\displaystyle \mathbb{C}}$, one finds the indexk(m,n) of the corresponding rootζ_k(m,n) and uses this to fill anM ×N raster grid by assigning to each point(m,n) a colorf_k(m,n). Additionally or alternatively the colors may be dependent on the distanceD(m,n), which is defined to be the first valueD such that|z_D −ζ_k(m,n)| <ε for some previously fixed smallε > 0.

A generalization of Newton's iteration is

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

wherea is anycomplex number.^[1] The special choicea = 1 corresponds to the Newton fractal. The fixed points of this map are stable whena lies inside the disk of radius 1 centered at 1. Whena is outside this disk, the fixed points are locally unstable, however the map still exhibits a fractal structure in the sense ofJulia set. Ifp is a polynomial of degreed, then the sequencez_n isbounded provided thata is inside a disk of radiusd centered atd.

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

•  
  Newton fractal for three degree-3 rootsp(z) =z³ − 1, coloured by number of iterations required
•  
  Newton fractal for three degree-3 rootsp(z) =z³ − 1, coloured by root reached
•  
  Newton fractal forp(z) =z³ − 2z + 2. 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 forp(z) =z⁸ + 15z⁴ − 16
•  
  Newton fractal forp(z) =z⁵ − 3iz³ − (5 + 2i)z² + 3z + 1, coloured by root reached, shaded by number of iterations required.
•  
  Newton fractal forp(z) = sinz, coloured by root reached, shaded by number of iterations required
•  
  Another Newton fractal forp(z) = sinz
•  
  Generalized Newton fractal forp(z) =z³ − 1,a = −⁠1/2⁠. The colour was chosen based on the argument after 40 iterations.
•  
  Generalized Newton fractal forp(z) =z² − 1,a = 1 +i.
•  
  Generalized Newton fractal forp(z) =z³ − 1,a = 2.
•  
  Generalized Newton fractal forp(z) =z^{4 + 3i} − 1,a = 2.1.
•  
  p(z) =z⁶ +z³ - 1
•  
  p(z) = sinz - 1
•  
  p(z) = sinz - 1
•  
  p(z) = coshz - 1
•  
  p(z) = coshz - 1
•  
  p(z) =z²⁰ - 2z + 2

Serie :p(z) =zⁿ- 1

•  
  p(z) =z³ - 1, a=1
•  
  p(z) =z³ - 1, a=2
•  
  p(z) =z⁴ - 1, a=1
•  
  p(z) =z⁴ - 1, a=2
•  
  p(z) =z⁵ - 1, a=1
•  
  p(z) =z⁵ - 1, a=2
•  
  p(z) =z⁶ - 1, a=1
•  
  p(z) =z⁷ - 1, a=1
•  
  p(z) =z⁸ - 1, a=1
•  
  p(z) =z¹⁰ - 1, a=1

Other fractals where potential and trigonometric functions are multiplied.p(z) =zⁿ*Sin(z) - 1

•  
  p(z) =z²*Sin(Z) - 1, a=1
•  
  p(z) =z²*Sin(Z) - 1, a=1 (zoom)
•  
  p(z) =z³*Sin(Z) - 1, a=1
•  
  p(z) =z⁴*Sin(Z) - 1, a=1
•  
  p(z) =z⁴*Sin(Z) - 1, a=1 (zoom)
•  
  p(z) =z⁵*Sin(Z) - 1, a=1
•  
  p(z) =z⁶*Sin(Z) - 1, a=1
•  
  p(z) =z⁶*Sin(Z) - 1, a=1 (zoom)

The Nova fractal invented in the mid 1990s by Paul Derbyshire,^[2][3] is a generalization of the Newton fractal with the addition of a valuec at each step:^[4]

${\displaystyle 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 keepsc constant over the image and initializesz₀ to the pixel coordinates. The "Mandelbrot" variant of the Nova fractal initializesc to the pixel coordinates and setsz₀ to a critical point, where^[5]

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

Commonly-used polynomials likep(z) =z³ − 1 orp(z) = (z − 1)³ lead to a critical point atz = 1.

•  
  Animated "Julia" Nova fractal forp(z) =z³ − 1 withc going from −1 to 1, colored by root reached.
•  
  Animated "Julia" Nova fractal forp(z) =z³ − 1 withc =⁠1/2⁠e^iφ andφ going from 0 to 2π, colored by root reached.

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

 

The three roots of the function are

${\displaystyle 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 inpseudocode as follows:

//z^3-1float2Function(float2z){returncpow(z,3)-float2(1,0);//cpow is an exponential function for complex numbers}//3*z^2float2Derivative(float2z){return3*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.

float2roots[3]=//Roots (solutions) of the polynomial{float2(1,0),float2(-.5,sqrt(3)/2),float2(-.5,-sqrt(3)/2)};colorcolors[3]=//Assign a color for each root{red,green,blue}Foreachpixel(x,y)onthetarget,do:{zx=scaledxcoordinateofpixel(scaledtolieintheMandelbrotXscale(-2.5,1))zy=scaledycoordinateofpixel(scaledtolieintheMandelbrotYscale(-2,1))float2z=float2(zx,zy);//z is originally set to the pixel coordinatesfor(intiteration=0;iteration<maxIteration;iteration++;){z-=cdiv(Function(z),Derivative(z));//cdiv is a function for dividing complex numbersfloattolerance=0.000001;for(inti=0;i<roots.Length;i++){float2difference=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){returncolors[i];//Return the color corresponding to the root}}}returnblack;//If no solution is found}

• Julia set
• Mandelbrot set

• 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) by3Blue1Brown, along with an interactive demonstration of the fractal onhis website, and thesource code for the demonstration