Finding all roots of a polynomial with mathematical guarantee

  • 32 Replies

0 Members and 1 Guest are viewing this topic.

Offline pauldelbrot

  • *
  • 3f
  • ******
  • Posts: 1652
« 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.

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 562
« 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.

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 562
« 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.

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

Started by marcm200 on Fractal Mathematics And New Theories

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

Started by Ebanflo on Fractal Mathematics And New Theories

3 Replies
Last post 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
Last post November 06, 2019, 04:49:30 PM
by gerrit
Finding Misiurewicz points

Started by gerrit on Fractal Mathematics And New Theories

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

Started by mikoval on Fractal Mathematics And New Theories

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