• October 20, 2021, 03:02:55 AM

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

0 Members and 1 Guest are viewing this topic.

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Newton-Raphson zooming
« on: October 30, 2017, 02:35:55 AM »
An old quote (Dec 2016) from Claude from the old forum.
Quote
Use box method to find the period (suggested to me by Robert Munafo), described here: http://www.mrob.com/pub/muency/period.html sample code here https://code.mathr.co.uk/mandelbrot-numerics/blob/HEAD:/c/lib/m_d_box_period.c

Using period, and initial guess in the current view, find the nucleus c where F^p(0,c)=0 using Newton's method.  sample code https://code.mathr.co.uk/mandelbrot-numerics/blob/HEAD:/c/lib/m_d_nucleus.c

Find the size estimate using formula from http://ibiblio.org/e-notes/MSet/windows.htm sample code https://code.mathr.co.uk/mandelbrot-numerics/blob/HEAD:/c/lib/m_d_size.c

Use size estimate s to choose a view radius r around the nucleus c.  Use (something like)  r = 4 s to view the minibrot, or r = 4 sqrt(s sqrt(s)) to view the final 2-fold embedded Julia set.  (Note: I'm not 100% sure on the formula for viewing the embedded Julia set, it seems to work for me most of the time, maybe Kalles Fraktaler uses a different formula?)

I implemented (ported) this in MATLAB and have some questions.

1) Finding the period and location of the nucleus works great, but the size estimate is often (almost always) much too small. I noticed in KF this is occasionally (but not almost always) a problem with NR zooming, for example you get the right location but the zoom factor is something like 1e2000000 instead of e100. As this problem happens occasionally in KF but almost always in my code: did you use a better size estimate method than in the quote or am I doing something wrong?

2) I noticed we don't have to stop the "period finding" algorithm at the first polygon surrounding the origin, but can continue the algorithm and find higher period nuclei in your starting polygon, whenever you get the polygon to surround the origin again. It seems the size estimation algorithm does not work even approximately anymore though for the higher period nuclei?

Thanks for sharing that code/information.


Linkback: https://fractalforums.org/index.php?topic=481.0

Offline claude

  • 3f
  • ******
  • Posts: 2033
    • mathr.co.uk
Re: Newton-Raphson zooming
« Reply #1 on: October 30, 2017, 03:02:32 AM »
1. Note that the size esitmate given by my code is a complex number, so you need to apply |cabs| to it to get the size as a real number (you can use carg to get the orientation, too).  Perhaps you are using just the real part or imaginary part?  Or something is over/underflowing to infinity/zero?  Or you have the wrong period?  I've not personally experienced KF going to e10000000 or whatever, a test location where it happens repeatably would help a lot (if you can provide one)

2. You need increasingly more than 4 points if you want to continue I think, because the polygon will be folded in half by the squaring at the iteration after the periodic nucleus is found.  See also "algorithm 9" from Wolf Jung's Mandel http://mndynamics.com/indexp.html which I used here: https://mathr.co.uk/blog/2017-06-05_periodicity_scan_revisited.html

2.b the Newton's method for nucleus finding can give results far from the initial guess (the basins of attraction are fractal) or fail entirely.  be sure you have converged to a nucleus before trying to get its size

2.c the size finding algorithm is sensitive to having the correct period for the nucleus.  Newton's method may converge to a lower period nucleus than expected, if its period is a factor of your target period.  You should be sure of the nucleus's true period (the lowest iteration where it returns to 0) before trying to get its size.  one way to do this is for each partial (iterations where |z| reaches a new minimum) in increasing order, try Newton's method (with guess your nucleus) at that period and see if it converges to the same location.  the first that does is true period.

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #2 on: October 30, 2017, 03:39:01 AM »
1. Note that the size esitmate given by my code is a complex number, so you need to apply |cabs| to it to get the size as a real number (you can use carg to get the orientation, too).  Perhaps you are using just the real part or imaginary part?  Or something is over/underflowing to infinity/zero?  Or you have the wrong period?  I've not personally experienced KF going to e10000000 or whatever, a test location where it happens repeatably would help a lot (if you can provide one)
Yes I use |size| of course and nothing is over/under flowing. I will report the "overshooting" in KF next time I encounter it. It's not that rare.
Quote
2. You need increasingly more than 4 points if you want to continue I think, because the polygon will be folded in half by the squaring at the iteration after the periodic nucleus is found.  See also "algorithm 9" from Wolf Jung's Mandel http://mndynamics.com/indexp.html which I used here: https://mathr.co.uk/blog/2017-06-05_periodicity_scan_revisited.html
3 points should always do, for when they surround the origin, \( F^{period}(z) \) must have a zero in the triangle as it is analytic. I've animated the algorithm using initial rectangle and indeed after finding the first period it is no longer convex and/or self intersecting. The "odd edges crossing" may not work anymore then, thanks for that insight.
Quote
2.b the Newton's method for nucleus finding can give results far from the initial guess (the basins of attraction are fractal) or fail entirely.  be sure you have converged to a nucleus before trying to get its size
I verified that the list of nuclei I get are in fact correct by inputting the locations in KF, and it  seems always correct. Of course "always" is a dangerous term.
Quote
2.c the size finding algorithm is sensitive to having the correct period for the nucleus.  Newton's method may converge to a lower period nucleus than expected, if its period is a factor of your target period.  You should be sure of the nucleus's true period (the lowest iteration where it returns to 0) before trying to get its size.  one way to do this is for each partial (iterations where |z| reaches a new minimum) in increasing order, try Newton's method (with guess your nucleus) at that period and see if it converges to the same location.  the first that does is true period.
Yes, I discard periods that are an integer multiple of any previously found periods.
I haven't found an instance where the nucleus location is incorrect (after verifying with KF), but haven't verified the periods.
Hard to believe I get the right location with the wrong period though.

PS here's my code (not that I expect you to debug my MATLAB code of course :)
Code: [Select]
function p = findPeriod(c0,dx,dy,n)
% in rectangle centered on c0 find period (up to n) of nucleus
%http://www.mrob.com/pub/muency/period.html

c = [-dx 1i*dy dx -1i*dy]+c0;
z = c*0;
p = [];
figure(55)
clf
grid on
for k=2:n
    z = z.^2 + c;
    input('asd')
    clf
    grid on
    ncrossings = 0;
    for l=1:3
        p1 = z(l);
        p2 = z(l+1);
        line( real([p1 p2]),imag([p1 p2]));
        if(crossesPosAxis(p1,p2))
            ncrossings = ncrossings+1;
        end
    end
    p1 = z(4);
    p2 = z(1);
    line( real([p1 p2]),imag([p1 p2]));
    if(crossesPosAxis(p1,p2))
        ncrossings = ncrossings+1;
    end
    axis([-1 1 -1 1]*2);
    fprintf('period = %d\n',k-1);
    if(mod(ncrossings,2)==1)
        fprintf('period found= %d\n',k-1);
        p = [p k-1];
        %break;
    end
end

function y = crossesPosAxis(a,b)

t = 1/(1-imag(b)/imag(a));
if(t<0 || t>1)
    y = 0;
else
    q = (imag(a)*real(b)-real(a)*imag(b))/(imag(a)-imag(b));
    if(q>=0)
        y = 1;
    else
        y = 0;
    end
end

function [cnucl r] = findNucleus(cguess,period,nmax,tol)
% find location and size r of nucleus with period
% https://code.mathr.co.uk/mandelbrot-numerics/blob/HEAD:/c/lib/m_d_nucleus.c

cnucl = NaN;
c = cguess;
for k=1:nmax
    [z dz] = zAnddz(c,period);
    dc = -z/dz;
    c = c + dc;
    if(abs(dc)<tol)
        cnucl = c;
        break;
    end
end
if(~isnan(cnucl))
   r = nuclSize(cnucl,period);
end

function r = nuclSize(c,period)
L = 1;
b = 1;
z = 0;
for k=1:period-1
    z = z^2 + c;
    L = 2 * z * L;
    b = b + 1/L;
end
r = 1/(b*L^2);
r = abs(r);

function [z dz] = zAnddz(c,period)
z = 0;
dz = 0;
for k=1:period
    dz = 2*z*dz + 1;
    z = z^2 + c;
end

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #3 on: October 30, 2017, 04:14:36 AM »






Code: [Select]
Re: -1.999403065371045427976003867720769568166885883022791237249771503247238028499716947798969346518070800
Im: -0.000000311366955701668923416100857227316774151686898815273002856634880548067779975665001108944020748
Zoom: 4.42e064
Iterations: 51261
IterDiv: 1.000000
SmoothMethod: 0
ColorMethod: 0
Differences: 0
ColorOffset: 0
Rotate: 0.000000
Ratio: 360.000000
Colors: 0,0,0,41,35,190,132,225,108,214,174,82,144,73,241,241,187,233,235,179,166,219,60,135,12,62,153,36,94,13,28,6,183,71,222,179,18,77,200,67,187,139,166,31,3,90,125,9,56,37,31,93,212,203,252,150,245,69,59,19,13,137,10,28,219,174,50,32,154,80,238,64,120,54,253,18,73,50,246,158,125,73,220,173,79,20,242,68,64,102,208,107,196,48,183,50,59,161,34,246,34,145,157,225,139,31,218,176,202,153,2,185,114,157,73,44,128,126,197,153,213,233,128,178,234,201,204,83,191,103,214,191,20,214,126,45,220,142,102,131,239,87,73,97,255,105,143,97,205,209,30,157,156,22,114,114,230,29,240,132,79,74,119,2,215,232,57,44,83,203,201,18,30,51,116,158,12,244,213,212,159,212,164,89,126,53,207,50,34,244,204,207,211,144,45,72,211,143,117,230,217,29,42,229,192,247,43,120,129,135,68,14,95,80,0,212,97,141,190,123,5,21,7,59,51,130,31,24,112,146,218,100,84,206,177,133,62,105,21,248,70,106,4,150,115,14,217,22,47,103,104,212,247,74,74,208,87,104,118,250,22,187,17,173,174,36,136,121,254,82,219,37,67,229,60,244,69,211,216,40,206,11,245,197,96,89,61,151,39,138,89,118,45,208,194,201,205,104,212,73,106,121,37,8,97,64,20,177,59,106,165,17,40,193,140,214,169,11,135,151,140,47,241,21,29,154,149,193,155,225,192,126,233,168,154,167,134,194,181,84,191,154,231,217,35,209,85,144,56,40,209,217,108,161,102,94,78,225,48,156,254,217,113,159,226,165,226,12,155,180,71,101,56,42,70,137,169,130,121,122,118,120,194,99,
Smooth: 1
MultiColor: 0
BlendMC: 0
MultiColors:
Power: 2
FractalType: 0
Slopes: 0
SlopePower: 50
SlopeRatio: 50
SlopeAngle: 45
imag: 1
real: 1
SeedR: 0
SeedI: 0
FactorAR: 1
FactorAI: 0
Try NR on the location indicated, or close. Try a few times, (upper "here" is worse); a small change in "click" location will work. Close to the branch point gives "NR can't be applied", further away it works, but there is a range where you get a zoom of -1e^e9 or something like that.


Offline claude

  • 3f
  • ******
  • Posts: 2033
    • mathr.co.uk
Re: Newton-Raphson zooming
« Reply #4 on: October 30, 2017, 08:42:37 AM »
Quote
Hard to believe I get the right location with the wrong period though.
Without further information I can't conclude otherwise.  Newton's method to find a nucleus of period P can also converge to a nucleus of period Q where P = n Q with n an integer.  This will make z very near zero within the 1..period-1 range, -> L near zero -> b huge -> size tiny.  You could try doing the box period stuff again, centered on the nucleus with radius 4^{-p} or so, because the smallest nucleus of a given period is in the antenna with size O(16^{-p}) and atom domain size O(4^{-p}) (see https://mathr.co.uk/blog/2017-05-22_on_the_precision_required_for_size_estimates.html , not sure if this is the smallest atom domain for a minibrot of a given period though it seems possible...)

Thanks for the problem location, I tested and managed to reproduce it, crazy zoom figure and near-crash (hangs for some time).  I fixed the symptoms (to be released in 2.12.5 this week) by failing if the computed zooms is more than 4*period, which should be impossible as that corresponds to the smallest minibrot of the given period.  An unsatisfying hack, until I get around to figuring out exactly why the gigantic values were appearing.
« Last Edit: October 30, 2017, 09:50:35 AM by claude »

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #5 on: October 30, 2017, 04:48:24 PM »
Thanks Claude, I'm going to kick around this NR zooming some more, if it works for you I must be doing something wrong.

Overshooting in KF NR is not uncommon, usually not by such extreme factors though and you can just back out to recover. Hard to bug-report as you lose the location that triggered it.

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #6 on: October 31, 2017, 03:36:18 AM »
Got it to work, including size estimation, either with triangles, or with a rectangle. With rectangle after finding the lowest period it becomes more complicated to decide if the points surround the origin due to self-intersection if you keep original order. Isn't a triangle faster anyways (as NR zooming gets slow at great depths)?

If you continue after finding the lowest period until one of the initial points goes to "infinity" you get a few more nuclei, though it is sort of random which ones you find. See example below, I verified all the black squares in the top figure (indicating where I found them) are in fact correct by inputting the location with appropriate zoom factor determined by the size estimate into KF.

Offline hapf

  • Fractal Friend
  • **
  • Posts: 17
Re: Newton-Raphson zooming
« Reply #7 on: November 02, 2017, 11:39:14 AM »
Interesting discussions on this new forum going on...
I use triangles for this and had no issues so far except sometimes nothing is found. But
that is due to the points escaping too early, I think.

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #8 on: November 23, 2017, 08:38:16 PM »
I managed to accelerate the Newton-Raphson part of the nucleus finding method.

Idea is to compute a reference orbit from cguess in full precision, then in the NR iterations use native precision using PT with this reference orbit. Speedup is considerable, it works on all examples I tried though I suspect it could fail if cguess is "to far" in some sense.

Perhaps something similar can be done for the box method to find the period, I haven't tried that yet.

Offline hapf

  • Fractal Friend
  • **
  • Posts: 17
Re: Newton-Raphson zooming
« Reply #9 on: November 24, 2017, 11:15:04 AM »
PT breaks down for NR and box method. It can work sometimes but is not reliable.

Offline claude

  • 3f
  • ******
  • Posts: 2033
    • mathr.co.uk
Re: Newton-Raphson zooming
« Reply #10 on: November 24, 2017, 02:28:24 PM »
Using perturbation for NR might "work" but the efficiency is terrible - with long double you'd get 64 extra accurate bits each iteration, whereas with full precision Newton's method should double the number of accurate bits each iteration.

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #11 on: November 25, 2017, 12:26:37 AM »
Using perturbation for NR might "work" but the efficiency is terrible - with long double you'd get 64 extra accurate bits each iteration, whereas with full precision Newton's method should double the number of accurate bits each iteration.
Yes, but I had in mind using it only to find a nucleus for reference orbit calculation for PT. In that case \( \Delta c \) needs only about 6 decimal places or something like that. (\( c_0 \) initial guess, nucleus at \( c_0 + \Delta c \).)

If \( c_0 \) has too short an orbit (before bailing out) you could use it till shortly before bailout and then switch to full precision for the rest, using the result as the next reference orbit.

I guess nobody uses this method to find reference points (except me).


Offline claude

  • 3f
  • ******
  • Posts: 2033
    • mathr.co.uk
Re: Newton-Raphson zooming
« Reply #12 on: November 26, 2017, 02:00:54 PM »
Oh, in mandelbrot-perturbator I do indeed use the low-precision derivative (needed for DE) when finding secondary references, with the implicit understanding that they are good enough for references but not for zooming..

Offline knighty

  • Fractal Feline
  • **
  • Posts: 199
Re: Newton-Raphson zooming
« Reply #13 on: November 26, 2017, 02:02:20 PM »
You can also refine the approximate solution using full precision. The refined solution would require very few iterations. Maybe one or two because the convergence is quadratic. This would be a big win over using full precision from scratch.

Quote
I guess nobody uses this method to find reference points (except me).
I do, in a slightly different manner: Find the roots of the series approximation at each iteration. I use a kind of interval arithmetic, that I learned thanks to Adam Majewski that it is called "ball arithmetic", to isolate the roots then Newton Raphson method to refine them. For the roots that have higher period than the "ultimate" series approximation one can still use series approximation and perturbation technique. I haven't tried it yet though.

One may think that this approach is extremely slow. It is not! The time spent in finding the roots is actually marginal because at most (99.99% ;) ) of the iterations there are no roots at all in the zoomed area.

While computing the SA, the first root ever found is used as reference. it is not necessary to recompute the SA from scratch, just shift the polynomial to the new location.

The advantage in having an accurate reference is that it reduces a lot the number of glitched pixels. Namely those due to the reference escaping prematurely. IMHO, this is the main weakness of KF: it computes much more secondary references than necessary.

Another advantage of finding approximate roots (while doing SA) is that they give excellent probe points (along with the corners of the rendered area) to test the SA accuracy. This is because SA overstepping errors begin to occur at the corners and/or some roots. in the second picture below, the green shades indicate where the program detects SA overstepping. The red crosses indicate the roots found while computing the SA.

Also, those roots and the ones that may be found after SA finishes should be good references for glitch correction.

Offline gerrit

  • 3f
  • ******
  • Posts: 2469
Re: Newton-Raphson zooming
« Reply #14 on: November 27, 2017, 05:07:32 AM »
The advantage in having an accurate reference is that it reduces a lot the number of glitched pixels. Namely those due to the reference escaping prematurely. IMHO, this is the main weakness of KF: it computes much more secondary references than necessary.
Indeed, when rendering deep zoom-out sequences with KF often 90% of the time is spent on additional references, often for no apparent visual reason.


xx
Newton-Raphson zooming for Burning Ship

Started by claude on Fractal Mathematics And New Theories

9 Replies
898 Views
Last post January 08, 2018, 03:03:56 PM
by knighty
xx
The Newton-Raphson method and Newton fractals, 3Blue1Brown

Started by Deliberate Dendrite on Fractal Mathematics And New Theories

5 Replies
174 Views
Last post Yesterday at 02:38:27 PM
by superheal
question
Newton Raphson - how long wilt it run ?

Started by CFJH on Kalles Fraktaler

13 Replies
793 Views
Last post September 11, 2019, 08:38:32 AM
by claude
xx
Newton-Raphson Fractal attempt in Xaos

Started by Know That Fractal! on Fractal Image Gallery

0 Replies
398 Views
Last post December 22, 2017, 01:40:55 AM
by Know That Fractal!
xx
Newton (gannjondal)

Started by Sabine62 on Fractal Image Gallery

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