Inverse Mandelbrot Iteration

Robert P. Munafo, 2001 Jan 12.

While inverse iteration of Julia sets is relatively easy, the corresponding operation for the Mandelbrot set is much tougher.

The Mandelbrot Set is defined in terms of an iteration of the simple second-order (quadratic) function:

f(z,c) = z²+c

Where z and c are complex numbers. Unlike the Julia set iteration, where c is a constant, in the Mandelbrot case z and c are both variables. c varies for each point being plotted, and z varies at each step in the iteration. Therefore, we are talking about a function of two variables, so there is not one "inverse" function but two, and the term "inverse" is not really appropriate. Any of the three functions could be thought of as the "inverse" of the other two. For example, consider the three functions:

a(b,c) = b^c

b(a,c) = a^(1/c)

c(a,b) = ln(a)/ln(b)

While we normally think of the second and third as "inverses" of the first, you could just as easily think of the first two as being inverses of the third.

Returning to the Mandelbrot function, the two "inverse" functions are:

z(f,c): What is the value of z, given f and c?

c(z,f): What is the value of c, given z and f?

Both are easy to derive from the definition of f(z,c) by algebra:

z(f,c) = sqrt(f-c) or -sqrt(f-c)

c(z,f) = f-z²

Notice that the z definition has two values except in the one case when f=c, because whenever you take the square root of a complex number there are two possible values, unless that number is 0.

The actual Mandelbrot iteration process can also be expressed as a function, and then there is a third argument, namely the number of iteration steps that have been performed so far:

	i(z, c, n)	= f(z, c)	for n=1
		= f(i(z, c, n-1), c)	for n>1

Substituting in the definition of f, we get:

	i(z, c, n)	= z²+c	for n=1
		= i(z, c, n-1)^2+c	for n>1

Since this is a function of three arguments, there are three corresponding functions any one of which could be thought of as an "inverse":

z(i, c, n): What values of z produce value i if iterated with c for n steps?

c(i, z, n): What value of c produces value i if iterated with z for n steps?

n(i, z, c): After how many steps does the iteration of z and c produce value i?

Since i was defined recursively in terms of itself, the definitions of these three must also include some type of iteration or recursion.

z(i, c, n)	= sqrt(i-c) or -sqrt(i-c)	for n=1

	= z(sqrt(i-c), c, n-1)
	or z(-sqrt(i-c), c, n-1)	for n>1

Notice, again, the z function has multiple values, in this case the number of values doubles with each recursive step so the total number of values is 2ⁿ.

	c(i, z, n)	= i-z²	for n=1
		= i-c(i, z, n-1)²	for n>1

This c function has the notable problem that if there is any error (such as roundoff error) that error will double in magnitude with each iteration. If the error in z was epsilon, after n iterations it is approximately epsilon×2ⁿ. However, this is probably no worse than the same problem that exists with forward iteration accuracy.

	n(i, z, c)	= 1	if i = z²+c
		= 1+n(i, z²+c, c)	otherwise

There is a problem with this function too — it only has a defined value if one of the iterations produces a result that is exactly equal to i. Thus, for most combinations of i, z and c, it has no defined value. A computer trying to evaluate the function would iterate forever.

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2008 Feb 22.

s.27