• December 11, 2017, 03:55:18 PM

Login with username, password and session length

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

0 Members and 1 Guest are viewing this topic.

Offline claude

  • 2b
  • **
  • Posts: 168
    • 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 Fanatic
  • ***
  • Posts: 25
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

  • 2b
  • **
  • Posts: 195
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

  • 2b
  • **
  • Posts: 195
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 Fanatic
  • ***
  • Posts: 25
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

  • 2b
  • **
  • Posts: 195
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

  • 2b
  • **
  • Posts: 195
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 Fanatic
  • ***
  • Posts: 25
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

  • 2b
  • **
  • Posts: 195
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 Fanatic
  • ***
  • Posts: 25
Re: Newton-Raphson zooming
« Reply #54 on: Yesterday at 12:59:07 PM »
Yes! still cool!  :)

Offline gerrit

  • 2b
  • **
  • Posts: 195
Re: Newton-Raphson zooming
« Reply #55 on: Today at 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.