Another Iteration on Iterated Functions

Another Iteration on Iterated Functions May 19th, 2009
Patrick Stein

Earlier, I started exploring iterated functions trying to make some way-points between Mandelbrot set iterations. In that post, I left off with the following: if $g(x) = x\sqrt{a} + \frac{b}{1 + \sqrt{a}}$ , then $g^2(x) = ax + b$ . Today, I am going to tackle the more general case of finding $g(x)$ so that $g^n(x) = ax + b$ .

First, a caveat

You can see already in the above that we had some arbitrary choices. We could have chosen either the positive or negative square root of $a$ . This is essentially a death knell for my dream of coming up with an equation to do an arbitrary number of partial iterations in a completely natural way.

Okay, so it’s not the end-all-and-be-all. It’s not unique. At least, it is more natural than pretending like things proceed directly from one iteration to the next in a straight line or along some fitted curve.

In the end, what I really want is some way to define $f^{\frac{1}{n}}(x)$ that isn’t too ugly compared to $f(x)$ itself. I want $f^{\frac{1}{n}}(x)$ to be continuous in the sense that if you pick some positive $\delta$ , then I can come up with some $n$ so that $| f^{\frac{a+1}{n}}(x) - f^{\frac{a}{n}}(x) | < \delta$ for all $a \in [ 0, 1, 2, \ldots, n-1 ]$ for every $x$ in some useful region.

I believe there will be a large class of functions for which this is possible. With $f(x) = x + b$ , defining $f^{\frac{1}{n}}(x) = x + \frac{b}{n}$ is continuous in this sense.

Alright, back to work

We want to find $g(x)$ so that $g^n(x) = f(x) = ax + b$ . Again, we’re going to hope that it is of the form: $\alpha{x} + \beta$ . (In light of the fact that things aren’t unique, maybe I should be saying we’re going to hope that something of this form works.) So, let’s assume we have such a $g(x) = \alpha{x} + \beta$ .

Then, $g^n(x) = \alpha\left( g^{n-1}(x) \right) + \beta = \alpha\left( \alpha\left( g^{n-2}(x) \right) + \beta\right) + \beta$ , and so on. We can show by induction on $n$ that the general case is $g^n(x) = \alpha^n x + \beta \sum_{k=0}^{n-1} \alpha^k$ . To get this to come out to $ax + b$ we then need $\alpha = \sqrt[n]{a}$ and $\beta = \frac{b}{\sum_{k=0}^{n-1} \sqrt[n]{a^k}}$ . With a little playing with the summation, we can make this $\beta = \frac{b\left(1 - \sqrt[n]{a}\right)}{1 - a}$ .

What about non-linear iterations?

The iteration in the Mandelbrot set uses $f(z) = z^2 + c$ . Can we find a candidate for $f^{\frac{1}{n}}(z)$ ?

Let’s start with just $f(z) = z^2$ for a moment without the $c$ involved. It’s going to be trickier to get something that comes out squared. With constant functions, you can feed the result back in as often as you like and still be constant. With linear functions, you can feed them back upon themselves as often as you like and still be linear. With something squared, you end up with something to the fourth power when you feed it back upon itself. But, maybe we can do with the exponents what we did with the constants in the previous section.

If we let $g(z) = z^\alpha$ , then $g^n(z) = \left(\left(z^\alpha\right)^\alpha\ldots\right)^\alpha = z^{\alpha^n}$ . So, if we let $\alpha = \sqrt[n]{2}$ , then we have $g^n(z) = f(z) = z^2$ . I believe this is continuous in the way that I want it to be. I will have to check that at some point though.

What happens now though if we add back in a constant? Let’s try $g(z) = z^\alpha + \beta$ . Here is $g^3(z)$ : $\left( \left( z^\alpha + \beta \right)^\alpha + \beta \right)\alpha + \beta$ . That is outright ugly. I’m not even sure where to start tackling that. So, I think I’ll call it a day here at the keyboard and start hitting the whiteboard.

nklein software

software development and consulting