### Finding all roots of a polynomial with mathematical guarantee

• 32 Replies
• 839 Views

0 Members and 1 Guest are viewing this topic.

• 3f
• Posts: 1652

#### Re: Finding all roots of a polynomial with mathematical guarantee

« Reply #30 on: September 10, 2019, 03:49:09 PM »
Doesn't look wrong to me. The larger blue regions ring the more prominent preimages of infinity, so I'd expect the first iteration there to jump to well outside the region immediately surrounding the origin, though the points then come tumbling back in toward roots from there. Mostly. The ones in black regions excepted.

#### marcm200

• Fractal Frankfurter
• Posts: 562

#### Re: Finding all roots of a polynomial with mathematical guarantee

« Reply #31 on: September 11, 2019, 08:42:07 AM »
This might be a bit over-informative, but I like the picture below (same polynomial as in my last post)

Black = non-root-convergent.
Blue = root-convergent, but first iterate increases distance to its root.

White = one iterate from a blue point leads to the white ones. They cluster in some regions, in others they're sparse (I suspect this to be a result of image resoution and point sample grid width). The right side next to the blue football looks a bit like a magnetic field. The white points often form a nice grid, almost looking like field lines closing in on a pole.

red = one Newton iterate from there hits the blue region (so kind of the blue's direct basin of (temporary) attraction)

dark gray = background color

Some pixels might (not checked) actually need more than one color, so red takes priority over white and that over blue.

Some blue points go directly to other blue points, some blue points jump outside the 1.5-square here (like pauldelbrot indicated in his latest post).

Second image is the 3-Lagrange overview. The red basin does not extend there, but some white pixels lie way outside the 1.5-square.

Overall I got the impression that any problematic region for Newton's method lies deep within the Lagrange estimate (non-convergent parts outside get smaller relative to the channels), so taking a starting point outside circumvents pretty much every obstacle, making the universal set quite appealing in the sense that most of the time way fewer than those calculated starting numbers might actually be necessary to find all roots.

#### marcm200

• Fractal Frankfurter
• Posts: 562

#### Re: Finding all roots of a polynomial with mathematical guarantee

« Reply #32 on: October 30, 2019, 09:21:33 AM »
This is an interesting extension of the universal starting points method.

Code: [Select]
"Root finding methods: a dynamical approach"Master thesis, Javier Olea Martinez, 2015
The auther studies functions of the form f(z)=P(z)*e^Q(z) where P, Q are polynomials. f and P have the same roots, and the Newton map of f is a rational function whose dynamics has changed compared to that of P. Infinity now is a parabolic fix point, and the immediate basins of the roots are quite small. The number of needed points in a universal set can be reduced and spread on a line segment instead of one or more circles.

### Similar Topics

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

Started by marcm200 on Fractal Mathematics And New Theories

4 Replies
277 Views
June 18, 2019, 11:31:40 PM
by gerrit
###### Roots of polynomials

Started by Ebanflo on Fractal Mathematics And New Theories

3 Replies
310 Views
March 26, 2018, 10:20:28 PM
by claude
###### Placing complex roots in the shape of words

Started by marcm200 on Share a fractal

11 Replies
362 Views
November 06, 2019, 04:49:30 PM
by gerrit
###### Finding Misiurewicz points

Started by gerrit on Fractal Mathematics And New Theories

3 Replies
263 Views
March 12, 2018, 05:48:47 PM