Finding all roots of a polynomial with mathematical guarantee

  • 31 Replies

0 Members and 1 Guest are viewing this topic.

Offline pauldelbrot

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