Newton's fractal

The Newton fractal too ${\displaystyle p(z)=\!\,z^{3}-1}$

The Newton's fractal to a non-constant meromorphic function that maps the complex numbers in itself is a subset of the set of complex numbers. More precisely, it is the Julia set for function ${\displaystyle p}$ ${\displaystyle {\mathcal {J}}_{f}}$

${\displaystyle f\colon z\mapsto f(z)=z-{\frac {p(z)}{p'(z)}},}$

which describes the Newton method for finding zeros of the function . The Newton method itself constructs a sequence with the recursion rule from a starting value . ${\displaystyle p}$ ${\displaystyle z_{0}}$ ${\displaystyle z_{k+1}=f(z_{k})}$

Depending on the start value , the orbit can vary from ${\displaystyle z=z_{0}}$ ${\displaystyle z}$

${\displaystyle z,\;f(z),\;f^{2}(z),\;f^{3}(z),\,\ldots }$

show very different behavior.

Note: Here the exponent refers to as a function, not its function value. means the -fold iterated application of to (or the -th iterate of ), so formally . ${\displaystyle f}$ ${\displaystyle f^{\,n}}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle z}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle f^{\,0}(z)=z,\,f^{\,n+1}(z)=f(f^{\,n}(z))}$

There are exactly two possibilities for the dynamics in an environment of : ${\displaystyle z}$

1. there is a neighborhood of such that the sequence of the distances is limited, or ${\displaystyle z}$ ${\displaystyle \|z-w\|,\;\|f(z)-f(w)\|,\;\|f^{2}(z)-f^{2}(w)\|,\,\ldots }$
2. for every (no matter how small) environment of , the images cover the entire complex plane including the point infinite (i.e. the entire Riemann number sphere). ${\displaystyle U}$ ${\displaystyle z}$ ${\displaystyle U,\;f(U),\;f^{2}(U),\;f^{3}(U),\,\ldots }$

The points in the first case form the Fatou set of , the points in the second case the Julia set . In the Fatou set it can happen, in particular, that the sequence of the distances converges to zero, i.e. the orbits of points approach the orbit of . If it has at least three zeros, the Julia set is always a “ fractal ”; therefore it is sometimes also called “ Newton's fractal of ”. ${\displaystyle {\mathcal {F}}_{f}}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {J}}_{f}}$ ${\displaystyle w}$ ${\displaystyle z}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {J}}_{f}}$ ${\displaystyle {\mathcal {J}}_{f}}$ ${\displaystyle p}$

Significance for the Newton method

If the starting value of the Newton iteration is close to a single zero , then the method converges quadratically to this zero (i.e. the number of correct decimal digits doubles in each step in the long term). With a multiple zero, the Newton method is still linearly convergent. Zeros are always in the Fatou set. ${\displaystyle p}$

However, the closer the starting value is to the Julia set, the more confusing the result of Newton's method is:

• Even starting values ​​that are far away from a zero can converge towards this, even if other zeros are significantly closer to the starting value (for case 1).
• There are start values ​​that do not converge towards a zero, but only towards a periodic cycle (for case 1). An example of this is the polynomial . Here there are starting values ​​that are captured by the attractive cycle {0,1} so that entire surfaces in the plane do not converge towards any zero point. ${\displaystyle z^{3}-2z+2}$
• If the start value is in the Julia set itself, then it does not converge to a zero (for case 2).

Surprisingly, the Julia set (the Newton's fractal) can also have a positive measure in the plane: this means that random starting values ​​lie in the Julia set and therefore do not converge to a zero (or another attractive cycle of ) (this behavior only comes in a few cases and was only proven a few years ago, but is quite possible). Even if the Newton fractal is a zero set, there can be entire areas in which the method does not converge to a zero. ${\displaystyle f}$

This statement also applies to real-valued rational functions. Again, the polynomial is used as an example. Because it has real coefficients, the values ​​of the Newton iteration for real start values ​​remain real-valued. Since the real axis runs through areas of non-convergence, there are intervals for which there is no convergence. There are infinitely many such intervals. ${\displaystyle z^{3}-2z+2}$

Sample fractals

example 1

Figure 1: Newton's fractal to ${\displaystyle z^{3}-2z+2}$

Figure 1 shows the Newton fractal (in white) , color-coded according to the speed of convergence and the three zeros. Starting values ​​that lie in the areas drawn in beige converge towards the same zero (in the picture on the left in light beige), analogously for the green and blue areas. The zeros to the green or blue area are symmetrical to the horizontal symmetry axis on the right in the picture. The faster a start value converges to its zero, the lighter it is colored. The values ​​in the infinitely many red areas do not converge towards a zero, but are caught by the attractive cycle . The Newton fractal - recognizable as a light structure in the picture - is not restricted. In the three directions to be recognized, it extends to ∞. ${\displaystyle z^{3}-2z+2}$ ${\displaystyle \{0,1\}}$

Example 2

Figure 2: Newton's fractal to a polynomial with 7 randomly chosen zeros

Figure 2 shows the Newton fractal for a polynomial with 7 randomly chosen zeros (white dots), the area represents . The fractal itself is z. B. the edge of the yellow area. It is also the edge of the green area, the edge of the turquoise area, etc. This property is common to all Julia sets. (The colors red and pink were used twice; however, the boundaries of the red and pink areas correspond to the Newton fractal.) ${\displaystyle -1<\operatorname {Re} (z),\operatorname {Im} (z)<1}$

Web links

Commons : Newton Fractal  - album containing pictures, videos and audio files

• JH Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton's Method . In: Inventiones Mathematicae , vol. 146, 2001 - with discussion of the structure of Newton's fractals
• D. Schleicher, Robin Stoll: Newton's method in practice: finding all roots of polynomials of degree one million efficiently. Description of Newton's method in practice, with which all zeros of certain polynomials of degrees over a million are found, arxiv : 1508.02935