Iterated function

Iterated transformations of the object on the left
On top is a clockwise rotation by 90°. It has order 4, because that is the smallest positive exponent that produces the identity. Below is a shear mapping with infinite order.
Below that are their compositions, which both have order 3.

In mathematics, an iterated function is a function that is obtained by composing another function with itself two or several times. The process of repeatedly applying the same function is called iteration. In this process, starting from some initial object, the result of applying a given function is fed again into the function as input, and this process is repeated.

For example, on the image on the right:

Template:Nobr

Iterated functions are studied in computer science, fractals, dynamical systems, mathematics and renormalization group physics.

Definition

The formal definition of an iterated function on a set X follows.

Let Template:Mvar be a set and Template:Math be a function.

Defining Template:Math as the n-th iterate of Template:Mvar, where n is a non-negative integer, by: $$f^0\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{\mathrm{id}}_X$$ and $$f^{n+1}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}f\circ f^n,$$

where Template:Math is the identity function on Template:Mvar and Template:Math denotes function composition. This notation has been traced to and John Frederick William Herschel in 1813. Herschel credited Hans Heinrich Bürmann for it, but without giving a specific reference to the work of Bürmann, which remains undiscovered.

Because the notation Template:Math may refer to both iteration (composition) of the function Template:Mvar or exponentiation of the function Template:Mvar (the latter is commonly used in trigonometry), some mathematiciansTemplate:Citation needed choose to use Template:Math to denote the compositional meaning, writing Template:Math for the Template:Mvar-th iterate of the function Template:Math, as in, for example, Template:Math meaning Template:Math. For the same purpose, Template:Math was used by Benjamin Peirce whereas Alfred Pringsheim and Jules Molk suggested Template:Math instead.

Abelian property and iteration sequences

In general, the following identity holds for all non-negative integers Template:Mvar and Template:Mvar,

$f^m\circ f^n=f^n\circ f^m=f^{m+n}.$

This is structurally identical to the property of exponentiation that Template:Math.

In general, for arbitrary general (negative, non-integer, etc.) indices Template:Mvar and Template:Mvar, this relation is called the translation functional equation, cf. Schröder's equation and Abel equation. On a logarithmic scale, this reduces to the nesting property of Chebyshev polynomials, Template:Math, since Template:Math.

The relation Template:Math also holds, analogous to the property of exponentiation that Template:Math.

The sequence of functions Template:Math is called a Picard sequence, named after Charles Émile Picard.

For a given Template:Mvar in Template:Mvar, the sequence of values Template:Math is called the orbit of Template:Mvar.

If Template:Math for some integer Template:Math, the orbit is called a periodic orbit. The smallest such value of Template:Mvar for a given Template:Mvar is called the period of the orbit. The point Template:Mvar itself is called a periodic point. The cycle detection problem in computer science is the algorithmic problem of finding the first periodic point in an orbit, and the period of the orbit.

Fixed points

If Template:Math for some Template:Mvar in Template:Mvar (that is, the period of the orbit of Template:Mvar is Template:Math), then Template:Mvar is called a fixed point of the iterated sequence. The set of fixed points is often denoted as Template:Math. There exist a number of fixed-point theorems that guarantee the existence of fixed points in various situations, including the Banach fixed point theorem and the Brouwer fixed point theorem.

There are several techniques for convergence acceleration of the sequences produced by fixed point iteration. For example, the Aitken method applied to an iterated fixed point is known as Steffensen's method, and produces quadratic convergence.

Limiting behaviour

Upon iteration, one may find that there are sets that shrink and converge towards a single point. In such a case, the point that is converged to is known as an attractive fixed point. Conversely, iteration may give the appearance of points diverging away from a single point; this would be the case for an unstable fixed point.

When the points of the orbit converge to one or more limits, the set of accumulation points of the orbit is known as the limit set or the ω-limit set.

The ideas of attraction and repulsion generalize similarly; one may categorize iterates into stable sets and unstable sets, according to the behavior of small neighborhoods under iteration. Also see infinite compositions of analytic functions.

Other limiting behaviors are possible; for example, wandering points are points that move away, and never come back even close to where they started.

Invariant measure

If one considers the evolution of a density distribution, rather than that of individual point dynamics, then the limiting behavior is given by the invariant measure. It can be visualized as the behavior of a point-cloud or dust-cloud under repeated iteration. The invariant measure is an eigenstate of the Ruelle-Frobenius-Perron operator or transfer operator, corresponding to an eigenvalue of 1. Smaller eigenvalues correspond to unstable, decaying states.

In general, because repeated iteration corresponds to a shift, the transfer operator, and its adjoint, the Koopman operator can both be interpreted as shift operators action on a shift space. The theory of subshifts of finite type provides general insight into many iterated functions, especially those leading to chaos.

Fractional iterates and flows, and negative iterates

Template:Color is a trivial functional 5th root of Template:Color. The computation of f(Template:Frac) = Template:Frac = g⁵(Template:Frac) is shown.

The notion Template:Math must be used with care when the equation Template:Math has multiple solutions, which is normally the case, as in Babbage's equation of the functional roots of the identity map. For example, for Template:Math and Template:Math, both Template:Math and Template:Math are solutions; so the expression Template:Math does not denote a unique function, just as numbers have multiple algebraic roots. A trivial root of f can always be obtained if fTemplate:'s domain can be extended sufficiently, cf. picture. The roots chosen are normally the ones belonging to the orbit under study.

Fractional iteration of a function can be defined: for instance, a half iterate of a function Template:Mvar is a function Template:Mvar such that Template:Math. This function Template:Math can be written using the index notation as Template:Math . Similarly, Template:Math is the function defined such that Template:Math, while Template:Math may be defined as equal to Template:Math, and so forth, all based on the principle, mentioned earlier, that Template:Math. This idea can be generalized so that the iteration count Template:Mvar becomes a continuous parameter, a sort of continuous "time" of a continuous orbit.

In such cases, one refers to the system as a flow (cf. section on conjugacy below.)

If a function is bijective (and so possesses an inverse function), then negative iterates correspond to function inverses and their compositions. For example, Template:Math is the normal inverse of Template:Mvar, while Template:Math is the inverse composed with itself, i.e. Template:Math. Fractional negative iterates are defined analogously to fractional positive ones; for example, Template:Math is defined such that Template:Math, or, equivalently, such that Template:Math.

Some formulas for fractional iteration

One of several methods of finding a series formula for fractional iteration, making use of a fixed point, is as follows.

1. First determine a fixed point for the function such that Template:Math.
2. Define Template:Math for all n belonging to the reals. This, in some ways, is the most natural extra condition to place upon the fractional iterates.
3. Expand Template:Math around the fixed point a as a Taylor series, $$f^n(x)=f^n(a)+(x-a){\frac{d}{dx}{f}^n(x)|}_{x=a}+\frac{(x-a{)}^2}{2}{\frac{d^2}{d{x}^2}{f}^n(x)|}_{x=a}+\cdots$$
4. Expand out $$f^n(x)=f^n(a)+(x-a)f^{\prime }(a)f^{\prime }(f(a))f^{\prime }(f^2(a))\cdots f^{\prime }(f^{n-1}(a))+\cdots$$
5. Substitute in for Template:Math, for any k, $$f^n(x)=a+(x-a)f^{\prime }(a{)}^n+\frac{(x-a{)}^2}{2}(f^{″}(a)f^{\prime }(a{)}^{n-1})(1+f^{\prime }(a)+\cdots +f^{\prime }(a{)}^{n-1})+\cdots$$
6. Make use of the geometric progression to simplify terms, $$f^n(x)=a+(x-a)f^{\prime }(a{)}^n+\frac{(x-a{)}^2}{2}(f^{″}(a)f^{\prime }(a{)}^{n-1})\frac{f^{\prime }(a{)}^n-1}{f^{\prime }(a)-1}+\cdots$$ There is a special case when Template:Math, $$f^n(x)=x+\frac{(x-a{)}^2}{2}(n{f}^{″}(a))+\frac{(x-a{)}^3}{6}(\frac{3}{2}n(n-1)f^{″}(a{)}^2+n{f}^{‴}(a))+\cdots$$

This can be carried on indefinitely, although inefficiently, as the latter terms become increasingly complicated. A more systematic procedure is outlined in the following section on Conjugacy.

Example 1

For example, setting Template:Math gives the fixed point Template:Math, so the above formula terminates to just $$f^n(x)=\frac{D}{1-C}+(x-\frac{D}{1-C})C^n=C^{n}x+\frac{1-C^n}{1-C}D,$$ which is trivial to check.

Example 2

Find the value of ${\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{\cdots }}}$ where this is done n times (and possibly the interpolated values when n is not an integer). We have Template:Math. A fixed point is Template:Math.

So set Template:Math and Template:Math expanded around the fixed point value of 2 is then an infinite series, $${\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{\cdots }}}=f^n(1)=2-(\ln 2{)}^n+\frac{(\ln 2{)}^{n+1}((\ln 2{)}^n-1)}{4(\ln 2-1)}-\cdots$$ which, taking just the first three terms, is correct to the first decimal place when n is positive. Also see Tetration: Template:Math. Using the other fixed point Template:Math causes the series to diverge.

For Template:Math, the series computes the inverse function Template:Sfrac.

Example 3

With the function Template:Math, expand around the fixed point 1 to get the series $$f^n(x)=1+b^n(x-1)+\frac{1}{2}{b}^n(b^n-1)(x-1{)}^2+\frac{1}{3!}{b}^n(b^n-1)(b^n-2)(x-1{)}^3+\cdots ,$$ which is simply the Taylor series of x^{(bn )} expanded around 1.

Conjugacy

If Template:Mvar and Template:Mvar are two iterated functions, and there exists a homeomorphism Template:Mvar such that Template:Math, then Template:Mvar and Template:Mvar are said to be topologically conjugate.

Clearly, topological conjugacy is preserved under iteration, as Template:Math. Thus, if one can solve for one iterated function system, one also has solutions for all topologically conjugate systems. For example, the tent map is topologically conjugate to the logistic map. As a special case, taking Template:Math, one has the iteration of Template:Math as

Template:Math,   for any function Template:Mvar.

Making the substitution Template:Math yields

Template:Math,   a form known as the Abel equation.

Even in the absence of a strict homeomorphism, near a fixed point, here taken to be at Template:Mvar = 0, Template:Mvar(0) = 0, one may often solve Schröder's equation for a function Ψ, which makes Template:Math locally conjugate to a mere dilation, Template:Math, that is

Template:Math.

Thus, its iteration orbit, or flow, under suitable provisions (e.g., Template:Math), amounts to the conjugate of the orbit of the monomial,

Template:Math,

where Template:Mvar in this expression serves as a plain exponent: functional iteration has been reduced to multiplication! Here, however, the exponent Template:Mvar no longer needs be integer or positive, and is a continuous "time" of evolution for the full orbit: the monoid of the Picard sequence (cf. transformation semigroup) has generalized to a full continuous group.

Iterates of the sine function (blue), in the first half-period. Half-iterate (orange), i.e., the sine's functional square root; the functional square root of that, the quarter-iterate (black) above it; and further fractional iterates up to the 1/64th. The functions below the (blue) sine are six integral iterates below it, starting with the second iterate (red) and ending with the 64th iterate. The green envelope triangle represents the limiting null iterate, the sawtooth function serving as the starting point leading to the sine function. The dashed line is the negative first iterate, i.e. the inverse of sine (arcsin). (From the general pedagogy web-site. For the notation, see [1].)

This method (perturbative determination of the principal eigenfunction Ψ, cf. Carleman matrix) is equivalent to the algorithm of the preceding section, albeit, in practice, more powerful and systematic.

Markov chains

If the function is linear and can be described by a stochastic matrix, that is, a matrix whose rows or columns sum to one, then the iterated system is known as a Markov chain.

Examples

There are many chaotic maps. Well-known iterated functions include the Mandelbrot set and iterated function systems.

Ernst Schröder, in 1870, worked out special cases of the logistic map, such as the chaotic case Template:Math, so that Template:Math, hence Template:Math.

A nonchaotic case Schröder also illustrated with his method, Template:Math, yielded Template:Math, and hence Template:Math.

If Template:Mvar is the action of a group element on a set, then the iterated function corresponds to a free group.

Most functions do not have explicit general closed-form expressions for the n-th iterate. The table below lists some that do. Note that all these expressions are valid even for non-integer and negative n, as well as non-negative integer n.

$f(x)$	$f^n(x)$
$x+b$	$x+nb$
$ax+b(a\ne 1)$	$a^{n}x+\frac{a^n-1}{a-1}b$
$a{x}^b(b\ne 1)$	$a^{\frac{b^n-1}{b-1}}{x}^{b^n}$
$a{x}^2+bx+\frac{b^2-2b}{4a}$ (see note)	$\frac{2{\alpha }^{2^n}-b}{2a}$ where: $\alpha =\frac{2ax+b}{2}$
$a{x}^2+bx+\frac{b^2-2b-8}{4a}$ (see note)	$\frac{2{\alpha }^{2^n}+2{\alpha }^{-2^n}-b}{2a}$ where: $\alpha =\frac{2ax+b\pm \sqrt{(2ax+b{)}^2-16}}{4}$
$\frac{ax+b}{cx+d}$   (fractional linear transformation)	$\frac{a}{c}+\frac{bc-ad}{c}\left[\frac{(cx-a+\alpha ){\alpha }^{n-1}-(cx-a+\beta ){\beta }^{n-1}}{(cx-a+\alpha ){\alpha }^n-(cx-a+\beta ){\beta }^n}\right]$ where: $\alpha =\frac{a+d+\sqrt{(a-d{)}^2+4bc}}{2}$ $\beta =\frac{a+d-\sqrt{(a-d{)}^2+4bc}}{2}$
$g^{-1}\left(h\right(g(x)\left)\right)$	$g^{-1}\left(h^n\right(g(x)\left)\right)$
$g^{-1}(g(x)+b)$   (generic Abel equation)	$g^{-1}(g(x)+nb)$
$\sqrt{x^2+b}$	$\sqrt{x^2+bn}$
$g^{-1}(ag(x)+b)(a\ne 1\vee b=0)$	$g^{-1}(a^{n}g(x)+\frac{a^n-1}{a-1}b)$
$\sqrt{a{x}^2+b}$	$\sqrt{a^n{x}^2+\frac{a^n-1}{a-1}b}$
$T_m(x)=\cos (m\arccos x)$ (Chebyshev polynomial for integer m)	$T_{mn}=\cos (m^n\arccos x)$

Note: these two special cases of Template:Math are the only cases that have a closed-form solution. Choosing b = 2 = –a and b = 4 = –a, respectively, further reduces them to the nonchaotic and chaotic logistic cases discussed prior to the table.

Some of these examples are related among themselves by simple conjugacies.

Means of study

Iterated functions can be studied with the Artin–Mazur zeta function and with transfer operators.

In computer science

In computer science, iterated functions occur as a special case of recursive functions, which in turn anchor the study of such broad topics as lambda calculus, or narrower ones, such as the denotational semantics of computer programs.

Definitions in terms of iterated functions

Two important functionals can be defined in terms of iterated functions. These are summation:

$\{b+1,\sum _{i=a}^{b}g(i)\}\equiv {(\{i,x\}\to \{i+1,x+g(i)\})}^{b-a+1}\{a,0\}$

and the equivalent product:

$\{b+1,\prod _{i=a}^{b}g(i)\}\equiv {(\{i,x\}\to \{i+1,xg(i)\})}^{b-a+1}\{a,1\}$

Functional derivative

The functional derivative of an iterated function is given by the recursive formula:

$\frac{\delta f^N(x)}{\delta f(y)}=f^{\prime }(f^{N-1}(x))\frac{\delta f^{N-1}(x)}{\delta f(y)}+\delta (f^{N-1}(x)-y)$

Lie's data transport equation

Template:See also Iterated functions crop up in the series expansion of combined functions, such as Template:Math.

Given the iteration velocity, or beta function (physics),

$v(x)={\frac{\partial f^n(x)}{\partial n}|}_{n=0}$

for the Template:Mvar^th iterate of the function Template:Mvar, we have

$g(f(x))=\exp [v(x)\frac{\partial }{\partial x}]g(x).$

For example, for rigid advection, if Template:Math, then Template:Math. Consequently, Template:Math, action by a plain shift operator.

Conversely, one may specify Template:Math given an arbitrary Template:Math, through the generic Abel equation discussed above,

$f(x)=h^{-1}(h(x)+1),$

where

$h(x)=\int \frac{1}{v(x)}dx.$

This is evident by noting that

$f^n(x)=h^{-1}(h(x)+n).$

For continuous iteration index Template:Mvar, then, now written as a subscript, this amounts to Lie's celebrated exponential realization of a continuous group,

$e^{t\frac{\partial }{\partial h(x)}}g(x)=g(h^{-1}(h(x)+t))=g(f_t(x)).$

The initial flow velocity Template:Mvar suffices to determine the entire flow, given this exponential realization which automatically provides the general solution to the translation functional equation,

$f_t(f_{\tau }(x))=f_{t+\tau }(x).$

See also

• Irrational rotation
• Iterated function system
• Iterative method
• Rotation number
• Sarkovskii's theorem
• Fractional calculus
• Recurrence relation
• Schröder's equation
• Functional square root
• Abel function
• Schröder's equation
• Böttcher's equation
• Infinite compositions of analytic functions
• Flow (mathematics)
• Tetration
• Functional equation

External links

• Template:Cite web