Finding all roots of a polynomial with mathematical guarantee

  • 32 Replies
  • 731 Views

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« on: July 28, 2019, 04:03:36 PM »
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?).

Quote
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/


Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #2 on: August 01, 2019, 07:59:52 PM »
Here is a first experimental result: A degree 15 polynomial with complex coefficients chosen at random from the complex 4-square. The Lagrange estimate is R=14.   .

The first image shows the 3*R-square of the complex plane and depicts nicely the crucial point of the article. Far away from the roots (the Lagrange region is indicated by a black circle), the basin of attraction for any root is very regular (apart from its boundary), so it is entirely possible to put points on a (2nd) circle around the origin so that every channel gets at least one point. And those points are independent from the coefficiants, only the degree is important. The universel set of points is indicated by small crosses outside the R-circle (looks more like a picket fence due to their denseness).

The second image shows a closeup of the center region where the zeros lie (small squares with a completely different color than their surrounding).

I am currently trying to recreate the images from the article and later intend to use especially polynomials where there is a large portion of non-Newton-converging complex points.

Is there a specific polynomial where this portion is as large as possible? I've read that the Newton formula seen as a rational map has attracting cycle(s) (sometimes? always?), so those won't converge to a root I suppose.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1842
« Reply #3 on: August 02, 2019, 01:27:27 AM »
What happens if 2 roots are very close? Don't you need more and more initial guesses to distinguish them? (Asking, I have no idea.)

Online pauldelbrot

  • *
  • 3f
  • ******
  • Posts: 1521
« Reply #4 on: August 02, 2019, 09:49:48 AM »
I'd be more concerned about the case where three roots were very close. That the basin for the one in the middle could become arbitrarily narrow, in degrees-of-arc terms.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #5 on: August 02, 2019, 09:54:50 AM »
What happens if 2 roots are very close? Don't you need more and more initial guesses to distinguish them? (Asking, I have no idea.)

According to the article even for the worst-case polynomial of degree d with the nastiest coefficients possible each (immediate, i.e. where the root itself lies within) basin, has a minimal width (p 15, "5. Hitting the channels", 1st paragraph).

And this lower width is universal and not dependent on the coefficients (p 30, "... is a universal set of starting values and must allow for the smallest basin of the worst-case polynomial of degree d").

(Sorry, for just citing the article, but I haven't figuered out the math quite yet as to be able to point to the specific equation).

I'd be more concerned about the case where three roots were very close. That the basin for the one in the middle could become arbitrarily narrow, in degrees-of-arc terms.
From what I gathered while reading the text their argument of a minimal width stems from the general shape of the channel-like basins in a large (compared to the roots' position) distance to them, so that they (somehow) can approximate the basins there to a definite minimal width.


Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1842
« Reply #6 on: August 02, 2019, 06:13:43 PM »
Yes, 3 roots as pauldelbrot says. Say roots are  1/2-q, 1/2, 1/2+q with q tiny. With real numbers it seems to me the attraction basin of 1/2 will shrink to 0 if q-->0. For complex the basins are laser beams, very sharply tipped cones.

Seems like in their "practical" section 9 they do not say how they derive their unnumbered formula from other (unnumbered) formulas.
I haven't found an epsilon such that delta is greater than zero and I understand delta words of it.


Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #7 on: August 02, 2019, 07:01:58 PM »
(Well, seems like I'm the defender of the article   ;D)

Proposition 7 on page 11 states "every basin has a channel with modulus at least \( pi / log(degree) \), so for me that means no matter how close the roots are, there's a channel with a positive width that depends only on the degree. Or did I misunderstand that claim?

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1842
« Reply #8 on: August 02, 2019, 07:22:54 PM »
(Well, seems like I'm the defender of the article   ;D)

Proposition 7 on page 11 states "every basin has a channel with modulus at least \( pi / log(degree) \), so for me that means no matter how close the roots are, there's a channel with a positive width that depends only on the degree. Or did I misunderstand that claim?

They are talking about the width of channels measured by "conformal modulus of the annulus formed by the channel modulo the dynamics", but to me that's experimental poetry.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #9 on: August 02, 2019, 07:55:10 PM »
...but to me that's experimental poetry.

Nice! I'm glad I'm not the only one not understanding the math part. But I focus more on sentences like this: "It will serve to measure the width of the channel. We will now provide a lower bound on these moduli." (directly above proposition 7).

Do you think the article is faulty? I haven't found a retraction or a correction note for it, so I currently am using it as is. I mean the idea of a universal set is simply great.

EDIT: I think the choice of words "lower bound of a channel width" is a bit misleading. What they meant to say was that every immediate basin has in a region far away from the roots (outside the Lagrangian estimate in my case, outside the unit disk in their case) a minimal width, and this is universal for a specific polynomial degree. Near the roots, if they are close, those channels might in deed get arbitrarily thin as you mentioned.

« Last Edit: August 02, 2019, 10:38:50 PM by marcm200, Reason: Clarification of thought »

Offline hobold

  • *
  • Fractal Friar
  • *
  • Posts: 115
« Reply #10 on: August 03, 2019, 11:57:12 AM »
If I had to construct a counterexample, my first intuition would be this:

Choose five distinct (non-overlapping) points on the same straight line as the roots of the polynomial. The two outermost points will remain invariant (they are there just to bracket the whole construction). Let the inner three points be within epsilon of each other. Then let epsilon gradually tend towards zero.

Open questions: does the (relative) location of the middle / center point matter?

Relevant observations to be made: does the channel width (of the central root) really not shrink to zero as epsilon tends to zero?

Edit:
It seems to me that even if a few counterexamples exist, the paper's main theorem could still be true in a statistical sense: with probability one.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #11 on: August 03, 2019, 01:23:22 PM »
Relevant observations to be made: does the channel width (of the central root) really not shrink to zero as epsilon tends to zero?

Shrink to zero where in the complex plane? Around the root itself?
It might have that as a mathematical limit, but since between two distinct complex points there's always positive distance so there's always room for a channel to be at a given spacing of your five distinct points (maybe it happens that the channel will in some instances become just a line, that I don't know).

EDIT: But, of course you're right that a limit of zero would counteract a lower bound on the channel width, if the whole channel were to be considered.

But the article speaks about the channel width at a great distance to the origin and therefore the root itself (page 13, "restricting any channel to the exterior of the unit disk...") And each immediate basin has a channel to infinity (proposition 6, p11), so there's always a channel for every root in every distance to the root.



Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #12 on: August 03, 2019, 07:07:47 PM »
I took the 0.5-q, 0.5, 0.5+q triplex suggestion and illustrated a degree 15 polynomial with 3 roots being close together and the other 12 randomly chosen in the 4-square.

The image below shows q=0.1 (left column) as a control, and p=0.0001 (right column). The upper row shows the overview: the Lagrange estimate (black circle), the universal set of points (picket fence outside the Lagrange circle). The bottom row shows a close up of the  region where the roots of interest lie (red rectangle with red dots).

The roots of interest have black, white and gray as a color of their basin, the other colors are not necessarily the same in the two columns (they get assigned by order of roots found), but the two polynomials have the same 12 random roots.

The closeup nicely showed hobold's thought of the basins getting closer at the tip, and the overview illustrates that outside the Lagrange estimate the channels are quite regular ("linear" as it is called in the article).

If anyone can get q to a tinier value, that would be interesting (I mean 0.0001 is not really tiny, but I am already concerned about numerical error using a degree 15 polynomial and double precision -  as the sum q^15 + q is outside the representable values for q=0.0001).

Side question (unrelated to the article): Does any basin of attraction for a root using Newton's method have an area - or can there be isolated points?



Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1842
« Reply #13 on: August 03, 2019, 08:57:32 PM »
Nice! I'm glad I'm not the only one not understanding the math part. But I focus more on sentences like this: "It will serve to measure the width of the channel. We will now provide a lower bound on these moduli." (directly above proposition 7).

Do you think the article is faulty? I haven't found a retraction or a correction note for it, so I currently am using it as is. I mean the idea of a universal set is simply great.

EDIT: I think the choice of words "lower bound of a channel width" is a bit misleading. What they meant to say was that every immediate basin has in a region far away from the roots (outside the Lagrangian estimate in my case, outside the unit disk in their case) a minimal width, and this is universal for a specific polynomial degree. Near the roots, if they are close, those channels might in deed get arbitrarily thin as you mentioned.
I don't think the article is wrong as I try to avoid having opinions on stuff I don't understand.

I planned to do exactly what you did in your last post, thanks.

On a circle radius R around 0, for large R you can look at the angles  0-1 (or 0-360 degrees) and consider which angles converge to root x; this will be 1 (?) interval per root. The paper claims R = sqrt(2) is always large enough, correct? And it seems that the angle interval for the central root in your example is not dependent on how close the other 2 are, which is surprising.

Still trying to understand it, I printed out the article on paper, see if that helps.

What if you'd run the Newton method backwards? If you start within eps from each root you'll get say 15 curves becoming straight lines (rays)  to inf at large R. The 3 curves of the 3 nearby roots (.5-q,.5,.5+q) start off very close (q) together but at large R they fan out and all rays are more or less uniform over the angles. And R=sqrt(2) is always "large enough"?

Those "rays" are cool, they remind me of the Mandelbrot set "external rays", could there be a relation? Attached the Newton method for z^2+c iterated 8 times from z=0 (as polynomial in c). There should be 128 channels each going to a mini. They don't look uniform.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 492
« Reply #14 on: August 03, 2019, 09:37:05 PM »
The paper claims R = sqrt(2) is always large enough, correct?
I understood that 1+sqrt(2) is always large enough if all roots lie within the unit disk, otherwise one has to scale the radius (I do it by the Lagrange estimate) (chapter 9, paragraph 2 "scale by r" and the formula for \( r\nu \) (omitting all the (d-1)/d etc. part as it is bounded from above by 1.

Your backward iteration is a good idea, I haven't thought of that.



xx
Exterior DE: Is there a mathematical guarantee at finite R?

Started by marcm200 on Fractal Mathematics And New Theories

4 Replies
265 Views
Last post June 18, 2019, 11:31:40 PM
by gerrit
clip
Roots of polynomials

Started by Ebanflo on Fractal Mathematics And New Theories

3 Replies
290 Views
Last post March 26, 2018, 10:20:28 PM
by claude
clip
Placing complex roots in the shape of words

Started by marcm200 on Share a fractal

11 Replies
282 Views
Last post November 06, 2019, 04:49:30 PM
by gerrit
clip
Finding Misiurewicz points

Started by gerrit on Fractal Mathematics And New Theories

3 Replies
246 Views
Last post March 12, 2018, 05:48:47 PM
by Adam Majewski
xx
Finding interesting zoom points

Started by mikoval on Fractal Mathematics And New Theories

3 Replies
232 Views
Last post September 18, 2018, 11:59:09 PM
by mikoval