Perturbation theory

  • 211 Replies
  • 6249 Views

0 Members and 1 Guest are viewing this topic.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« on: October 31, 2017, 05:29:39 PM »
(Moved this out of the movie-gallery.)
There are 2 main questions I guess.

1. classify the potential problems with perturbation iterations and provide proven (in the mathematical sense) remedies - Pauldelbrot's heuristic goes pretty far to detect glitches, but is still missing some proofs (for example the magnitude threshold value of 10^{-3} is somewhat unjustified). ( http://www.fractalforums.com/announcements-and-news/pertubation-theory-glitches-improvement/ is the original thread )

2. the same for series approximation, in particular there is a desire for a cheap per-image test to know if it is safe to skip this many iterations with these series coefficients, maybe controlled by an input maximum error tolerance or so, while not being too conservative (it is always safe to skip no iterations, but we want to maximize skipping for efficiency).
Thanks for the link. It would be nice if all this theory developed over the last 5 years was summarized in a self-contained document. Martin's 1.5-pager is crystal clear, but it's just a starter and of course needs a chapter on accuracy control and criteria for selecting reference points etc which is now hidden in the fractal structure of the old forum :)

Not sure if any rigorous proofs on accuracy can be expected, but there are plenty of numerical methods experts or grad students looking for low hanging fruit who might have ideas if some concise writeup of the current state of the art existed, or better, was published.

Offline claude

  • *
  • 3c
  • ***
  • Posts: 895
    • mathr.co.uk
« Reply #1 on: November 01, 2017, 02:44:34 AM »
I have such a writeup in preparation.  Not published yet.  In the meantime, here are some references:

* K. I. Martin, ?SuperFractalThing Maths?, http://superfractalthing.co.nf/sft_maths.pdf the originating paper
* Pauldelbrot, ?Perturbation Theory Glitches Improvement?, http://www.fractalforums.com/index.php?topic=18908.msg73027#msg73027 glitch detection heuristic |z+d| < 10^{-3} |z|
* knighty, ?Re: SuperFractalThing?, http://www.fractalforums.com/index.php?topic=23279.msg91505#msg91505 presenting interval arithmetic for 3 term series error analysis and how to apply it, as well as a glitch detection heuristic
* knighty, ?Re: SuperFractalThing?, http://www.fractalforums.com/index.php?topic=23279.msg95532#msg95532 the above formulas extended to arbitrary numbers of terms in the series (both series and truncation error, with a couple of variations)
* knighty, ?Re: SuperFractalThing?, http://www.fractalforums.com/index.php?topic=23279.msg96343#msg96343 a per-image "is series approximation valid" test for the interval arithmetic truncation error
* Botond Kósa, ?Re: Mandel Machine?, http://www.fractalforums.com/index.php?topic=18482.msg74200#msg74200 an alternative series stopping heuristic based on magnitudes of terms
* laser blaster  ?Re: Perturbation formula for burning ship (hopefully correct :P)?, http://www.fractalforums.com/index.php?topic=19165.msg74090#msg74090 case analysis for |z+d|-|z| to allow perturbation to work for burning ship and other abs fractals
« Last Edit: November 01, 2017, 02:55:33 AM by claude »

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #2 on: November 01, 2017, 06:33:39 PM »
I have such a writeup in preparation.  Not published yet.  In the meantime, here are some references:
Thanks!

Yesterday I looked for a "correctness proof" of the basic floating point M-set algorithm as taught in kindergarten but found only this:
https://www.mrob.com/pub/muency/roundofferror.html, which seems to say even that is not understood mathematically.

I found some links on the "shadowing lemma/theorem" talked about in chaos theory, which seems to be the same as what's called "backward stability" in standard numerical analysis. Backward stability means here that though your floating point orbit diverges a lot from the exact orbit for given c (c as in \( z \leftarrow z^2 + c \)), there exists another c' which differs from the exact c by something of the order of the round-off error whose exact orbit stays very close to the numerical orbit. It seems however only to be a conjecture for the M-set, but well supported by numerical experiments?


Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #3 on: November 02, 2017, 06:47:37 AM »
I tried computing a z-orbit at one c value (bailout ~200 at R=10000) with hardware double precision and with extended precision.
The blue line in plot below indicates by how much the hardware z deviates from the "exact" value. Bailout is at 212 using double precision, at 220 using extended precision. (Increasing accuracy doesn't change it further.)

I then used Newtons method to find a c that generates the double precision orbit using extended precision. With that new c the error is as plotted in red. The change in c is below double precision accuracy as it should be. So the shadow lemma seems to apply to plain iterations and we have backward stability, at least for this example for which I used

c = -1.372966131127572971770926665264106372254+1i*0.09019294174637803053912656841861050357861.

I tried other random values with same result. Of course there could be pathological values of c, but I have no idea how to find them if they exist.

Next thing to check is stability of the perturbation iteration. Formula (1) from Martins paper is exact, so if it fails using double precision at some points, stability must fail. I guess I need a c0 for a reference orbit and a "bad" c1 inside a glitch. If anyone can provide me with values to try I can check.



Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #4 on: November 02, 2017, 07:08:03 AM »
* Pauldelbrot, ?Perturbation Theory Glitches Improvement?, http://www.fractalforums.com/index.php?topic=18908.msg73027#msg73027 glitch detection heuristic |z+d| < 10^{-3} |z|
Isn't there a \( +\epsilon_0 \) missing in the second and 3d formulas in that post?

Offline claude

  • *
  • 3c
  • ***
  • Posts: 895
    • mathr.co.uk
« Reply #5 on: November 02, 2017, 02:44:18 PM »
Isn't there a \( +\epsilon_0 \) missing in the second and 3d formulas in that post?

Hm, I think you're right.  Well spotted, perturbing d_0 should give d_0+e_0 indeed!

Offline Adam Majewski

  • *
  • Fractal Friar
  • *
  • Posts: 125
« Reply #6 on: November 02, 2017, 04:35:30 PM »
I tried computing a z-orbit at one c value (bailout ~200 at R=10000) with hardware double precision and with extended precision.
The blue line in plot below indicates by how much the hardware z deviates from the "exact" value. Bailout is at 212 using double precision, at 220 using extended precision. (Increasing accuracy doesn't change it further.)

I then used Newtons method to find a c that generates the double precision orbit using extended precision. With that new c the error is as plotted in red. The change in c is below double precision accuracy as it should be. So the shadow lemma seems to apply to plain iterations and we have backward stability, at least for this example for which I used

c = -1.372966131127572971770926665264106372254+1i*0.09019294174637803053912656841861050357861.

I tried other random values with same result. Of course there could be pathological values of c, but I have no idea how to find them if they exist.

Next thing to check is stability of the perturbation iteration. Formula (1) from Martins paper is exact, so if it fails using double precision at some points, stability must fail. I guess I need a c0 for a reference orbit and a "bad" c1 inside a glitch. If anyone can provide me with values to try I can check.


what library do you use?
Do you know arb : http://arblib.org/

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #7 on: November 03, 2017, 06:24:29 AM »
Here's something I don't understand. In Martins paper, eq (1)
\[ \Delta_{n+1} = 2X_n\Delta_n + \Delta^2_n + \Delta_0 \]
he mentions all quantities are small. \( \Delta_0 \) is of the size of your window so very small, but I'm not so sure about the other two terms. Surely at some point they must get bigger than \( \Delta_0/\epsilon \) with \( \epsilon \) the machine precision, at which point the addition of \( \Delta_0 \) drops out. When that happens the location no longer matters, which could explain glitch patches of equal color in the rendering.

If \( X_n \) is the orbit of a mini it never gets larger than 2. If the point we're calculating with eq. (1) lies outside the set, to ever bail out \( \Delta_n \) must become of the order of the escape radius, so this scenario always happens long before it reaches the escape radius, namely when it reaches \( |\Delta_0/\epsilon| \).

What I don't understand is how this can work at all, with only a small amount of "glitches"? I've implemented it and I see it works except for small glitch areas. Perhaps in the "good" areas the dynamics is such that the dropping out of the location due to loss of precision no longer matters as the orbit is already "on target" or something like that?

As the glitch can be removed by choosing a different reference orbit, somehow the right reference orbit manages to delay the point of loss of precision in the addition in eq. (1) to a point where the location is no longer important?

Any insights anyone?

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #8 on: November 03, 2017, 06:25:24 AM »

Offline claude

  • *
  • 3c
  • ***
  • Posts: 895
    • mathr.co.uk
« Reply #9 on: November 03, 2017, 07:38:25 AM »
If \( X_n \) is the orbit of a mini it never gets larger than 2. If the point we're calculating with eq. (1) lies outside the set, to ever bail out \( \Delta_n \) must become of the order of the escape radius, so this scenario always happens long before it reaches the escape radius, namely when it reaches \( |\Delta_0/\epsilon| \).

if X is the orbit of a mini it periodically becomes 0, so D^2 can be much smaller than D, so adding D0 might not lose precision at that iteration.

Offline quaz0r

  • *
  • Strange Attractor
  • ******
  • Posts: 96
« Reply #10 on: November 03, 2017, 07:56:55 AM »
when \( \Delta_0 \) stops contributing, it simply stops contributing (without issue).  on the other hand, if the reference orbit \( X_n \) reaches a value that causes the addition of the other terms to get lost with the floating-point precision being used, then all points affected in this way using this reference will end up with the same value at that iteration, resulting as you say in the glitched regions of points with the same bad value.  also i think "noisy" glitch regions are also possible where substantial but not complete loss of significance occurs.

this is actually the primary issue which remains to be perfectly solved and proven:  when exactly does this loss of significance become too great, and what is the most accurate and efficient way to detect this?  (or was knighty's superman-math for this totally solid, and just didnt get any attention for adding too much unwanted complexity?)

as far as how any of this even works at all, well, the more chaotic a given location, the more this all breaks down indeed, with more and more reference points and/or floating-point precision required.
« Last Edit: November 03, 2017, 08:40:40 AM by quaz0r »

Offline hapf

  • *
  • Fractal Friend
  • **
  • Posts: 17
« Reply #11 on: November 03, 2017, 08:54:55 AM »
as far as how any of this even works at all, well, the more chaotic a given location, the more this all breaks down indeed, with more and more reference points and/or floating-point precision required.
Correct. In the denser areas close to the border even at shallow depths numerically things are off very quickly and tons of references are needed for numerical accuracy while visually it can still look "correct" with one reference. This is such a region
-1.02377361138741699544372E+00
2.48937314496115289076363E-01
1.176759003E-14

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #12 on: November 03, 2017, 06:09:35 PM »
when \( \Delta_0 \) stops contributing, it simply stops contributing (without issue). 

I don't think agree with the "without issue" part. If you think of the orbit of  \( \Delta_n \) as being driven by  \( \Delta_0 \), then as soon as  \( \Delta_0 \) drops out (when  \( \Delta_n \)  gets too big), the orbit is "on its own". If it was on its way out anyways that is fine (no glitch) but if, in exact artithmetic, it should return to smaller values, bounce around in a complicated manner, and only then exit, this behavior is completely missed because it exits when it should not (as the return is driven by  \( \Delta_0 \), which is now too small).

Quote
on the other hand, if the reference orbit \( X_n \) reaches a value that causes the addition of the other terms to get lost with the floating-point precision being used, then all points affected in this way using this reference will end up with the same value at that iteration, resulting as you say in the glitched regions of points with the same bad value.
I don't think that ever happens as the whole point of the PT is to separate out the iterations of \( X_n \) and  \( \Delta_n \) and they are never added (this would usually just give \( X_n \)) except for bailout check, which only gets triggered when  \( \Delta_n \) gets big. 

The (smooth) glitches happen when for two different values of  \( \Delta_0 \), their \( \Delta_n \) orbits get closer than the machine precision and from then on snap together. I am suspecting that the dropping out of  \( \Delta_0 \) terms when  \( \Delta_n \) gets largish has something to do with it, but there could be other rounding error accumulations.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1536
« Reply #13 on: November 03, 2017, 08:10:42 PM »
Here's an image showing the efficacy of Pauldelbrot's glitch detection method, which is (using notation from Martin's paper)
\[ |X_n+\Delta_n|/|X_n|<\rm{tol}. \]
I indicate the pixels where a glitch is detected with this method by a gray overlay.
In normal reading order: Brute force result using high precision, then PT results with various values of tol:
0, 1e-12, 1e-9, 1e-7, 1-e6, 1e-5, 1e-4, 1e-3, 1e-2, 1e-1, 1e0.
The reference point is indicated by a black square (a period 111 mini).
KF rendered this location using 8 references.

How does one continue from here on? Do you find a new mini in the glitched area (maybe a region containing the "worst" glitch?), rerun that region, and repeat?

Offline quaz0r

  • *
  • Strange Attractor
  • ******
  • Posts: 96
« Reply #14 on: November 03, 2017, 11:51:17 PM »
i wasnt asking, i was telling.


xx
Resource for Learning Perturbation Theory

Started by Byte11 on Programming

0 Replies
197 Views
Last post September 10, 2018, 06:49:35 PM
by Byte11
xx
String Theory

Started by FractalDave on Fractal Image Gallery

5 Replies
137 Views
Last post September 19, 2018, 05:39:39 PM
by gerrit
xx
perturbation for Z := exp(Z) + C

Started by claude on Fractal Mathematics And New Theories

5 Replies
691 Views
Last post February 06, 2018, 09:35:59 AM
by claude
xx
perturbation algebra

Started by claude on Fractal Mathematics And New Theories

1 Replies
220 Views
Last post March 13, 2018, 12:07:42 AM
by claude
xx
algebraic number theory and the Mandelbrot set

Started by claude on Fractal Mathematics And New Theories

0 Replies
90 Views
Last post August 05, 2018, 06:32:41 PM
by claude