Newton fractal

The Newton fractal is a boundary set in the complex plane which is characterized by Newton's method applied to a fixed polynomial p ( Z ) ∈ C [ Z ] {displaystyle p(Z)in mathbb {C} } or transcendental function. It is the Julia set of the meromorphic function z ↦ z − p ( z ) p ′ ( z ) {displaystyle zmapsto z-{ frac {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 regions G k {displaystyle G_{k}} , each of which is associated with a root ζ k {displaystyle zeta _{k}} of the polynomial, k = 1 , … , deg ⁡ ( p ) {displaystyle k=1,ldots ,deg(p)} . 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.Newton fractal for three degree-3 roots ( p ( z ) = z 3 − 1 {displaystyle p(z)=z^{3}-1} ), coloured by number of iterations requiredNewton fractal for three degree-3 roots ( p ( z ) = z 3 − 1 {displaystyle p(z)=z^{3}-1} ), coloured by root reachedNewton fractal for p ( z ) = z 3 − 2 z + 2 {displaystyle p(z)=z^{3}-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 for x 8 + 15 x 4 − 16 {displaystyle x^{8}+15x^{4}-16} Newton fractal for p ( z ) = z 5 − 3 i z 3 − ( 5 + 2 i ) z 2 + 3 z + 1 {displaystyle p(z)=z^{5}-3iz^{3}-(5+2i)z^{2}+3z+1} , coloured by root reached, shaded by number of iterations required.Newton fractal for p ( z ) = sin ⁡ ( z ) {displaystyle p(z)=sin(z)} , coloured by root reached, shaded by number of iterations requiredAnother Newton fractal for sin ⁡ ( x ) {displaystyle sin(x)} Generalized Newton fractal for p ( z ) = z 3 − 1 {displaystyle p(z)=z^{3}-1} , a = − 0.5. {displaystyle a=-0.5.} The colour was chosen based on the argument after 40 iterations.Generalized Newton fractal for p ( z ) = z 2 − 1 {displaystyle p(z)=z^{2}-1} , a = 1 + i . {displaystyle a=1+i.} Generalized Newton fractal for p ( z ) = z 3 − 1 {displaystyle p(z)=z^{3}-1} , a = 2. {displaystyle a=2.} Generalized Newton fractal for p ( z ) = z 4 + 3 i − 1 {displaystyle p(z)=z^{4+3i}-1} , a = 2.1. {displaystyle a=2.1.} The Newton fractal is a boundary set in the complex plane which is characterized by Newton's method applied to a fixed polynomial p ( Z ) ∈ C [ Z ] {displaystyle p(Z)in mathbb {C} } or transcendental function. It is the Julia set of the meromorphic function z ↦ z − p ( z ) p ′ ( z ) {displaystyle zmapsto z-{ frac {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 regions G k {displaystyle G_{k}} , each of which is associated with a root ζ k {displaystyle zeta _{k}} of the polynomial, k = 1 , … , deg ⁡ ( p ) {displaystyle k=1,ldots ,deg(p)} . 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. Many points of the complex plane are associated with one of the deg ⁡ ( p ) {displaystyle deg(p)} roots of the polynomial in the following way: the point is used as starting value z 0 {displaystyle z_{0}} for Newton's iteration z n + 1 := z n − p ( z n ) p ′ ( z n ) {displaystyle z_{n+1}:=z_{n}-{frac {p(z_{n})}{p'(z_{n})}}} , yielding a sequence of points z 1 , z 2 , … , {displaystyle z_{1},z_{2},ldots ,} If the sequence converges to the root ζ k {displaystyle zeta _{k}} , then z 0 {displaystyle z_{0}} was an element of the region G k {displaystyle G_{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 is z 3 − 2 z + 2 {displaystyle z^{3}-2z+2} , where some points are attracted by the cycle 0, 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 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 interesting pictures, one may first choose a specified number d {displaystyle d} of complex points ( ζ 1 , … , ζ d ) {displaystyle (zeta _{1},ldots ,zeta _{d})} and compute the coefficients ( p 1 , … , p d ) {displaystyle (p_{1},ldots ,p_{d})} of the polynomial Then for a rectangular lattice z m n = z 00 + m Δ x + i n Δ y {displaystyle z_{mn}=z_{00}+m,Delta x+in,Delta y} , m = 0 , … , M − 1 {displaystyle m=0,ldots ,M-1} , n = 0 , … , N − 1 {displaystyle n=0,ldots ,N-1} of points in C {displaystyle mathbb {C} } , one finds the index k ( m , n ) {displaystyle k(m,n)} of the corresponding root ζ k ( m , n ) {displaystyle zeta _{k(m,n)}} and uses this to fill an M {displaystyle M} × N {displaystyle N} raster grid by assigning to each point ( m , n ) {displaystyle (m,n)} a color f k ( m , n ) {displaystyle f_{k(m,n)}} . Additionally or alternatively the colors may be dependent on the distance D ( m , n ) {displaystyle D(m,n)} , which is defined to be the first value D {displaystyle D} such that | z D − ζ k ( m , n ) | < ϵ {displaystyle |z_{D}-zeta _{k(m,n)}|<epsilon } for some previously fixed small ϵ > 0 {displaystyle epsilon >0} .