Newton fractal
3918520
213214547
2008-05-18T09:24:28Z
59.100.137.96
/* See also */
[[Image:Fractal newton.png|frame|right]]
The '''Newton fractal''' is a boundary set in the [[complex plane]] which is characterized by [[Newton's method]] applied to a fixed [[polynomial]] <math>p(Z)\in\mathbb{C}[Z]</math>. When there are no attractive cycles, it divides the complex plane into regions <math>G_k</math>, each of which is associated with a [[root (mathematics)|root]] <math>\zeta_k</math> of the polynomial, <math>k=1,..,\operatorname{deg}(p)</math>. In this way the Newton fractal is similar to the [[Mandelbrot set]], and like other fractals it exhibits a complex 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 <math>\operatorname{deg}(p)</math> roots of the polynomial in the following way: the point is used as starting value <math>z_0</math> for Newton's iteration <math>z_{n+1}:=z_n-\frac{p(z)}{p'(z)}</math>, yielding a sequence of points <math>z_1</math>, <math>z_2</math>, .... If the sequence converges to the root ''ζ<sub>k</sub>'', then ''z<sub>0</sub>'' was an element of the region ''G<sub>k</sub>''. 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<sup>3</sub>-2z+2'', where some points are attracted by the cycle 0, 1, 0, 1 ... rather than by a root.
To plot interesting pictures, one may first choose a specified number ''d'' of complex points ''(ζ<sub>1</sub>,...,ζ<sub>d</sub>)'' and compute the coëfficients ''(p<sub>1</sub>,...,p<sub>d</sub>)'' of the polynomial
:<math>p(z)=z^d+p_1z^{d-1}+\cdots+p_{d-1}z+p_d:=(z-\zeta_1)\cdot\cdots\cdot(z-\zeta_d)</math>.
Then for a rectangular lattice ''z<sub>mn</sub> = z<sub>00</sub> + mΔx + inΔy'', ''m'' = 0, ..., ''M'' - 1, ''n'' = 0, ..., ''N'' - 1 of points in <math>\mathbb{C}</math>, one finds the index ''k(m,n)'' of the corresponding root ''ζ<sub>k(m,n)</sub>'' and uses this to fill an ''M×N'' raster grid by assigning to each point ''(m,n)'' a colour ''f<sub>k(m,n)</sub>''. 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<sub>D</sub> - ζ<sub>k(m,n)</sub>''|'' < ε'' for some previously fixed small ''ε > 0''.
== Generalization of Newton fractals ==
A generalization of Newton's iteration is
:<math>z_{n+1}=z_n- a \frac{p(z_n)}{p'(z_n)} </math>
where a is any complex number<ref>{{cite web | url = http://www.chiark.greenend.org.uk/~sgtatham/newton/ | title = Fractals derived from Newton-Raphson | author = Simon Tatham }}</ref>. The special choice <math>a=1</math> corresponds to the Newton fractal.
The fixed points of this map are stable when <math>a</math> 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]].
<gallery>
Image:FRACT008.png|Newton fractal for three degree-3 roots (<math>p(z)=z^3-1</math>), coloured by number of iterations required
Image:Newtroot 1 0 0 m1.png|Newton fractal for three degree-3 roots (<math>p(z)=z^3-1</math>), coloured by root reached
Image:Newton_z3-2z+2.png|Newton fractal for <math>p(z)=z^3-2z+2</math>. Points in the red basins do not reach a root.
Image:timelapse34.jpg|Newton fractal for <math>x^8+15x^4-16</math>
Image:Newtroot 1 0 m3i m5m2i 3 1.png|Newton fractal for <math>p(z)=z^5-3iz^3-(5+2i)z^2+3z+1</math>, coloured by root reached, shaded by number of iterations required
Image:timelapse4.jpg|Newton fractal for <math>p(z)=sin(z)</math>, coloured by root reached, shaded by number of iterations required
Image:Sin(x)_detail.png|Another Newton fractal for <math>sin(x)</math>
Image:Mnfrac1.png| Generalized Newton fractal for <math>p(z)=z^3-1</math>, <math>a=-0.5.</math> The colour was chosen based on the argument after 40 iterations.
Image:Mnfrac2.png| Generalized Newton fractal for <math>p(z)=z^2-1</math>, <math> a=1+i.</math>
Image:Mnfrac3.png| Generalized Newton fractal for <math>p(z)=z^3-1</math>, <math>a=2.</math>
Image:Mnfrac4.png| Generalized Newton fractal for <math>p(z)=z^{4+3i}-1</math>, <math>a=2.1.</math>
</gallery>
== See also ==
* [[Julia set]]
* [[Mandelbrot set]]
* [[Nova fractal]]
==References==
{{reflist}}
* [http://www.math.sunysb.edu/~scott/ 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
*[http://citeseer.ist.psu.edu/313081.html ''On the Number of Iterations for Newton's Method''] by Dierk Schleicher July 21, 2000
*[http://www.math.sunysb.edu/cgi-bin/thesis.pl?thesis06-1 ''Newton's Method as a Dynamical System''] by Johannes Rueckert
{{Commons|Newton fractal|Newton fractal}}
[[Category:Numerical analysis]]
[[Category:Fractals]]
[[bg:Нютонов фрактал]]
[[cs:Fraktál Newton]]
[[de:Newton-Fraktal]]
[[pl:Wstęga Newtona]]
[[ru:Бассейны Ньютона]]