Newton fractal

Julia set for the rational function associated to Newton's method for ƒ:z→z³−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)\in {\mathbb {C}}[Z]$ or transcendental function. It is the Julia set of the meromorphic function $z\mapsto z-{\tfrac {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}$ , each of which is associated with a root $\zeta _{k}$ of the polynomial, $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)$ roots of the polynomial in the following way: the point is used as starting value $z_{0}$ for Newton's iteration $z_{{n+1}}:=z_{n}-{\frac {p(z_{n})}{p'(z_{n})}}$ , yielding a sequence of points $z_1,z_2,\ldots,$ If the sequence converges to the root $\zeta _{k}$ , then $z_{0}$ was an element of the region $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}-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$ of complex points $(\zeta_1,\ldots,\zeta_d)$ and compute the coefficients $(p_1,\ldots,p_d)$ of the polynomial

p(z)=z^{d}+p_{1}z^{{d-1}}+\cdots +p_{{d-1}}z+p_{d}:=(z-\zeta _{1})\cdot \cdots \cdot (z-\zeta _{d})

Then for a rectangular lattice $z_{mn} = z_{00} + m \, \Delta x + in \, \Delta y$ , $m = 0, \ldots, M - 1$ , $n = 0, \ldots, N - 1$ of points in $\mathbb {C}$ , one finds the index $k(m,n)$ of the corresponding root $\zeta _{{k(m,n)}}$ and uses this to fill an $M$ × $N$ raster grid by assigning to each point $(m,n)$ a colour $f_{{k(m,n)}}$ . Additionally or alternatively the colours may be dependent on the distance $D(m,n)$ , which is defined to be the first value $D$ such that $|z_{D}-\zeta _{{k(m,n)}}|<\epsilon$ for some previously fixed small $\epsilon >0$ .

Generalization of Newton fractals

A generalization of Newton's iteration is

z_{{n+1}}=z_{n}-a{\frac {p(z_{n})}{p'(z_{n})}}

where $a$ is any complex number.^[1] The special choice $a=1$ corresponds to the Newton fractal. The fixed points of this map are stable when $a$ lies inside the disk of radius 1 centered at 1. When $a$ 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 $p$ is a polynomial of degree $n$ , then the sequence $z_{n}$ is bounded provided that $a$ is inside a disk of radius $n$ centered at $n$ .

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

Newton fractal for three degree-3 roots ( $p(z)=z^{3}-1$ ), coloured by number of iterations required
Newton fractal for three degree-3 roots ( $p(z)=z^{3}-1$ ), coloured by root reached
Newton fractal for $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}+15x^{4}-16$
Newton fractal for $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)$ , coloured by root reached, shaded by number of iterations required
Another Newton fractal for $\sin(x)$
Generalized Newton fractal for $p(z)=z^{3}-1$ , $a=-0.5.$ The colour was chosen based on the argument after 40 iterations.
Generalized Newton fractal for $p(z)=z^{2}-1$ , $a=1+i.$
Generalized Newton fractal for $p(z)=z^{3}-1$ , $a=2.$
Generalized Newton fractal for $p(z)=z^{{4+3i}}-1$ , $a=2.1.$
$p(z)=z^{6}+z^{3}-1$
$p(z)=\sin(z)-1$
$p(z)=\cosh(z)-1$

References

Wikimedia Commons has media related to Newton fractals.

↑ Simon Tatham. "Fractals derived from Newton–Raphson".

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

Isaac Newton

Publications	De analysi per aequationes numero terminorum infinitas (1669, published 1711) Method of Fluxions (1671) De motu corporum in gyrum (1684) Philosophiæ Naturalis Principia Mathematica (1687) General Scholium (1713) Opticks (1704) The Queries (1704) Arithmetica Universalis (1707)

Other writings	Notes on the Jewish Temple Quaestiones quaedam philosophicae The Chronology of Ancient Kingdoms Amended (1728) An Historical Account of Two Notable Corruptions of Scripture (1754)

Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation Post-Newtonian expansion Parameterized post-Newtonian formalism Newton–Cartan theory Schrödinger–Newton equation Gravitational constant Newton's laws of motion Newtonian dynamics Newton's method in optimization Gauss–Newton algorithm Truncated Newton method Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Newtonian fluid Corpuscular theory of light Leibniz–Newton calculus controversy Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method Newton fractal Generalized Gauss–Newton method Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number Kissing number problem Power number Solar mass Dynamics Absolute time and space Finite difference Table of Newtonian series Impact depth Structural coloration Inertia

Life	Cranbury Park Woolsthorpe Manor Early life of Isaac Newton Later life of Isaac Newton Religious views of Isaac Newton Isaac Newton's occult studies The Mysteryes of Nature and Art Scientific revolution Copernican Revolution

Friends and family	Catherine Barton John Conduitt William Clarke Benjamin Pulleyn William Stukeley William Jones Isaac Barrow Abraham de Moivre John Keill

Discoveries and inventions	Calculus Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Newton's cradle Sextant

Phrases	"Hypotheses non fingo" "Standing on the shoulders of giants"

Theory expansions	Kepler's laws of planetary motion Problem of Apollonius

Related	Writing of Principia Mathematica Newton (Blake) List of things named after Isaac Newton Newton (unit) Isaac Newton in popular culture Elements of the Philosophy of Newton Isaac Newton S/O Philipose

This article is issued from Wikipedia - version of the 9/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Newton fractal

Generalization of Newton fractals

See also

References