Function iteration

Function Iteration can easily be defined for integer values of n as the nth term in the series:

$f(x),f(f(x)),f(f(f(x))),f(f(f(f(x)))),...,f^{n}(x)\,$

But what about fractional or negative values of n? We can extend iteration to these values by using the Continuous Iteration Method.

The Continuous Iteration Method

The "way in" to finding the continuous iteration of a function, f(x), is to first solve the starting equation. This is:

$f(x_{0})=x_{0}\,$

Next we want to construct a Taylor series around this value.

$f^{n}(x)=x_{0}+(x-x_{0})a_{1}+{(x-x_{0})^{2} \over 2!}a_{2}+{(x-x_{0})^{3} \over 3!}a_{3}+...\,$

The difficult part of the formula comes in finding the coefficients for this series. The first four are:

$a_{1}=f'(x_{0})^{n}\,$

$a_{2}=f''(x_{0})f'(x_{0})^{n-1}\left({1-f'(x_{0})^{n} \over 1-f'(x_{0})}\right)\,$

$a_{3}=f'''(x_{0})f'(x_{0})^{n-1}{1-f'(x_{0})^{2n} \over 1-f'(x_{0})^{2}}+3\left({f''(x_{0})^{2}f'(x_{0})^{n-2} \over 1-f'(x_{0})}\right)\left({1-f'(x_{0})^{2n} \over 1-f'(x_{0})^{2}}-{1-f'(x_{0})^{n} \over 1-f'(x_{0})}\right)\,$

$a_{4}=f''''(x_{0})f'(x_{0})^{n-1}\left({1-f'(x_{0})^{3n} \over 1-f'(x_{0})^{3}}\right)\,$

$+2f'''(x_{0})f''(x_{0})^{2}f'(x_{0})^{n-2}\left({f'(x_{0})^{n}-1 \over f'(x_{0})^{2}-1}\right)\left({f'(x_{0})^{n}-f'(x_{0}) \over f'(x_{0})^{3}-1}\right)\left(3f'(x_{0})^{n+1}+5f'(x_{0})^{n}+5f'(x_{0})+2\right)\,$ $+3f''(x_{0})^{3}f'(x_{0})^{n-3}\left({f'(x_{0})^{n}-1 \over f'(x_{0})-1}\right)\left({f'(x_{0})^{n}-f'(x_{0}) \over f'(x_{0})^{2}-1}\right)\left({f'(x_{0})^{n+1}+5f'(x_{0})^{n}-5f'(x_{0})^{2}-1 \over f'(x_{0})^{3}-1}\right)\,$ They are found by differentiating the equation below and substituting in the starting equation.

$f(f(..f(x)..))\,$

For example the first differential gives:

$f'(x)f'(f(x))f'(f(f(x))..f'(f^{n-1})\,$

which after substituting in the starting equation becomes:

$f'(x_{0})^{n}\,$

which is the first coefficient. Later terms are more complicated and require the use of geometric series formulae. Daniel Geisler has shown how to construct these coefficients in a simple manner using Bell polynomials.

Examples

Example 1

Let us first take a simple linear example. We start with the function

$f(x)=3x+6\,$

The starting equation gives us:

$x_{0}=-3\,$

Now to find $f(f(x))$ we set n=2 in our formula. We get:

$f^{2}(x)=-3+9(x+3)=9x+24\,$

To find the iterative root g(x) of f(x) such that g(g(x))=f(x) we set n=1/2.

$f^{1 \over 2}(x)=-3+3^{1 \over 2}(x+3)={\sqrt {3}}x+(3{\sqrt {3}}-3)\,$

Example 2

Now a quadratic example:

$f(x)=x^{2}+6x+6\,$

We want to find f(f(x)) so set n=2. The starting equation gives $x_{0}=-2or-3$. Let us choose -2 first of all. The formula gives us:

$f^{2}(x)=-2+4(x+2)+6(x+2)^{2}+4(x+2)^{3}+(x+2)^{4}\,$ $=x^{4}+12x^{3}+54x^{2}+108x+78\,$

If we chose -3 we get the same result:

$f^{2}(x)=-3+0(x+3)+0(x+3)^{2}+0(x+3)^{3}+(x+3)^{4}\,$ $=x^{4}+12x^{3}+54x^{2}+108x+78\,$

Example 3

Now a quartic example:

$f(x)=x^{4}-4x^{2}+2\,$

We want to find g(x) such that g(g(x))=f(x) so set n=1/2. The starting equation gives 2 or -1 so we will choose 2. The formula gives us:

$f^{1 \over 2}(x)=2+4(x-2)+(x-2)^{2}=x^{2}-2\,$

Infinite Series

When considered as an infinite series, the continuous iteration formula allows us to define new functions. We can ask questions such as what is the functional square root of sin(x)? That is to say, what function f(x) is there such that f(f(x))=sin(x). However, to be really useful, there needs to be a simpler way of obtaining the coefficients of the series.

Limits of Applicablility

Not all functions can successfully be used in the continuous iteration formula. One condition are that the function is able to be written as a polynomial series. It is not yet determined if the formula has any relevence to the following iterative funtion:

$f^{n}(x)={2^{2^{2^{2..^{x}}}}}\,$

Many cases where there is no solution to the 'starting equation' or the series has poles in it can be solved by changing the function by a small amount and then taking a limit.

Special Cases

For n=1 we simply get the Taylor series expansion of f(x). When n=-1 we get the inverse function series. In this special case the series simplifies considerably to:

$y={x-x_{0} \over f'(x_{0})}\,$

$f^{-1}(x)=x_{0}+y-{y^{2} \over 2!}{f''(x_{0}) \over f'(x_{0})}+{y^{3} \over 3!}\left({f'''(x_{0}) \over f'(x_{0})}-3{f''(x_{0})^{2} \over f'(x_{0})^{2}}\right)\,$

$+{y^{4} \over 4!}\left({f''''(x_{0}) \over f'(x_{0})}+10{f''(x_{0})f'''(x_{0}) \over f'(x_{0})^{2}}-15{f''(x_{0})^{3} \over f'(x_{0})^{3}}\right)+...\,$

Authors

• Paul Bird