Iterated function

The process of repeatedly applying the same function is called iteration.

For example, on the image on the right: Iterated functions are studied in computer science, fractals, dynamical systems, mathematics and renormalization group physics.

This notation has been traced to and John Frederick William Herschel in 1813.

For the same purpose, f [n](x) was used by Benjamin Peirce[6][4][nb 1] whereas Alfred Pringsheim and Jules Molk suggested nf(x) instead.

indices m and n, this relation is called the translation functional equation, cf.

The relation (f m)n(x) = (f n)m(x) = f mn(x) also holds, analogous to the property of exponentiation that (am)n = (an)m = amn.

If x = f(x) for some x in X (that is, the period of the orbit of x is 1), then x is called a fixed point of the iterated sequence.

There are several techniques for convergence acceleration of the sequences produced by fixed point iteration.

Upon iteration, one may find that there are sets that shrink and converge towards a single point.

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.

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.

The theory of subshifts of finite type provides general insight into many iterated functions, especially those leading to chaos.

For example, for n = 2 and f(x) = 4x − 6, both g(x) = 6 − 2x and g(x) = 2x − 2 are solutions; so the expression f 1/2(x) does not denote a unique function, just as numbers have multiple algebraic roots.

A trivial root of f can always be obtained if f's domain can be extended sufficiently, cf.

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

[15] This can be carried on indefinitely, although inefficiently, as the latter terms become increasingly complicated.

For example, setting f(x) = Cx + D gives the fixed point a = D/(1 − C), so the above formula terminates to just

So set x = 1 and f n (1) expanded around the fixed point value of 2 is then an infinite series,

With the function f(x) = xb, expand around the fixed point 1 to get the series

As a special case, taking f(x) = x + 1, one has the iteration of g(x) = h−1(h(x) + 1) as Making the substitution x = h−1(y) = ϕ(y) yields Even in the absence of a strict homeomorphism, near a fixed point, here taken to be at x = 0, f(0) = 0, one may often solve[16] Schröder's equation for a function Ψ, which makes f(x) locally conjugate to a mere dilation, g(x) = f '(0) x, that is Thus, its iteration orbit, or flow, under suitable provisions (e.g., f '(0) ≠ 1), amounts to the conjugate of the orbit of the monomial, where n in this expression serves as a plain exponent: functional iteration has been reduced to multiplication!

Here, however, the exponent n no longer needs be integer or positive, and is a continuous "time" of evolution for the full orbit:[17] the monoid of the Picard sequence (cf.

transformation semigroup) has generalized to a full continuous group.

[18] 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.

A nonchaotic case Schröder also illustrated with his method, f(x) = 2x(1 − x), yielded Ψ(x) = −⁠1/2⁠ ln(1 − 2x), and hence fn(x) = −⁠1/2⁠((1 − 2x)2n − 1).

Most functions do not have explicit general closed-form expressions for the n-th iterate.

Choosing b = 2 = –a and b = 4 = –a, respectively, further reduces them to the nonchaotic and chaotic logistic cases discussed prior to the table.

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.

Given the iteration velocity, or beta function (physics), for the nth iterate of the function f, we have[22] For example, for rigid advection, if f(x) = x + t, then v(x) = t. Consequently, g(x + t) = exp(t ∂/∂x) g(x), action by a plain shift operator.

Conversely, one may specify f(x) given an arbitrary v(x), through the generic Abel equation discussed above, where This is evident by noting that For continuous iteration index t, then, now written as a subscript, this amounts to Lie's celebrated exponential realization of a continuous group, The initial flow velocity v suffices to determine the entire flow, given this exponential realization which automatically provides the general solution to the translation functional equation,[23]

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.
g : R → R is a trivial functional 5th root of f : R + → R + , f ( x ) = sin( x ) . The computation of f ( π ⁄ 6 ) = 1 ⁄ 2 = g 5 ( π ⁄ 6 ) is shown.
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. [ 19 ] For the notation, see [2] .)