Inmathematics, aniterated function is a function that is obtained bycomposing another function with itself two or several times. The process of repeatedly applying the same function is callediteration. 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:

${\displaystyle L=F(K),M=F\circ F(K)=F^2(K).}$

Iterated functions are studied incomputer science,fractals,dynamical systems, mathematics andrenormalization group physics.

The formal definition of an iterated function on asetX follows.

LetX be a set andf:X →X be afunction.

Definingfⁿ as then-th iterate off, wheren is a non-negative integer, by:$${\displaystyle f^0\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{\mathrm{id}}_X}$$and$${\displaystyle f^{n+1}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}f\circ f^n,}$$

whereid_X is theidentity function onX and(f${\displaystyle \circ }$g)(x) =f (g(x)) denotesfunction composition. This notation has been traced to andJohn Frederick William Herschel in 1813.^[1][2][3][4] Herschel creditedHans Heinrich Bürmann for it, but without giving a specific reference to the work of Bürmann, which remains undiscovered.^[5]

Because the notationfⁿ may refer to both iteration (composition) of the functionf orexponentiation of the functionf (the latter is commonly used intrigonometry), some mathematicians^{[citation needed]} choose to use∘ to denote the compositional meaning, writingf^∘n(x) for then-th iterate of the functionf(x), as in, for example,f^∘3(x) meaningf(f(f(x))). For the same purpose,f^[n](x) was used byBenjamin Peirce^{[6][4][nb 1]} whereasAlfred Pringsheim andJules Molk suggestedⁿf(x) instead.^{[7][4][nb 2]}

In general, the following identity holds for all non-negative integersm andn,

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

This is structurally identical to the property ofexponentiation thata^maⁿ =a^{m +n}.

In general, for arbitrary general (negative, non-integer, etc.) indicesm andn, this relation is called thetranslation functional equation, cf.Schröder's equation andAbel equation. On a logarithmic scale, this reduces to thenesting property ofChebyshev polynomials,T_m(T_n(x)) =T_{m n}(x), sinceT_n(x) = cos(n arccos(x)).

The relation(f^m)ⁿ(x) = (fⁿ)^m(x) =f^mn(x) also holds, analogous to the property of exponentiation that(a^m)ⁿ = (aⁿ)^m =a^mn.

The sequence of functionsfⁿ is called aPicard sequence,^[8][9] named afterCharles Émile Picard.

For a givenx inX, thesequence of valuesfⁿ(x) is called theorbit ofx.

Iffⁿ (x) =f^n+m (x) for some integerm > 0, the orbit is called aperiodic orbit. The smallest such value ofm for a givenx is called theperiod of the orbit. The pointx itself is called aperiodic point. Thecycle detection problem in computer science is thealgorithmic problem of finding the first periodic point in an orbit, and the period of the orbit.

Ifx = f(x) for somex inX (that is, the period of the orbit ofx is1), thenx is called afixed point of the iterated sequence. The set of fixed points is often denoted asFix(f). There exist a number offixed-point theorems that guarantee the existence of fixed points in various situations, including theBanach fixed point theorem and theBrouwer fixed point theorem.

There are several techniques forconvergence acceleration of the sequences produced byfixed point iteration.^[10] For example, theAitken method applied to an iterated fixed point is known asSteffensen'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 anattractive fixed point. Conversely, iteration may give the appearance of points diverging away from a single point; this would be the case for anunstable fixed point.^[11]

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

The ideas of attraction and repulsion generalize similarly; one may categorize iterates intostable sets andunstable sets, according to the behavior of smallneighborhoods under iteration. Also seeinfinite 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.

If one considers the evolution of a density distribution, rather than that of individual point dynamics, then the limiting behavior is given by theinvariant 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 ortransfer 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, theKoopman operator can both be interpreted asshift operators action on ashift space. The theory ofsubshifts of finite type provides general insight into many iterated functions, especially those leading to chaos.

The notionf^1/n must be used with care when the equationgⁿ(x) =f(x) has multiple solutions, which is normally the case, as inBabbage's equation of the functional roots of the identity map. For example, forn = 2 andf(x) = 4x − 6, bothg(x) = 6 − 2x andg(x) = 2x − 2 are solutions; so the expressionf ^1/2(x) does not denote a unique function, just as numbers have multiple algebraic roots. A trivial root off can always be obtained iff'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, ahalf iterate of a functionf is a functiong such thatg(g(x)) =f(x).^[12] This functiong(x) can be written using the index notation asf ^1/2(x) . Similarly,f ^1/3(x) is the function defined such thatf^1/3(f^1/3(f^1/3(x))) =f(x), whilef^2/3(x) may be defined as equal tof ^1/3(f^1/3(x)), and so forth, all based on the principle, mentioned earlier, thatf^m ○fⁿ =f^{m +n}. This idea can be generalized so that the iteration countn becomes acontinuous parameter, a sort of continuous "time" of a continuousorbit.^[13][14]

In such cases, one refers to the system as aflow (cf. section onconjugacy below.)

If a function is bijective (and so possesses an inverse function), then negative iterates correspond to function inverses and their compositions. For example,f ⁻¹(x) is the normal inverse off, whilef ⁻²(x) is the inverse composed with itself, i.e.f ⁻²(x) =f ⁻¹(f ⁻¹(x)). Fractional negative iterates are defined analogously to fractional positive ones; for example,f ^−1/2(x) is defined such thatf ^−1/2(f ^−1/2(x)) =f ⁻¹(x), or, equivalently, such thatf ^−1/2(f ^1/2(x)) =f ⁰(x) =x.

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

1. First determine a fixed point for the function such thatf(a) =a.
2. Definefⁿ(a) =a for alln belonging to the reals. This, in some ways, is the most natural extra condition to place upon the fractional iterates.
3. Expandfⁿ(x) around the fixed pointa as aTaylor series,$${\displaystyle 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$${\displaystyle 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 forf^k(a) =a, for anyk,$${\displaystyle f^n(x)=a+(x-a)f^{\prime }(a{)}^n+\frac{(x-a{)}^2}{2}(f^{″}(a)f^{\prime }(a{)}^{n-1})\left(1+f^{\prime }(a)+\cdots +f^{\prime }(a{)}^{n-1}\right)+\cdots }$$
6. Make use of thegeometric progression to simplify terms,$${\displaystyle 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 whenf '(a) = 1,$${\displaystyle f^n(x)=x+\frac{(x-a{)}^2}{2}(n{f}^{″}(a))+\frac{(x-a{)}^3}{6}\left(\frac{3}{2}n(n-1)f^{″}(a{)}^2+n{f}^{‴}(a)\right)+\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 onConjugacy.

For example, settingf(x) =Cx +D gives the fixed pointa =D/(1 −C), so the above formula terminates to just$${\displaystyle f^n(x)=\frac{D}{1-C}+\left(x-\frac{D}{1-C}\right)C^n=C^{n}x+\frac{1-C^n}{1-C}D,}$$which is trivial to check.

Find the value of${\displaystyle {\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{\cdots }}}}$ where this is donen times (and possibly the interpolated values whenn is not an integer). We havef(x) =√2^x. A fixed point isa =f(2) = 2.

So setx = 1 andfⁿ (1) expanded around the fixed point value of 2 is then an infinite series,$${\displaystyle {\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 whenn is positive. Also seeTetration:fⁿ(1) =ⁿ√2. Using the other fixed pointa =f(4) = 4 causes the series to diverge.

Forn = −1, the series computes the inverse function⁠2+lnx/ln 2⁠.

With the functionf(x) =x^b, expand around the fixed point 1 to get the series$${\displaystyle 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 ofx^{(bn )} expanded around 1.

Iff andg are two iterated functions, and there exists ahomeomorphismh such thatg =h⁻¹ ○f ○h, thenf andg are said to betopologically conjugate.

Clearly, topological conjugacy is preserved under iteration, asgⁿ = h⁻¹  ○ fⁿ ○h. Thus, if one can solve for one iterated function system, one also has solutions for all topologically conjugate systems. For example, thetent map is topologically conjugate to thelogistic map. As a special case, takingf(x) =x + 1, one has the iteration ofg(x) =h⁻¹(h(x) + 1) as

gⁿ(x) =h⁻¹(h(x) + n),   for any functionh.

Making the substitutionx =h⁻¹(y) =ϕ(y) yields

g(ϕ(y)) =ϕ(y+1),   a form known as theAbel equation.

Even in the absence of a strict homeomorphism, near a fixed point, here taken to be atx = 0,f(0) = 0, one may often solve^[16]Schröder's equation for a function Ψ, which makesf(x) locally conjugate to a mere dilation,g(x) =f '(0)x, that is

f(x) = Ψ⁻¹(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,

Ψ⁻¹(f '(0)ⁿ Ψ(x)),

wheren in this expression serves as a plain exponent:functional iteration has been reduced to multiplication! Here, however, the exponentn no longer needs be integer or positive, and is a continuous "time" of evolution for the full orbit:^[17] themonoid of the Picard sequence (cf.transformation semigroup) has generalized to a fullcontinuous group.^[18]

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

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

There aremany chaotic maps. Well-known iterated functions include theMandelbrot set anditerated function systems.

Ernst Schröder,^[20] in 1870, worked out special cases of thelogistic map, such as the chaotic casef(x) = 4x(1 −x), so thatΨ(x) = arcsin(√x)², hencefⁿ(x) = sin(2ⁿ arcsin(√x))².

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

Iff is theaction of a group element on a set, then the iterated function corresponds to afree group.

Most functions do not have explicit generalclosed-form expressions for then-th iterate. The table below lists some^[20] that do. Note that all these expressions are valid even for non-integer and negativen, as well as non-negative integern.

${\displaystyle f(x)}$	${\displaystyle f^n(x)}$
${\displaystyle x+b}$	${\displaystyle x+nb}$
${\displaystyle ax+b(a\ne 1)}$	${\displaystyle a^{n}x+\frac{a^n-1}{a-1}b}$
${\displaystyle a{x}^b(b\ne 1)}$	${\displaystyle a^{\frac{b^n-1}{b-1}}{x}^{b^n}}$
${\displaystyle a{x}^2+bx+\frac{b^2-2b}{4a}}$ (see note)	${\displaystyle \frac{2{\alpha }^{2^n}-b}{2a}}$ where: ${\displaystyle \alpha =\frac{2ax+b}{2}}$
${\displaystyle a{x}^2+bx+\frac{b^2-2b-8}{4a}}$ (see note)	${\displaystyle \frac{2{\alpha }^{2^n}+2{\alpha }^{-2^n}-b}{2a}}$ where: ${\displaystyle \alpha =\frac{2ax+b\pm \sqrt{(2ax+b{)}^2-16}}{4}}$
${\displaystyle \frac{ax+b}{cx+d}}$   (fractional linear transformation)[21]	${\displaystyle \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: ${\displaystyle \alpha =\frac{a+d+\sqrt{(a-d{)}^2+4bc}}{2}}$ ${\displaystyle \beta =\frac{a+d-\sqrt{(a-d{)}^2+4bc}}{2}}$
${\displaystyle g^{-1}(h(g(x)))}$	${\displaystyle g^{-1}(h^n(g(x)))}$
${\displaystyle g^{-1}(g(x)+b)}$   (genericAbel equation)	${\displaystyle g^{-1}(g(x)+nb)}$
${\displaystyle \sqrt{x^2+b}}$	${\displaystyle \sqrt{x^2+bn}}$
${\displaystyle g^{-1}(ag(x)+b)(a\ne 1\vee b=0)}$	${\displaystyle g^{-1}(a^{n}g(x)+\frac{a^n-1}{a-1}b)}$
${\displaystyle \sqrt{a{x}^2+b}}$	${\displaystyle \sqrt{a^n{x}^2+\frac{a^n-1}{a-1}b}}$
${\displaystyle T_m(x)=\cos (m\arccos x)}$ (Chebyshev polynomial for integerm)	${\displaystyle T_{mn}=\cos (m^n\arccos x)}$

Note: these two special cases ofax² +bx +c are the only cases that have a closed-form solution. Choosingb = 2 = –a andb = 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.

Iterated functions can be studied with theArtin–Mazur zeta function and withtransfer operators.

Incomputer science, iterated functions occur as a special case ofrecursive functions, which in turn anchor the study of such broad topics aslambda calculus, or narrower ones, such as thedenotational semantics of computer programs.

Two importantfunctionals can be defined in terms of iterated functions. These aresummation:

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

and the equivalent product:

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

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

${\displaystyle \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)}$

Iterated functions crop up in the series expansion of combined functions, such asg(f(x)).

Given theiteration velocity, orbeta function (physics),

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

for then^th iterate of the functionf, we have^[22]

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

For example, for rigid advection, iff(x) =x +t, thenv(x) =t. Consequently,g(x +t) = exp(t ∂/∂x)g(x), action by a plainshift operator.

Conversely, one may specifyf(x) given an arbitraryv(x), through the genericAbel equation discussed above,

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

where

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

This is evident by noting that

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

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

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

The initial flow velocityv suffices to determine the entire flow, given this exponential realization which automatically provides the general solution to thetranslation functional equation,^[23]

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

• Gill, John (January 2017)."A Primer on the Elementary Theory of Infinite Compositions of Complex Functions". Colorado State University.

• Dynamical systems
• Fractals
• Sequences and series
• Fixed points (mathematics)
• Functions and mappings
• Functional equations

• CS1 French-language sources (fr)
• CS1 maint: location missing publisher
• CS1 maint: multiple names: authors list
• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from May 2019
• All articles with unsourced statements
• Articles with unsourced statements from August 2020