Newton fractal

From Wikipedia, the free encyclopedia

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) ∈ ℂ[Z]. When there are not attractive cycles, it divides the complex plane into regions G_k, each of which is associated with a root ζ_k of the polynomial, k = 1, ..., deg(p). 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.

Each point of the complex plane is associated with one of the deg(p) roots of the polynomial in the following way: the point is used as starting value z₀ for Newton's iteration $z_{n+1}:=z_n-\frac{p(z)}{p'(z)}$ , yielding a sequence of points $z 1$ , $z 2$ , .... If the sequence converges to the root ζ_k, then z₀ was an element of the region G_k.

To plot interesting pictures, one may first choose a specified number d of complex points (ζ₁,...,ζ_d) and compute the coëfficients (p₁,...,p_d) of the polynomial

$p(z)=z^d+p_1z^{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₀₀ + mΔx + inΔy, m = 0, ..., M - 1, n = 0, ..., N - 1 of points in ℂ, one finds the index k(m,n) of the corresponding root ζ_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 - ζ_k(m,n)| < ε for some previously fixed small ε > 0.

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 $x 8 + 15 x 4 - 16$	Newton fractal for $p (z) = z 5 - 1$ , coloured by root reached, shaded by number of iterations required
Newton fractal for $p (z) = z 5 - 3 i z 3 - (5 + 2 i) z 2 + 3 z + 1$ , coloured by root reached, shaded by number of iterations required	Newton fractal for $p (z) = s i n (x)$ , coloured by root reached, shaded by number of iterations required

[edit] See also

Wikimedia Commons has media related to:

Newton fractal

Curtis McMullen

J. H. Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton's Method Preprint (2000), Inventiones Mathematicae vol. 146 (2001) – with a discussion of the global structure of Newton fractals

Retrieved from "http://en.wikipedia.org../../../n/e/w/Newton_fractal.html"

Categories: Numerical analysis | Fractals

Newton fractal

From Wikipedia, the free encyclopedia

[edit] See also

Views

Navigation

Search

In other languages