Newton-Raphson zooming

  • 57 Replies
  • 1880 Views

0 Members and 1 Guest are viewing this topic.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« Reply #45 on: December 05, 2017, 09:30:00 PM »
IMHO, the numerical accuracy it is not a problem per se for evaluation the radius of the ball. One have only to make sure that ball conservatively covers the outcome of the operation.

I think there will be a problem if you have insufficent precision, such that |z|+r = |z| in your low precision type.

Offline knighty

  • *
  • Fractal Feline
  • **
  • Posts: 169
« Reply #46 on: December 05, 2017, 09:50:25 PM »
I  never got that problem and don't really care because IA is so conservative that rounding errors are usually "shadowed". We don't need to be too careful for these application. In more serious application and projects that cost Billions one really need to care. Anyway, I may be wrong (and probably is ;) )

Glad it worked for both of you. Just keep in mind that the root finding algorithm reports roots many times (0 to 4). One have to clean the list of roots.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #47 on: December 06, 2017, 01:26:44 AM »
Just for fun I ran the ball period finding algorithm on all pixels in the attached location. The 2nd attachments shows the result for the period detected in false color (0=nothing found). Upper graph using zero'th order (as in the box method), bottom graph using the first order "Taylor-ball method" which I finally understood. Obviously a big improvement.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #48 on: December 06, 2017, 01:55:16 AM »
Why is the minimal separation between period p roots \( 2^{-p} \)? Found it in the mandelroots code.

Offline knighty

  • *
  • Fractal Feline
  • **
  • Posts: 169
« Reply #49 on: December 06, 2017, 11:27:13 AM »
Why? I don't know. That was empirical / wild guess. This poster gives better insight (see "largest roots of p_k()" and "interlacing").

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #50 on: December 06, 2017, 05:54:43 PM »
OK, thanks. Here's the thesis going with the poster: http://ir.lib.uwo.ca/cgi/viewcontent.cgi?article=5704&context=etd
Never heard of the Fibonacci-Mandelbrot set before.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #51 on: December 07, 2017, 01:34:33 AM »
Calculated period of each pixel using ball method + NR, then plot the periods image in false color (so each pixel with a color has a verified nucleus in it). Attached result and location in DE rendering. Interestingly the period plot reveals some spiraly pattern that is not obvious in the normal rendering. In MATLAB you can click on a pixel and read off the period. Probably useless, but fun.

Offline knighty

  • *
  • Fractal Feline
  • **
  • Posts: 169
« Reply #52 on: December 07, 2017, 11:39:41 AM »
Wow! That's cool!
How much time did it take to compute?
Have you checked for duplicates? The method can give a root that is actually outside the probed pixel.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #53 on: December 07, 2017, 04:52:42 PM »
Takes about 2-3 times longer than just the iteration + derivative (less than a second for this one).
I just carry along the ball iterations and check if a period is detected, if so refine location with Newton and tolerance of 1/10th pixel radius (you get the first iteration for free).
Usually 1-3 iterations is enough. Then accept if result is still within the pixel.

Edit: I had a bug, corrected picture attached (no more spirals, still cool I hope:)
« Last Edit: December 07, 2017, 11:33:19 PM by gerrit »

Offline knighty

  • *
  • Fractal Feline
  • **
  • Posts: 169
« Reply #54 on: December 10, 2017, 12:59:07 PM »
Yes! still cool!  :)

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #55 on: December 11, 2017, 02:05:01 AM »
Here's another hopefully interesting picture.
Top-left all pixels for which ball method found a period.
Top-right what is left over after verifying with Newton method that there is a nucleus.

For distance estimate definition \( d_e = |z_n|\log|z_n|/|z'_n| \) we have
\( d_e/2 \leq d \leq 2d_e \) with \( d \) the true distance to the boundary.
If R is half the pixel distance it follows that if
\( R>2d_e \) there is a nucleus in the pixel
\( R<d_e/(2\sqrt{2}) \) there is no nucleus in the pixel
otherwise could be either way.

Middle-left shows the yes and maybe pixels. Middle right where DE is sure there is a nucleus but ball+NR didn't find it.
Bottom-left periods missed by the ball method alone, bottom-right ball false positives.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« Reply #56 on: December 12, 2017, 02:37:28 AM »
Why is the minimal separation between period p roots \( 2^{-p} \)? Found it in the mandelroots code.

I think the two period P roots nearest the tip of the antenna are approximately 2-2P apart, at least that is what this short numerical experiment indicates:

Code: [Select]
#include <mandelbrot-numerics.h>

int main()
{
  mpfr_t distance;
  mpfr_init2(distance, 53);
  for (int period = 4; period <= 65536; period <<= 1)
  {
    mpc_t nucleus[3];
    mpc_t delta;
    mpc_init2(nucleus[0], 4 * period);
    mpc_init2(nucleus[1], 4 * period);
    mpc_init2(nucleus[2], 4 * period);
    mpc_init2(delta, 4 * period);
    mpc_set_si(nucleus[0], -2, MPC_RNDNN);
    mpc_set_si(nucleus[1], -2, MPC_RNDNN);
    m_r_nucleus(nucleus[0], nucleus[0], period, 64);
    m_r_nucleus(nucleus[1], nucleus[1], period + 1, 64);
    mpc_sub(delta, nucleus[0], nucleus[1], MPC_RNDNN);
    mpc_add(nucleus[2], nucleus[0], delta, MPC_RNDNN);
    m_r_nucleus(nucleus[2], nucleus[2], period + 1, 64);
    mpc_sub(delta, nucleus[1], nucleus[2], MPC_RNDNN);
    mpc_abs(distance, delta, MPFR_RNDN);
    mpfr_log2(distance, distance, MPFR_RNDN);
    mpfr_div_si(distance, distance, period, MPFR_RNDN);
    mpfr_printf("%6d\t%Re\n", period, distance);
    mpc_clear(nucleus[0]);
    mpc_clear(nucleus[1]);
    mpc_clear(nucleus[2]);
    mpc_clear(delta);
  }
  return 0;
}

output:

Code: [Select]
     4  -7.5096990924173856e-01
     8  -1.3888901895836767e+00
    16  -1.6945028256046299e+00
    32  -1.8472514137604439e+00
    64  -1.9236257068802221e+00
   128  -1.9618128534401109e+00
   256  -1.9809064267200556e+00
   512  -1.9904532133600277e+00
  1024  -1.9952266066800139e+00
  2048  -1.997613303340007e+00
  4096  -1.9988066516700034e+00
  8192  -1.9994033258350017e+00
 16384  -1.9997016629175008e+00

I have a hunch that the two period P roots closes to the tip of the antenna are the closest pair of period P roots, though I don't have a proof.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« Reply #57 on: December 12, 2017, 05:42:52 AM »
Thanks Claude, that looks like an excellent conjecture.
I found a writeup on roots here
Code: [Select]
ftp://nozdr.ru/biblio/kolxo3/Cs/CsCa/Yap%20C.K.%20Fundamental%20problems%20in%20algorithmic%20algebra%20(web%20draft,%202000)(O)(550s)_CsCa_.pdfwhich in "lecture 6" also discusses bounds on basin of attraction for Newton's method.
Probably too much for me to digest but maybe you get something out of it if you don't know it already.


xx
Newton-Raphson zooming for Burning Ship

Started by claude on Fractal Mathematics And New Theories

9 Replies
396 Views
Last post January 08, 2018, 03:03:56 PM
by knighty
xx
Newton-Raphson Fractal attempt in Xaos

Started by Know That Fractal! on Fractal Image Gallery

0 Replies
131 Views
Last post December 22, 2017, 01:40:55 AM
by Know That Fractal!
xx
Newton's Garden

Started by gannjondal on Fractal Image Gallery

4 Replies
173 Views
Last post April 17, 2018, 11:22:45 PM
by spain2points
clip
Revisiting the 3D Newton

Started by gannjondal on Fractal Mathematics And New Theories

19 Replies
1056 Views
Last post August 13, 2018, 10:19:39 AM
by Sabine62
xx
Newton (gannjondal)

Started by Sabine62 on Fractal Image Gallery

0 Replies
22 Views
Last post August 15, 2018, 04:28:09 PM
by Sabine62