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 Paul Bird Continuous Iteration Method discovered in 2005.

The Paul Bird 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}\left({1-f'(x_{0})^{2n} \over 1-f'(x_{0})^{2}}\right)+3{f''(x_{0})^{2}f'(x_{0})^{n-2} \over 1-f'(x_{0})}\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)+5f'''(x_{0})f''(x_{0})^{2}(...)+f''(x_{0})^{3}(...)\,$

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. Although it is always theoretically possible to construct all the coefficients algorithmically, it is not yet known if there is a simple way of constructing the coefficients.

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.