I mentioned this paper in gerrit's thread about Newton-Hines (

https://fractalforums.org/fractal-mathematics-and-new-theories/28/newton-hines-fractals/2737/msg15710#new) but I thought it'd be best to start a thread for this (I am trying to write code that prints out the set of valid starting points in symbolic form for Newton's method on root finding. Did anyone already do this - so I could compre my results to?).

How to find all roots of complex polynomials by Newton’s method

John Hubbard, Dierk Schleicher, Scott Sutherland

Digital Object Identifier

Invent. math. 146, 1–33 (2001)

Short recap: For any polynomial there can be constructed a set of finite many points so that for every root of the polynomial there is at least one starting point in that set that converges by Newton's method to that specific root. And that set is only dependent on the degree of the polynomial.

From what I understood, the process of the paper works because each root has a basin of attraction that forms (at a certain distance from the origin) a channel going out to infinity - and if one starts with a point in that basin far away from all the roots the channels become in shape what their name suggests: channels, and one can place the Newton-iteration starting points on a circle around the origin. Larger circles are always possible but increase the number of Newton iteration steps required to arrive at a certain distance to a root.

As a start, here is a set of symbolic points (hopefully correctly calculated) for a simple degree d=2 polynomial - constructed by hand, since it needs some calculations of log and I am currently trying to understand the error propagation of that.

Polynomial \( f(z)=a_2\cdot z^2 + a_1\cdot z + a_0 \)

Estimate for the magnitude of the roots: (Lagrange's estimation used as it resembles the formula to calculate a sufficiently large escape radius for polynomial Julia sets): \( R=max \{ 1, |\frac{a_0}{a_2}| + |\frac{a_1}{a_2}| \} \)

From their section 9 ("the recipe for dessert", as the authors call it) I figuered:

Number of circles needed: \( s=\lceil 0.26632*log(d)\rceil = 1 \)

Number of points per circle: \( N=\lceil 8.32547*d*log(d) \rceil = 12 \)

and then use double that value to ensure that there are points not too close to the basin's boundary, hence N=24

The radius of the circles (if all roots were in the unit disk): 1 <= v <= s

\[ r_v=(1+\sqrt 2)*(\frac{d-1}{d})^{\frac{2v-1}{4s}} \]

hence \( r_1=(1+\sqrt 2)*\frac{1}{2}^{\frac{1}{4}} <= 2.5 \) (to have a computer-representable value)

The angles of the points: 0 <= j < N: \( \theta _j=\frac{2\pi \cdot j}{N} \)

so the final set of starting points be:

\[ \{ 2.5 \cdot R \cdot e^{\frac{1 \cdot 2i \pi}{24}}, 2.5 \cdot R \cdot e^{\frac{2 \cdot 2i \pi}{24}}, ... 2.5 \cdot R \cdot e^{\frac{23 \cdot 2i \pi}{24}} \} \]Linkback: https://fractalforums.org/fractal-mathematics-and-new-theories/28/finding-all-roots-of-a-polynomial-with-mathematical-guarantee/2959/