User:Fanf/maths

Incrementally calculating means and standard deviations.

There used to be some equations here that were not completely correct. Please see my corrected working on incremental calculation of weighted mean and variance on my work home page.

Mandelbrot Set

Distance estimation

${\begin{aligned}z_{0\quad }&=0\\z_{n+1}&=z_{n}^{2}+c\\\\{\frac {\partial }{\partial {c}}}z_{0\quad }&=1\\{\frac {\partial }{\partial {c}}}z_{n+1}&=2\cdot z_{n}\cdot {\frac {\partial }{\partial {c}}}z_{n}+1\\\\\delta &=\lim _{n\to \infty }2\cdot {\frac {z_{n}\cdot \ln {z_{n}}}{{\frac {\partial }{\partial {c}}}z_{n}}}\\\end{aligned}}$

Boettcher map and Douady-Hubbard potential

First some basic notation to make the formulae less cluttered.

${\begin{aligned}f_{c}(z)&=z^{2}+c\\z_{n}&=f_{c}^{n}(z)=f_{c}(\cdots f_{c}(z))\\r_{n}&=\left|z_{n}\right|=\left|f_{c}^{n}(z)\right|\\\end{aligned}}$

To generate a Julia set, c is a fixed parameter and z varies across the complex plane. For the Mandelbrot set, c varies across the plane and z starts its iteration at 0. In both cases we iterate until z escapes to infinity, in which case it is outside the set, or remains bounded, in which case it is inside. Because we are most interested in the behaviour of z as it is iterated, we usually leave the parameter c implicit.

The simplest Julia set, when $c=0$, is just the unit circle. In this case we can write down a direct formula for $z_{n}$:

${\begin{aligned}f_{0}(z)&=z^{2}\\z_{n}&=f_{0}^{n}(z)=z_{n-1}^{2}=z_{n-2}^{4}=z_{n-3}^{8}=z^{2^{n}}\end{aligned}}$

There is something called a Böttcher map which transforms the exterior of Julia set $c=0$ into the exterior of other connected Julia sets and back again. It's like a Riemann map, but it operates on the complement of the set.

$f_{c}(z)=\Phi _{c}^{-1}(f_{0}(\Phi _{c}(z)))\,$

The definition of the map is as follows. Observe that $\Phi _{0}(z)$ is the identity function.

$\Phi _{c}(z)=\lim _{n\to \infty }{\sqrt[{2^{n}}]{z_{n}}}$

Adrien Douady and John Hubbard showed that the Böttcher map $\Phi _{c}(0)$ is a conformal mapping from the exterior of the Mandelbrot set M to the exterior of the unit disk, and therefore the Mandelbrot set is connected.

The Böttcher map allows us to treat the exterior of the set as an electrostatic field. Imagine an infinitely long crinkly cylinder whose cross-section is the set. If you electrically charge the cylinder it creates a field in the surrounding space. The Böttcher map tells you how the simple circular equipotential curves and radial field lines of the Julia set $c=0$ correspond to those surrounding the Mandelbrot set and the other connected Julia sets.

This is a powerful tool for understanding the Mandelbrot set. The binary decomposition makes a lot of the field structure visible, since the boundaries between the black and white areas are formed from segments of field lines and equipotential curves. If you express the angle of a field line as a binary fraction of a whole turn, you get the sequence of black and white segments that the field line crosses in the binary decomposition. Field lines with rational angles correspond to pinch points on the Mandelbrot set.

For our purposes we are less interested in field lines and more interested in the Douady-Hubbard potential function. We use the Böttcher map to warp the space around the set into its simplest form. This allows us to use the standard formula for the electrostatic potential around an infinite wire, which is the log of the distance from the wire. The base of the logarithm is related to how highly charged the wire is; we can choose it for our convenience.

${\begin{aligned}\phi _{c}(z)&=\;\log \left|\Phi _{c}(z)\right|\\&=\lim _{n\to \infty }\log \left|{z_{n}}^{1/2^{n}}\right|\\&=\lim _{n\to \infty }\log {r_{n}}^{1/2^{n}}\\&=\lim _{n\to \infty }{\frac {1}{2^{n}}}\log r_{n}\\\end{aligned}}$

Since we don't have time to count to infinity, in practice we define a bail-out radius R and stop iterating points that get further than that from the origin. The iteration count n is used for the flat blocky level-set colouring scheme.

$r_{n-1}\leq R<r_{n}$

The way to get a smooth colouring is to ask what fractional iteration value $\nu$ would make the point land exactly on the bail-out radius.

$n-1\leq \nu <n$

We can use the potential function to formalize this idea. If R is large, varying it will not make much difference to the potential we calculate for a point. So to derive $\nu$ we assume that we get the same result from the two expressions for the potential in the first line below. (I think this is what causes the small errors and discontinuities discussed by Linas.)

${\begin{aligned}{\frac {\log R}{2^{\nu }}}&\simeq {\frac {\log r_{n}}{2^{n}}}\\2^{n-\nu }&={\frac {\log r_{n}}{\log R}}\\\nu &=n-\log _{2}\left({\frac {\log r_{n}}{\log R}}\right)\\&=n-\log _{2}(\log r_{n})+\log _{2}(\log R)\end{aligned}}$

The final term in that equation is a constant, since R is a fixed parameter of our implementation. We might as well throw it away since it does not add any useful information.

$n^{\prime }=n-\log _{2}(\log r_{n})\,$

And thus we get the equation to use for smoothly colouring of the exterior of the Mandelbrot set.

Iteration Intuition

After writing the above, I noticed that the final equation is in fact just the negated log of the Douady-Hubbard potential, assuming n is practically infinite. (In the following I will use the binary logarithm throughout, $\lg x=\log _{2}x$.)

${\begin{aligned}-\lg \phi _{c}(z)&\simeq -\lg {\frac {\lg r_{n}}{2^{n}}}\\&=\lg 2^{n}-\lg \lg r_{n}\\&=n-\lg ^{2}r_{n}\end{aligned}}$

I didn't really understand this so I sought a more intuitive explanation.

Observe that when z is large, $f_{c}(z)$ is very close to $f_{0}(z)$. So in the following we can treat the crinkly component c as insignificant.

${\begin{aligned}z_{n}&=f^{n}(z)\simeq z^{2^{n}}\\\lg ^{2}z_{n}&\simeq \lg \lg z^{2^{n}}\\&=\lg 2^{n}\lg z\\&=\lg 2^{n}+\lg \lg z\\&=n+\lg ^{2}z\\\end{aligned}}$

So the double log gives us a sort of measure of distance in terms of the number of iterations needed to get from $z$ to $z_{n}$.

${\begin{aligned}n&=\log _{2}2^{n}\\&=\log _{2}\log _{z}z^{2^{n}}\\&=\lg {\frac {\lg z^{2^{n}}}{\lg z}}\\&=\lg ^{2}z^{2^{n}}-\lg ^{2}z\\&\simeq \lg ^{2}z_{n}-\lg ^{2}z\\\end{aligned}}$

Recall that

${\begin{aligned}z&=re^{\theta i}\\z^{p}&=r^{p}e^{p\theta i}\\\end{aligned}}$

Hence the equations in $z$ also apply to $r=|z|$,

${\begin{aligned}-\lg ^{2}z&\simeq n-\lg ^{2}z_{n}\\-\lg ^{2}r&\simeq n-\lg ^{2}r_{n}\\\end{aligned}}$

When $z$ is close to the set, $r$ is slightly greater than one (plus crinkles), so $\lg r$ is a small positive number, and $\lg ^{2}r$ is a large negative number. Hence the negation to turn it into the equivalent of an iteration count.

The equation above also relates back to the definition of the electrostatic potential and our simplifying approximation, that is,

$\phi _{c}(z)\simeq \lg r$

Thinking about what happens when we finish iterating,

${\begin{aligned}r_{n}&>R>r_{n-1}\\r_{n}&\simeq r_{n-1}^{2}\\R^{2}>r_{n}&>R\\\end{aligned}}$

So $\lg ^{2}r_{n}$ lies between two numbers with a difference of one,

$\lg ^{2}R^{2}=1+\lg ^{2}R\,$

When $\lg ^{2}r_{n}$ is subtracted from $n$, it contributes a fractional part and a fixed offset determined by the bail-out radius.

Finally, on a practical note I find that a better function for colouring pixels is to take the log again:

$m=\lg(n-\lg ^{2}r_{n})\,$

The extra log gives the value a more uniform gradient so it cycles through the colours evenly, and it gets much closer to the set before it flies off to infinity so less of the picture suffers from aliasing. Even better, it retains these properties as you zoom in.