In mathematics, an iterated function is a function X → X (that is, a function from some set X to itself) which is obtained by composing another function f : X → X with itself a certain number of times. The process of repeatedly applying the same function is called iteration. In this process, starting from some initial number, the result of applying a given function is fed again in the function as input, and this process is repeated.
- 1 Definition
- 2 Abelian property and Iteration sequences
- 3 Fixed points
- 4 Limiting behaviour
- 5 Fractional iterates and flows, and negative iterates
- 6 Some formulas for fractional iteration
- 7 Conjugacy
- 8 Markov chains
- 9 Examples
- 10 Means of study
- 11 In computer science
- 12 Definitions in terms of iterated functions
- 13 Lie's data transport equation
- 14 See also
- 15 References
The formal definition of an iterated function on a set X follows.
Let X be a set and f: X → X be a function.
Define f n as the n-th iterate of f, where n is a non-negative integer, by:
- (f○g)(x) = f (g(x)),
Because the notation f n may refer to both iteration (composition) of the function f or exponentiation of the function f (the latter is commonly used in trigonometry), some mathematicians choose to write f °n for the n-th iterate of the function f.
Abelian property and Iteration sequences
In general, the following identity holds for all non-negative integers m and n,
This is structurally identical to the property of exponentiation that aman = am+n, i.e. the special case f(x)=ax.
In general, for arbitrary general (negative, non-integer, etc.) indices m and n, 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, Tm(Tn(x))=Tm n(x), since Tn(x) = cos(n arcos(x )).
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 f n (x) = f n+m (x) for some integer m, the orbit is called a periodic orbit. The smallest such value of m for a given x is called the period of the orbit. The point x 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.
If f(x) = 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. The set of fixed points is often denoted as Fix(f ). 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.
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 behaviour of small neighborhoods under iteration. (Also see Infinite compositions of analytic functions.)
Other limiting behaviours are possible; for example, wandering points are points that move away, and never come back even close to where they started.
Fractional iterates and flows, and negative iterates
In some instances, fractional iteration of a function can be defined: for instance, a half iterate of a function f is a function g such that g(g(x)) = f(x). This function g(x) can be written using the index notation as f ½(x) . Similarly, f ⅓(x) is the function defined such that f⅓(f⅓(f⅓(x))) = f(x), while f ⅔(x) may be defined equal to f ⅓(f ⅓(x)), and so forth, all based on the principle, mentioned earlier, that f m○f n = f m + n. This idea can be generalized so that the iteration count n becomes a continuous parameter, a sort of continuous "time" of a continuous orbit.
Negative iterates correspond to function inverses and their compositions. For example, f −1(x) is the normal inverse of f, while f −2(x) is the inverse composed with itself, i.e. f −2(x) = f −1(f −1(x)). Fractional negative iterates are defined analogously to fractional positive ones; for example, f −½(x) is defined such that f − ½(f −½(x)) = f −1(x), or, equivalently, such that f −½(f ½(x)) = f 0(x) = x.
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 f(a)=a .
(2) Define f n(a)=a 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 f n(x) around the fixed point a as a Taylor series,
(4) Expand out
(5) Substitute in for f k(a)= a, for any k,
(6) Make use of the geometric progression to simplify terms,
(6b) There is a special case when f '(a)=1,
(7) When n is not an integer, make use of the power formula y n = exp(n ln(y)).
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.
For example, setting f(x) = Cx+D gives the fixed point a = D/(1-C), so the above formula terminates to just
which is trivial to check.
Find the value of where this is done n times (and possibly the interpolated values when n is not an integer). We have f(x)=√x. A fixed point is a=f(2)=2.
So set x=1 and f n (1) expanded around the fixed point value of 2 is then an infinite series,
which, taking just the first three terms, is correct to the first decimal place when n is positive—cf. Tetration: f n(1) = n√ . (Using the other fixed point a = f(4) = 4 causes the series to diverge.)
For n = −1, the series computes the inverse function, 2 lnx/ln2.
With the function f(x) = xb, expand around the fixed point 1 to get the series
which is simply the Taylor series of x(bn ) expanded around 1.
Clearly, topological conjugacy is preserved under iteration, as gn=h−1 ○ f n ○ h. 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 f(x) = x+1, one has the iteration of g(x) = h−1(h(x)+1) as
- gn(x) = h−1(h(x) + n), for any function h.
Making the substitution x = h−1(y) = ϕ(y) yields
- g(ϕ(y)) = ϕ(y+1), a form known as the Abel equation.
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 Schröder's equation for a function Ψ, which makes f(x) locally conjugate to a mere dilation, g(x) = f '(0) x, that is
- f(x) = Ψ−1(f '(0) Ψ(x)).
Thus, its iteration orbit, or flow, under suitable provisions (e.g., f '(0) ≠ 1), amounts to the conjugate of the orbit of the monomial,
- Ψ−1(f '(0)n Ψ(x)),
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: the monoid of the Picard sequence (cf. transformation semigroup) has generalized to a full continuous group.
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) = −½ ln(1−2x), and hence f n(x) = −½((1−2x)2n−1).
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 positive integer n.
| (see note)
| (see note)
|(rational difference equation)||
|(generic Abel equation)|
Note: these two special cases of ax2 + bx + c 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. A few further examples, essentially amounting to simple conjugacies of Schröder's examples can be found in ref.
Means of study
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
and the equivalent product:
Lie's data transport equation
Iterated functions crop up in the series expansion of the combined functions, such as g(f(x)).
For example, for rigid advection, if f(x) = x + a, then v(x) = a. Consequently g(x + a) = exp(a ∂/∂x) g(x), a plain shift operator.
One may further find f(x) given v(x), through the Abel equation discussed above,
This is evident by noting that
- Kuczma, Marek (1968). Functional equations in a single variable. Monografie Matematyczne. Warszawa: PWN – Polish Scientific Publishers.
- Kuczma, M., Choczewski B., and Ger, R. (1990). Iterative Functional Equations. Cambridge University Press. ISBN 0-521-35561-3.
- Carleson, L.; Gamelin, T. D. W. (1993). Complex dynamics. Universitext: Tracts in Mathematics. Springer-Verlag. ISBN 0-387-97942-5.
- Istratescu, Vasile (1981). Fixed Point Theory, An Introduction, D. Reidel, Holland. ISBN 90-277-1224-7.
- The notion f1/n must be used with care when the equation gn(x) = f(x) has multiple solutions, which is normally the case, as in Babbage's equation of the functional roots of the identity map. 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 ½(x) doesn't denote a unique function, just as algebraic roots of numbers are multiple. The issue is quite similar to division by zero. The roots chosen are normally the ones belonging to the orbit under study.
- Kimura, Tosihusa (1971). "On the Iteration of Analytic Functions", Funkcialaj Ekvacioj 14, 197-238.
- Curtright, T.L.; Zachos, C.K. (2009). "Evolution Profiles and Functional Equations". Journal of Physics A. 42 (48): 485208. doi:10.1088/1751-8113/42/48/485208.
- For explicit instance, example 2 above amounts to just f n(x) = Ψ−1((ln2)n Ψ(x)), for any n, not necessarily integer, where Ψ is the solution of the relevant Schröder's equation, Ψ(√x)= ln2 Ψ(x). This solution is also the infinite m limit of (f m(x) −2)/(ln2)m.
- Curtright, T.L. Evolution surfaces and Schröder functional methods.
- Schröder, Ernst (1870). "Ueber iterirte Functionen". Math. Ann. 3 (2): 296–322. doi:10.1007/BF01443992.
- Brand, Louis, "A sequence defined by a difference equation," American Mathematical Monthly 62, September 1955, 489–492. online
- Katsura, S.; Fukuda, W. (1985). "Exactly solvable models showing chaotic behavior". Physica A: Statistical Mechanics and its Applications. 130 (3): 597. doi:10.1016/0378-4371(85)90048-2.
- Berkson, E.; Porta, H. (1978). "Semigroups of analytic functions and composition operators". The Michigan Mathematical Journal. 25: 101. doi:10.1307/mmj/1029002009. Curtright, T. L.; Zachos, C. K. (2010). "Chaotic maps, Hamiltonian flows and holographic methods". Journal of Physics A: Mathematical and Theoretical. 43 (44): 445101. doi:10.1088/1751-8113/43/44/445101.