Technical Discussion of Fractal Formulas

From Ultrafractal Wiki

Contents 1 Technical Discussion of Fractal Formulas 1.1 Damien's reply about Halley's root-finding Method 2 Dan's Response 3 Further info from Damien 3.1 Dave's Tip 3.2 Dan's Reply 3.3 Response from Kerry 3.4 Dan's Reply 3.5 Another Reponse from Dan 3.6 Reply from Damien 3.7 Dan's reply

Technical Discussion of Fractal Formulas

Damien's reply about Halley's root-finding Method

Dan,

"There didn't seem to be any article for a 'Halley root finding' method on wikipedia, does anyone know about it?""

Try this:

• wikipedia on Halley's Method

And this:

• Mathworld on Halley's Method

Basically, Halley's method is similar to Newton's method in that it is an iterative method for approximating the root (solution) to a formula. Newton's method is basically to evaluate the function at your current guess, then draw a tangent line to the axis and use that as the next guess. This requires that you have the first derivative available.

Halley's method uses the second derivative as well (curvature) so at each step you get a better estimate. The trade-off is that each step is more complicated. Newton's method converges quadratically, so it has standard power-2 minibrots in it. Halley's method converges cubically, so it has power-3 minibrots in it. You could construct an endless sequence of root-approximating algorithms using more and more derivatives to generate higher-order minibrots in the fractals.

Also note that the Newton and Halley formulas I wrote (and are most frequently used in other programs as well) use a simple polynomial function z^n - 1 = 0 as the function to solve. This is easy to compute the derivative for, but the methods are generalized and can be used to approximate solutions for any differentiable function.

Relaxation, by the way, is a way to "soften up" the Convergence of the method. Using a value of 0.5 makes each step only half as effective. Interesting effects can be produced by using values > 1, negative values, or even complex values. These are left as an exercise to the reader.

Damien Jones

Dan's Response

Dan wrote:

Meanwhile I have found quite a few other fractals that generate mega-plane-filling-amounts of detail ;D Something I read about there being two root finding methods, 'Newton' and 'Halley' lead me to have a play with the Halley fractal, and I found that it also generates detail with very high dimension when relaxation is set appropriately, see the UPR below for a simple example.

There didn't seem to be any article for a 'Halley root finding' method on wikipedia, does anyone know about it? would it be worth adding a little article for the halley method/fractal?

I have been debating on the mandelbrot page about the suitability/notability of particular image, which I put up to illustrate the mandelbrot fractal with power=(-1.5, 0), it is a zoom though, so it doesn't show much apart from that this kind of thing is possible:

Image to illustrate the mandelbrot fractal with power=(-1.5, 0)

I have now added a zoom out on this to show the entire lake of this negative exponent setting (this is on the mandelbrot set page at the moment, see the discussion there if you are interested):

Zoom out to show lake

have fun! :D

dan

halleyDetailTwo {
fractal:
  title="halleyDetailTwo" width=1024 height=1024 layers=1
  credits="dan wills;6/10/2008;Frederik Slijkerman;7/23/2002"
layer:
  caption="Background" opacity=100
mapping:
  center=-5/9.6875 magn=0.20983607
formula:
  maxiter=149 filename="Fractint.ufm" entry="halley" p_order=3
  p_relax_r=2.9 p_epsilon=0.00000000000000000000001 p_relax_i=0
inside:
  transfer=sqrt filename="Standard.ucl" entry="ExponentialSmoothing"
  p_diverge=yes p_converge=yes p_divergescale=1.0
outside:
  transfer=sqrt filename="Standard.ucl" entry="ExponentialSmoothing"
  p_diverge=yes p_converge=yes p_divergescale=1.0
gradient:
  smooth=yes rotation=-1158 index=-1486 color=16767395 index=158
  color=16774593 index=-625 color=16777215 index=196 color=7114688
  index=-1387 color=6294379 index=233 color=3215660 index=-1343
  color=2556185 index=-1727 color=1180168 index=-1705 color=0
  index=-1681 color=1247252 index=-1652 color=3211352
opacity:
  smooth=no index=0 opacity=255
}

Further info from Damien

Dan,

"I'm wondering, are these methods (newton, halley, the whole householder series) actually being used to find zero-crossings in the UF formulae (is that what the lake edge is, perhaps?) Or are they rather used just to get a closer approximation to the actual shape of the fractal? Or are the fractals more of a by-product of the dynamics of the methods?"

A Fractal Formula is primarily a way of taking a z value and making a new z value. This is what a transform does once; a formula just does it over and over again.

The root-finding fractal formulas are, in fact, finding the zero-crossings. Take this formula:

f(z) = z3 - 1

For real numbers, there is one z where f(z) = 0, and that is 1.0. But in complex numbers, there are three solutions: 1.0, and also 0.5 +- 0.5 * sqrt(3) * i.

The Newton formula uses each pixel value as a starting guess, and iterates successively until the difference between one guess and the next is very small. Where you start determines which of the solutions the method will "attract" to. The boundaries between these regions, though, is fractal.

What you see when you render a Newton fractal depends on how you color it. Traditional iteration-bands coloring will show you "how long" it takes to approach each solution. Other coloring methods can show you which solution was selected. But most of the coloring methods we use are going to show the results of that step-by-step transformation that makes each starting point converge on a result. So the peculiarities of the particular method (Newton, Halley, Householder, etc.) will have the most impact on the fractal shape.

The seed value which is added at each iteration will also have some effect, but won't change the underlying character of the iterative transformation.

If you want to see what that iterative Transform is doing, set up a fractal with one iteration and color it (perhaps by using a very fine grid). Set the relaxation to zero, increase the Iterations to two. Now slowly, slowly increase the relaxation towards one. You'll see that the entire Complex Plane is being stretched and pinched in strange ways. This is the transformation that is taking place at every iteration.

Stack up those transformations and you can imagine the kneading that is taking place. Kneading is one of the basic fractal characteristics.

Damien Jones

Dave's Tip

Hi Dan,

Regarding the Halley method and other such mathematical stuff, the best place to look is here

bye,

Dave

Dan's Reply

Ah thanks David and Damien, I don't know how I managed to miss that! whoops! :D

Thanks also for your plain-english explanations, that makes this a lot easier to understand.

I'm wondering, are these methods (newton, halley, the whole householder series) actually being used to find zero-crossings in the UF formulae (is that what the lake edge is, perhaps?) Or are they rather used just to get a closer approximation to the actual shape of the fractal? Or are the fractals more of a by-product of the dynamics of the methods?

I'm a little out of my depth with the math here but I'd love to have a clearer picture of what is going on. I've written a simple euler integrator before (for a spring dynamics system), as well as an 'implicit integrator', (we used this at rsp to animate springy web dynamics in the recent "Charlotte's Web" movie) So I know a tiny bit about trying to move towards solutions in a function but I don't have a lot of actual formal math behind me, so it takes a bit of translation for me to get it, so thanks for that! :D

all the best, I hope your relaxations are all well tweaked ;D

dan

Response from Kerry

Dan Wills wrote:

"I'm wondering, are these methods (newton, halley, the whole householder series) actually being used to find zero-crossings in the UF formulae (is that what the lake edge is, perhaps?) Or are they rather used just to get a closer approximation to the actual shape of the fractal? Or are the fractals more of a by-product of the dynamics of the methods?"

Damien beat me to it with a nice description of Halley's method. As he said, one can construct any number of such methods by using better and better approximations of the function at the root (function, function & slope, function & slope & curvature, etc.). Each of these opens up new opportunities for relaxation coefficients, and thus, fractal formulae.

Scads of whole-plane-detail formulas can be found by cranking up the relaxation just past the point of stability. With these formulas, the fractal is a result of the dynamics: the formulas are generally very good at finding solutions to their target equations, but in some cases, they get 'confused" and a small change in starting conditions can lead to a large change in final result.

That's what gives rise to the fractal structure--the dynamics of the root-finding algorithms.

Kerry

Dan's Reply

Certainly! :D I reckon I can understand this in a basic sort of way, but I'd need to actually visualize what is happening to the orbits as relaxation changes in order to get a proper geometric appreciation for the transformations that occur when these root finding methods are used.

This kind of sensitivity to initial conditions it is certainly one of my favorite phenomena! :D thanks for taking the time to elucidate it Kerry!

dan

Another Reponse from Dan

G'day Damien,

Damien wrote:

"Dan, I'm wondering, are these methods (newton, halley, the whole householder series) actually being used to find zero-crossings in the UF formulae (is that what the lake edge is, perhaps?) Or are they rather used just to get a closer approximation to the actual shape of the fractal? Or are the fractals more of a by-product of the dynamics of the methods?"

"A fractal formula is primarily a way of taking a z value and making a new z value. This is what a transform does once; a formula just does it over and over again."

I really appreciate your guidance and advice on this fascinating topic!! :D

I don't understand this in a formal way but I still love the realization that fractals are really just like repeated 'warps'. It really struck me at one point when I was experimenting with some 2d vector fields (those generated by one iteration of some simple fractal formulae). I was repeatedly passing pixel data through them in a feedback loop, for simple field shapes you get simple results but when the shape of the warp is right, you see fractal detail that increases the more times you loop - when the shape of the warp is such that the kneading is even more crazily twisted, you sometimes get an inordinate amount of detail per-pixel. I guess this might be a very informal way to think about what is happening to these root-finding fractals, as the relaxation value is increased.

"The root-finding fractal formulas are, in fact, finding the zero- crossings. Take this formula: f(z) = z3 - 1"

"For real numbers, there is one z where f(z) = 0, and that's 1. But in complex numbers, there are three solutions: 1, and also 0.5 +- 0.5 * sqrt(3) * i."

"The Newton formula uses each pixel value as a starting guess, and iterates successively until the difference between one guess and the next is very small. Where you start determines which of the solutions the method will "attract" to. The boundaries between these regions, though, is fractal."

I find this fairly straightforward to visualize for the standard newton fractal, I've always thought of it a bit like a magnetic pendulum with three target magnets.. I know that there's a different fractal that does model that phenomena explicitly, but the analogy still helps me understand the basic 3-way newton.

I'm sure there would be a similarly practical way to imagine the dynamics of nova and halley and so on, but I find those a lot harder to get hold of mentally.. I'm guessing that this is mainly because I haven't tried to study the formulae or the warp-dynamics much myself, and that they might also correspond to completely non physics-like dynamics, making them hard to imagine directly. I hope I do get a chance to carefully tease the dynamics apart one day though ;D

"What you see when you render a Newton fractal depends on how you color it. Traditional iteration-bands coloring will show you "how long" it takes to approach each solution. Other coloring methods can show you

which solution was selected. But most of the coloring methods we use are going to show the results of that step-by-step transformation that makes each starting point converge on a result."

Cool, so the answer to my question "are these formulae actually finding the roots?", is yes, but what is used to produce the pixel values (or at least to /initialize the coloring method/) is not the roots that were found, but the data generated by the steps on the journey to finding them. Is it even perhaps (more usually?) the final point on the plane that was reached at the iteration limit. Would that be a fair way to put it do you think?

"So the peculiarities of the particular method (Newton, Halley, Householder, etc.) will have the most impact on the fractal shape. The seed value which is added at each iteration will also have some effect, but won't change the underlying character of the iterative transformation."

I have certainly noticed this, I've looked around in the phoenixDoubleNove a /lot/ and it seems to have a similar character all over the place, and across lots of different values for its parameters. Makes sense since it's the same simple transformation, repeatedly applied.

Another example of massive detail generation, the negative-fractional-exponent mandelbrot lake (-1.5, 0.0) has a more barnsley-fractal-esque crystalline quality to it, there are lots and lots of infinitely fine discontinuities layered up everywhere - it's a lot more detailed then a normal barnsley of course and it also varies quite a lot as you move across the plane.

I'd love to know if there's any analogy between the geometrical transformations applied by the root-finding methods, and a neg-mandelbrot fractal set up this way.

There is a bit of a discussion about this on wikipedia at the moment (because I posted a detail of a negmandel on the mandel set page, I have now re-posted with a rendering of the entire lake): here

I wonder if anyone can help to answer the question that 'gandalf61' asked here, of whether the discontinuities in a neg-mandel like this are coming from sensitive selection of one root over another by the formula? A fractional power makes the mandelbrot function multivalued (ie it has multiple solutions), and I'd like to know how the formula decides which one to go with. Is it an arbitrary choice, so making the image a kind of curious rendering artifact, or whether there is something more intrinsic about the way the root is chosen that leads to the mega-detail.\

It would also be heaps interesting to have a better idea of how this relates to the mega-detail in a relaxed phoenixDoubleNova, is that also a multivalued result, or perhaps it's just approaching one?

"If you want to see what that iterative transform is doing, set up a fractal with one iteration and color it (perhaps by using a very fine grid). Set the relaxation to zero, increase the iterations to two. Now slowly, slowly increase the relaxation towards one. You'll see that the entire complex plane is being stretched and pinched in strange ways. This is the transformation that is taking place at every iteration. Stack up those transformations and you can imagine the kneading that is taking place. Kneading is one of the basic fractal characteristics. mmm, the complex plane is rather lucky to be getting all these lovely kneady massages, wouldn't you say? :D"

hehe, but seriously.. it's awesome getting a better appreciation for the exact kneadings that lead to these awesome dimension-climbing phenomena.

I sometimes like to try to think of this stuff also in relation to Wolfram's 4 classes of computation too, what we often see with fractals is classes 1 (fixed points) and 2 (loops and recursion), I like to think that this massively detailed stuff is pushing towards class 3 (randomness generating).

I am not very clear how class 4 can fit into this picture though.. it's usually found between class 2 and 3 somewhere. I'd love to hear your thoughts about that.

Thanks again Damien, you fricking rock!

dan

Reply from Damien

Dan,

"I don't understand this in a formal way but I still love the realization that fractals are really just like repeated 'warps'."

That's basically it, yes. It's the same "warp" applied over and over again. As you indicate, you can use any "warp" repeatedly and get some fractal results in many cases; here's an old one where I used fBm as the warp and applied it something like 1,000 times: [1] here]

"Cool, so the answer to my question "are these formulae actually finding the roots?", is yes, but what is used to produce the pixel values (or at least to /initialize the coloring method/) is not the roots that were found, but the data generated by the steps on the journey to finding them. Is it even perhaps (more usually?) the final point on the plane that was reached at the iteration limit. Would that be a fair way to put it do you think?"

The coloring algorithms most commonly in use are affected by every iteration value, not just the last. So yes, the last iteration (the "solution" reached) does affect the coloring, but not more or less than the other iterations. It's the entire set of iterations, as a whole. And not just as an unordered set of points, but as a sequence.

"I'd love to know if there's any analogy between the geometrical transformations applied by the root-finding methods, and a neg-mandelbrot fractal set up this way."

It's the same deal. The classical Mandelbrot formula has three visual components to its step-to-step transformation. First, cut along a ray from the origin to infinity along the negative real axis; grab each edge and pivot them around the origin to the positive real axis so that they overlap. Second, glue down a circle of radius 1 centered at the origin, and pinch what's inside the circle towards the origin and stretch what's outside the circle towards infinity. Third, unglue the circle and shift the entire plane by a particular amount (so the next iteration will cut/stretch/pinch around a new origin).

That's the entire process, and it's done for every iteration. The first two steps are what the 2 as an exponent are doing; the third step is the addition of the seed value. If you use a different exponent, you change the exact details of the twisting and pinching/stretching, but the mechanics are the same (mostly). And just like with Newton, this basic transformative step is applied over and over, producing the kneading that makes fractals work.

"I wonder if anyone can help to answer the question that 'gandalf61' asked here, of whether the discontinuities in a neg-mandel like this are coming from sensitive selection of one root over another by the formula?"

It's a valid question, because as gandalf61 pointed out, the log function for complex values is multivalued. If you think about complex numbers in polar coordinates rather than rectangular coordinates, it's easier to see. Most implementations I've seen (including the one in UF) take the "simplest" log. The actual full multi-valued log function is like a crazy piece of spiral pasta centered at the origin, sticking straight out of the plane; we cut a small section of that pasta so that when we look straight down at the plane, none of the pasta overlaps itself. We choose the piece that's actually touching the origin and has equal amounts above and below it. Choosing any other part of the pasta is "valid" and will produce different fractals; Jim Muth over on the FractInt list has done some exploring with formulas that adjust the "cut" and found some interesting results.

In a sense UF's choice is "arbitrary" but it's arbitrary in the same way that we restrict the range of the arcsine function to the "simple" -pi/2 <= asin(n) <= pi/2 even though there are other "valid" results. And since this is the "most natural" place to make the cut, most implementations make it in the same place. Arguing that it's an artifact is incorrect because similar details exist regardless of where the actual cut is.

"It would also be heaps interesting to have a better idea of how this relates to the mega-detail in a relaxed phoenixDoubleNova, is that also a multivalued result, or perhaps it's just approaching one?"

It's not multi-valued. At each step, there's exactly one answer that is valid for the parameters given. I think the chaos you're seeing is more like the classic bifurcation fractal. With the bifurcation fractal you use a simple iterative formula that normally converges on a single value; as you increase a multiplier you change the result slowly until you reach a critical point, where suddenly the system bifurcates and settles into an oscillating pattern. Increase it further and it doubles again, and again, and the distances between critical points shortens geometrically until BAM! Chaos reigns. Continue increasing beyond the chaos threshold and pockets of stability appear in a sea of chaos, but at no point does sanity (stability) fully return.

With the PDN formula you're doing the same thing, but with a more complicated formula and with complex values rather than real values. As you increase the relaxation, what should have converged on a single result (the "solution" to the formula) instead bubbles over into chaos, with pockets of order here and there.

"mmm, the complex plane is rather lucky to be getting all these lovely kneady massages, wouldn't you say? :D"

I'd knead a hypervolume using quaternions if I could get my fingers on it, but it always slips through that fourth dimension and gets away...

"What do you all think, as users of UltraFractal, is the concept of the 'lake' significant enough to warrant an article about it?"

"It could be described formally in terms of convergence and divergence, attractors and so on, but I personally like the informal notion of the 'lake'. The points that don't escape the attractor."

The term "lake" has been used to refer to the attracting portion of a fractal for a long time. Arthur C. Clarke's book "The Ghost from the Grand Banks" actually has the main characters living next to a real lake that coincidentally looked like the Mandelbrot set; what makes the reference noteworthy is that a real lake looked like the M-set "lake", a pun that only a few people would actually get. (And Clarke had a long fascination with fractals.) I'm fairly certain that this use predates FractInt but I don't have documentation to prove it, so I'm willing to be wrong.  :-)

Damien Jones

Dan's reply

wow, what an awesome response damien! :D thanks so much!

I would easily recommend your description of mandelbrot dynamics to any classroom in which the mandelbrot fractal is mentioned! there are very easy ways to describe these warp dynamics, and you've put it very understandably in your response, for sure  :) .

You have also put the idea of the arbitrary choice of roots in a very understandable way, thanks very much for that! :D I hope to traverse this concept a lot in the near future! :D.

I personally think that this hint may be a key to unlocking a vast plethora of (wolfram-) class three and four processes that generate some visually - extremely aesthetically pleasing structures.

I had a look at the spiral pasta on the "complex logarithm" wikipedia page, and it is quite clear to me why one would need to make such "arbitrary" decisions when performing a discretization of a computation such as this. I wonder how far we could go with understandings so strictly patrolled by the wikipedia meme-police ;D

I find it fascinating (upon fascination) that this should be a point of contention on wikipedia.. but then, it does seem that wikipedia will be one of the final arenas for fights between bizarre memes in our strangely resourced and certainly computation-influenced (though who knows how deeply it goes) planet. :D

I love this area of thought personally, how directly Turing and Von Neumann have influenced the lives of pretty much every single human alive today.. it's very deeply gnarley, to be damned sure! :D I feel that fractals are one way of finding peace with the timeless universe of computation, in which we find ourselves oddly embedded - I'm certainly trying to find some kind of synthesis between the code and my life if I can! ;D.

I personally would like to take my view a little bit further with the help of "Process Physics": plus NKS - Stephen Wolfram's "new kinda science", which when combined, places universal computation at a very central place in terms of understanding the underlying dynamics of our existence.. but I'm getting ahead of myself ;D

I really want to read that Arthur-C-Clarke book! it sounds fantastic :D

thanks *fractally* (on so many levels) for your thoughts! dan