Fractal Related Discussion > Fractal Mathematics And New Theories

Newton-Raphson zooming

(1/12) > >>

gerrit:
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?)
--- End quote ---

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.

claude:
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.

gerrit:

--- Quote from: claude 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)

--- End quote ---
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

--- End quote ---
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

--- End quote ---
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.

--- End quote ---
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: ---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

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

--- End code ---

gerrit:

--- Code: ---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

--- End code ---
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.

claude:

--- Quote ---Hard to believe I get the right location with the wrong period though.
--- End quote ---
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.