• February 18, 2018, 10:59:53 PM

Login with username, password and session length

Author Topic:  Newton-Raphson zooming  (Read 1212 times)

0 Members and 1 Guest are viewing this topic.

Offline claude

  • Fractal Flamingo
  • ****
  • Posts: 348
    • mathr.co.uk
Re: Newton-Raphson zooming
« 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 Friar
  • *
  • Posts: 123
Re: Newton-Raphson zooming
« 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

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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 Friar
  • *
  • Posts: 123
Re: Newton-Raphson zooming
« 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

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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 Friar
  • *
  • Posts: 123
Re: Newton-Raphson zooming
« 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

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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 Friar
  • *
  • Posts: 123
Re: Newton-Raphson zooming
« Reply #54 on: December 10, 2017, 12:59:07 PM »
Yes! still cool!  :)

Offline gerrit

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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 Flamingo
  • ****
  • Posts: 348
    • mathr.co.uk
Re: Newton-Raphson zooming
« 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

  • Fractal Frankfurter
  • *
  • Posts: 548
Re: Newton-Raphson zooming
« 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
265 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
68 Views
Last post December 22, 2017, 01:40:55 AM
by Know That Fractal!
xx
Another possible way to accelerate MB set deep zooming

Started by knighty on Fractal Mathematics And New Theories

56 Replies
1047 Views
Last post February 15, 2018, 11:42:37 PM
by gerrit
xx
Mandelbrot set deep zooming in the web browser

Started by claude on Other

0 Replies
201 Views
Last post October 29, 2017, 11:00:15 PM
by claude
xx
Speeding up deep zooming using neural networks / deep learning?

Started by greentexas on Fractal Mathematics And New Theories

27 Replies
826 Views
Last post December 13, 2017, 10:43:46 PM
by Byte11