Newton fractal
Encyclopedia
The Newton fractal is a boundary set in the complex plane
which is characterized by Newton's method
applied to a fixed polynomial
. It is the Julia set
of the meromorphic function
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 
, each of which is associated with a root 
of the polynomial, 
. 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
roots of the polynomial in the following way: the point is used as starting value 
for Newton's iteration 
, yielding a sequence of points 
, 
, .... If the sequence converges to the root 
, then 
was an element of the region 
. 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 
, 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
of complex points 
and compute the coefficients 
of the polynomial
.
Then for a rectangular lattice
, 
, ..., 
, 
, ..., 
of points in 
, one finds the index 
of the corresponding root 
and uses this to fill an 
×
raster grid by assigning to each point 
a colour 
. Additionally or alternatively the colours may be dependent on the distance 
, which is defined to be the first value 
such that 
for some previously fixed small 
.
where
is any complex number. The special choice 
corresponds to the Newton fractal.
The fixed points of this map are stable when
lies inside the disk of radius 1 centered at 1. When 
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
is a polynomial of degree 
, then the sequence 
is bounded provided that 
is inside a disk of radius 
centered at 
.
More generally, Newton's fractal is a special case of a Julia set
.
Complex plane
In mathematics, the complex plane or z-plane is a geometric representation of the complex numbers established by the real axis and the orthogonal imaginary axis...
which is characterized by Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
applied to a fixed polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
. It is the Julia setJulia set
In the context of complex dynamics, a topic of mathematics, the Julia set and the Fatou set are two complementary sets defined from a function...
of the meromorphic function
Meromorphic function
In complex analysis, a meromorphic function on an open subset D of the complex plane is a function that is holomorphic on all D except a set of isolated points, which are poles for the function...
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 , each of which is associated with a root of the polynomial, . In this way the Newton fractal is similar to the Mandelbrot setMandelbrot set
The Mandelbrot set is a particular mathematical set of points, whose boundary generates a distinctive and easily recognisable two-dimensional fractal shape...
, and like other fractals it exhibits an intricate appearance arising from a simple description. It is relevant to numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical 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
roots of the polynomial in the following way: the point is used as starting value for Newton's iteration , yielding a sequence of points , , .... If the sequence converges to the root , then was an element of the region . 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 , 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
of complex points and compute the coefficients of the polynomial.Then for a rectangular lattice
, , ..., , , ..., of points in , one finds the index of the corresponding root and uses this to fill an × raster grid by assigning to each point a colour . Additionally or alternatively the colours may be dependent on the distance , which is defined to be the first value such that for some previously fixed small .Generalization of Newton fractals
A generalization of Newton's iteration iswhere
is any complex number. The special choice corresponds to the Newton fractal.The fixed points of this map are stable when
lies inside the disk of radius 1 centered at 1. When is outside this disk, the fixed points are locally unstable, however the map still exhibits a fractal structure in the sense of Julia setJulia set
In the context of complex dynamics, a topic of mathematics, the Julia set and the Fatou set are two complementary sets defined from a function...
. If
is a polynomial of degree , then the sequence is bounded provided that is inside a disk of radius centered at .More generally, Newton's fractal is a special case of a Julia set
Julia set
In the context of complex dynamics, a topic of mathematics, the Julia set and the Fatou set are two complementary sets defined from a function...
.