Trying to Short-Stop Iterated Functions ⇐

Trying to Short-Stop Iterated Functions May 15th, 2009
Patrick Stein

If a function is pretty fun, why not do it again?

My post yesterday about the Mandelbrot set got me thinking again about iterated functions. With the Mandelbrot set, you start with some complex number $c$ and with $z_0 = 0$ . Then, you generate $z_{i+1}$ by doing $z_{i+1} = z_i^2 + c$ .

Here’s another way to write this iteration. Let $f_c(z) = z^2 + c$ . Let $z_0 = 0$ and $z_1 = f_c(z_0)$ and $z_2 = f_c(z_1) = f_c(f_c(z_0)) = f_c^2(z_0)$ . In general, we write $f_c^n(z)$ to mean $f_c(f_c(\ldots f_c(z)))$ when there are $n$ copies of $f_c$ . It is easy to verify then that $f_c^{a}(f_c^{b}(z)) = f_c^{a+b}(x)$ .

The Jam

For that post, I generated the image linked at the right here. Each level of that image represents one iteration of $f_c^{i+1}(0) = f_c(f_c^i(0))$ with each strand made up of four different $f_c$ functions with neighboring $c$ ‘s.

One of the annoying things about that image is that I went directly from one iteration to the next. I had pondered using conventional splines or other polynomials to interpolate between iterations in an effort to smooth out the transitions. I didn’t go to the trouble for it though because any straightforward interpolation would be every bit as fake as the linear version. There is no provision in the iteration for $f_c^{\alpha}$ unless $\alpha$ is a non-negative integer.

Now the question is, can we fake one? Can we make some other function $g_c(z)$ so that $g_c^2(z) = f_c(z)$ ?

Faking easy functions

Let’s start with an easier function. In fact, let’s start with the easiest function: $f(x) = 0$ . It is obvious that $f^n(x) = f(x)$ for all positive integers $n$ . As such, if we let $g(x) = 0$ , it is trivially true that $g^2(x) = f(x)$ . But, that was too easy.

Maybe $f(x) = x$ will be harder? No. Again, $f^2(x) = f(f(x)) = f(x)$ .

Faking translations

Let’s move up to something a little trickier. Let’s say that $f(x) = x + c$ for some constant $c$ . Now, we see that $f^2(x) = f(f(x)) = f(x + c) = (x + c) + c = x + 2c$ . What are we going to try for $g(x)$ then? Let’s try the obvious: $g(x) = x + \frac{c}{2}$ . Hooray! $g^2(x) = f(x)$ . So, it makes sense then to think of $f^{1/2}(x)$ as $x + \frac{c}{2}$ . Similarly, we can think of $f^{1/n}(x)$ as $x + \frac{c}{n}$ for all positive integers $n$ . In this way, we can make values $f^q(x)$ for any positive rational number $q$ .

Faking translations with scaling

Now, we’re cooking. Let’s up the ante. Let’s try $f(x) = ax + b$ . What are we going to try for $g(x)$ then? Let’s guess we can still use roughly the same form: $g(x) = \alpha x + \beta$ . Then, $g^2(x) = \alpha^2 x + \alpha \beta + \beta$ . If we want $g^2(x) = f(x)$ , then we need $\alpha^2 = a$ and $(\alpha + 1)\beta = b$ . This means that $\alpha = \sqrt{a}$ and $\beta = \frac{b}{1 + \sqrt{a}}$ . In particular, notice that if $a$ and $b$ are both real numbers with $a$ less than zero, then $\alpha$ is pure imaginary and $\beta$ is complex.

TTFN

I have much more to say about iterated functions, but I will save some for the next iteration. Next time, I will start with that last case and calculate $f^q(x)$ for rational $q$ .

nklein software

software development and consulting