Newton-Raphson zooming

• 57 Replies
• 1969 Views

0 Members and 1 Guest are viewing this topic.

• 3c
• Posts: 826

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.

knighty

• Fractal Feline
• Posts: 174

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.

• 3f
• Posts: 1480

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.

• 3f
• Posts: 1480

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.

knighty

• Fractal Feline
• Posts: 174

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").

• 3f
• Posts: 1480

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.

• 3f
• Posts: 1480

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.

knighty

• Fractal Feline
• Posts: 174

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.

• 3f
• Posts: 1480

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 »

knighty

• Fractal Feline
• Posts: 174

Re: Newton-Raphson zooming

« Reply #54 on: December 10, 2017, 12:59:07 PM »
Yes! still cool!

• 3f
• Posts: 1480

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.

• 3c
• Posts: 826

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.

• 3f
• Posts: 1480

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.

Similar Topics

Newton-Raphson zooming for Burning Ship

Started by claude on Fractal Mathematics And New Theories

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

Started by Know That Fractal! on Fractal Image Gallery

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

Started by gannjondal on Fractal Image Gallery

4 Replies
196 Views
April 17, 2018, 11:22:45 PM
by spain2points
Revisiting the 3D Newton

Started by gannjondal on Fractal Mathematics And New Theories

26 Replies
1437 Views
October 01, 2018, 10:24:43 PM
by FractalDave
Newton (gannjondal)

Started by Sabine62 on Fractal Image Gallery

0 Replies
45 Views
August 15, 2018, 04:28:09 PM
by Sabine62