View source for Iterated function

{{Short description|Result of repeatedly applying a mathematical function}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}

[[File:Powers of rotation, shear, and their compositions.svg|thumb|400px|Iterated transformations of the object on the left<br>On top is a clockwise rotation by 90°. It has [[Order (group theory)|order]] 4, because that is the smallest positive exponent that produces the identity. Below is a [[shear mapping]] with infinite order.<br><small>Below that are their [[Function composition|compositions]], which both have order 3.</small>]]

In [[mathematics]], an '''iterated function''' is a function that is obtained by [[function composition|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:
:{{nobr|1=<math>L = F(K), \ M = F \circ F (K) = F^2(K).</math>}}

Iterated functions are studied in [[computer science]], [[fractals]], [[dynamical system]]s, mathematics and [[renormalization group]] physics.

==Definition==
The formal definition of an iterated function on a [[set (mathematics)|set]] ''X'' follows.

Let {{mvar|''X''}} be a set and {{math|''f'':  ''X'' → ''X''}} be a [[function (mathematics)|function]].

Defining {{math| ''f'' <sup>''n''</sup>}} as the ''n''-th iterate of {{mvar|''f''}}, where ''n'' is a non-negative integer, by:
<math display="block">f^0 ~   \stackrel{\mathrm{def}}{=}  ~ \operatorname{id}_X</math>
and
<math display="block">f^{n+1} ~ \stackrel{\mathrm{def}}{=} ~ f \circ f^{n},</math>

where {{math|id<sub>''X''</sub>}} is the [[identity function]] on {{mvar|''X''}} and {{math|(''f'' {{text| {{math| <math>\circ</math> }} }} ''g'')(''x'') {{=}} ''f'' (''g''(''x''))}} denotes [[function composition]]. This notation has been traced to and [[John Frederick William Herschel]] in 1813.<ref name="Herschel_1813"/><ref name="Herschel_1820"/><ref name="Peano_1903"/><ref name="Cajori_1929"/> Herschel credited [[Hans Heinrich Bürmann]] for it, but without giving a specific reference to the work of Bürmann, which remains undiscovered.<ref>{{cite book|title=Encounters with Chaos and Fractals|first1=Denny|last1=Gulick|first2=Jeff|last2=Ford|edition=3rd|publisher=CRC Press|year=2024|isbn=9781003835776|page=2|url=https://books.google.com/books?id=aVQIEQAAQBAJ&pg=PA2}}</ref>

Because the notation {{math|''f'' <sup>''n''</sup>}} may refer to both iteration (composition) of the function {{mvar|''f''}} or [[Exponentiation#Iterated functions|exponentiation of the function]] {{mvar|''f''}} (the latter is commonly used in [[trigonometric functions|trigonometry]]), some mathematicians{{citation needed|date=August 2020|reason=Origin? Example authors?}} choose to use {{math|∘}} to denote the compositional meaning, writing {{math|''f''{{i sup|∘''n''}}(''x'')}} for the {{mvar|n}}-th iterate of the function {{math|''f''(''x'')}}, as in, for example, {{math|''f''{{i sup|∘3}}(''x'')}} meaning {{math|''f''(''f''(''f''(''x'')))}}. For the same purpose, {{math|''f'' <sup>[''n'']</sup>(''x'')}} was used by [[Benjamin Peirce]]<ref name="Peirce_1852"/><ref name="Cajori_1929"/><ref group="nb">while {{math|''f'' <sup>(''n'')</sup>}} is taken for the [[Derivative#Lagrange's notation|{{math|''n''}}th derivative]]</ref> whereas [[Alfred Pringsheim]] and [[Jules Molk]] suggested {{math|{{i sup|''n''}}''f''(''x'')}} instead.<ref name="Pringsheim-Molk_1907"/><ref name="Cajori_1929"/><ref group="nb" name="NB_Rucker"/>

==Abelian property and iteration sequences==
In general, the following identity holds for all non-negative integers {{mvar|m}} and {{mvar|n}},

: <math>f^m \circ f^n =   f^n \circ f^m = f^{m+n}~.</math>

This is structurally identical to the property of [[exponentiation]] that {{math|1=''a''<sup>''m''</sup>''a''<sup>''n''</sup> = ''a''<sup>''m'' + ''n''</sup>}}.

In general, for arbitrary general (negative, non-integer, etc.) indices {{mvar|m}} and {{mvar|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]], {{math|1=''T''<sub>''m''</sub>(''T''<sub>''n''</sub>(''x'')) = ''T''<sub>''m n''</sub>(''x'')}}, since  {{math|1=''T''<sub>''n''</sub>(''x'') = cos(''n'' arccos(''x''))}}.

The relation  {{math|1=(''f''<sup> ''m''</sup>)<sup>''n''</sup>(''x'') = (''f''<sup> ''n''</sup>)<sup>''m''</sup>(''x'') = ''f''<sup> ''mn''</sup>(''x'')}} also holds, analogous to the property of exponentiation that  {{math|1=(''a''<sup>''m''</sup>)<sup>''n''</sup> = (''a''<sup>''n''</sup>)<sup>''m''</sup> = ''a''<sup>''mn''</sup>}}.

The sequence of functions  {{math|''f'' <sup>''n''</sup>}} is called a '''Picard sequence''',<ref>{{cite book |title=Functional equations in a single variable |last=Kuczma |first=Marek| author-link=Marek Kuczma|series=Monografie Matematyczne |year=1968 |publisher=PWN – Polish Scientific Publishers |location=Warszawa}}</ref><ref>{{cite book|title=Iterative Functional Equations| last=Kuczma| first=M., Choczewski B., and Ger, R. |year=1990|publisher=Cambridge University Press|isbn= 0-521-35561-3|url=https://archive.org/details/iterativefunctio0000kucz|url-access=registration}}</ref> named after [[Charles Émile Picard]].

For a given {{mvar|x}} in {{mvar|X}}, the [[sequence]] of values  {{math|''f''<sup>''n''</sup>(''x'')}} is called the '''[[orbit (dynamics)|orbit]]''' of {{mvar|x}}.

If  {{math|1=''f'' <sup>''n''</sup> (''x'') =  ''f'' <sup>''n''+''m''</sup> (''x'')}} for some integer {{math|m > 0}}, the orbit is called a '''periodic orbit'''. The smallest such value of {{mvar|m}} for a given {{mvar|x}} is called the '''period of the orbit'''. The point {{mvar|x}} itself is called a [[periodic point]]. The [[cycle detection]] problem in computer science is the [[algorithm]]ic problem of finding the first periodic point in an orbit, and the period of the orbit.

==Fixed points==

If {{math|1='' ''x'' = f''(''x'')}} for some {{mvar|x}} in {{mvar|X}} (that is, the period of the orbit of {{mvar|x}} is {{math|1}}), then {{mvar|x}} is called a '''[[fixed point (mathematics)|fixed point]]''' of the iterated sequence.  The set of fixed points is often denoted as {{math|'''Fix'''(''f'')}}. There exist a number of [[fixed-point theorem]]s 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]].<ref>{{Cite book| last1=Carleson|first1=L.| last2=Gamelin|first2=T. D. W.| title=Complex dynamics|series=Universitext: Tracts in Mathematics| publisher=Springer-Verlag| year=1993| isbn=0-387-97942-5| url-access=registration| url=https://archive.org/details/complexdynamics0000carl}}</ref> 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]].<ref>Istratescu, Vasile  (1981). ''Fixed Point Theory, An Introduction'',  D. Reidel, Holland.  {{ISBN|90-277-1224-7}}.</ref>

When the points of the orbit converge to one or more limits, the set of [[accumulation point]]s 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 manifold|stable set]]s and [[unstable set]]s, according to the behavior of small [[Neighbourhood (mathematics)|neighborhood]]s under iteration. Also see [[infinite compositions of analytic functions]].

Other limiting behaviors are possible; for example, [[wandering point]]s 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 operator]]s 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==
[[File:TrivFctRootExm svg.svg|thumb|{{color|#20b080|''g'': '''R'''→'''R'''}} is a trivial functional 5th root of {{color|#901070|2=''f'': '''R'''<sup>+</sup>→'''R'''<sup>+</sup>, ''f''(''x'') = sin(''x'')}}. The computation of ''f''({{frac|π|6}}) = {{frac|1|2}} = ''g''<sup>5</sup>({{frac|π|6}}) is shown.]]
The notion {{math|''f''{{i sup|1/''n''}}}} must be used with care when the equation {{math|1=''g''<sup>''n''</sup>(''x'') = ''f''(''x'')}} has multiple solutions, which is normally the case, as in [[Functional square root|Babbage's equation]] of the functional roots of the identity map. For example, for {{math|1=''n'' = 2}} and {{math|1=''f''(''x'') = 4''x'' − 6}}, both {{math|1=''g''(''x'') = 6 − 2''x''}} and {{math|1=''g''(''x'') = 2''x'' − 2}} are solutions; so the expression {{math|''f''<sup> 1/2</sup>(''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. 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 [[functional square root|half iterate]] of a function {{mvar|f}} is a function {{mvar|g}} such that {{math|1=''g''(''g''(''x'')) = ''f''(''x'')}}.<ref>{{cite web |work=MathOverflow |title=Finding f such that f(f(x))=g(x) given g |url=https://mathoverflow.net/q/66538 }}</ref> This function {{math|''g''(''x'')}} can be written using the index notation as {{math|''f''<sup> 1/2</sup>(''x'')}} . Similarly, {{math|''f''<sup> 1/3</sup>(''x'')}} is the function defined such that {{math|1=''f''<sup>1/3</sup>(''f''<sup>1/3</sup>(''f''<sup>1/3</sup>(''x''))) = ''f''(''x'')}}, while {{math|''f''{{i sup|2/3}}(''x'')}} may be defined as equal to {{math|''f''{{i sup| 1/3}}(''f''{{i sup|1/3}}(''x''))}}, and so forth, all based on the principle, mentioned earlier, that {{math|1=''f''<sup> ''m''</sup> ○ ''f''<sup> ''n''</sup> = ''f''<sup> ''m'' + ''n''</sup>}}. This idea can be generalized so that the iteration count {{mvar|n}} becomes a '''continuous parameter''', a sort of continuous "time" of a continuous [[Orbit (dynamics)|orbit]].<ref>{{cite journal |first1=R. |last1=Aldrovandi |first2=L. P. |last2=Freitas |title=Continuous Iteration of Dynamical Maps |journal=J. Math. Phys. |volume=39 |issue=10 |pages=5324 |year=1998 |doi=10.1063/1.532574 |arxiv=physics/9712026 |bibcode=1998JMP....39.5324A |hdl=11449/65519 |s2cid=119675869 |hdl-access=free }}</ref><ref>{{cite journal |first1=G. |last1=Berkolaiko |first2=S. |last2=Rabinovich |first3=S. |last3=Havlin |title=Analysis of Carleman Representation of Analytical Recursions |journal=J. Math. Anal. Appl. |volume=224 |pages=81–90 |year=1998 |doi=10.1006/jmaa.1998.5986 |doi-access=free }}</ref>

In such cases, one refers to the system as a [[flow (mathematics)|flow]] (cf. section on [[#Conjugacy|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, {{math|''f''<sup> −1</sup>(''x'')}} is the normal inverse of {{mvar|f}}, while {{math|''f''<sup> −2</sup>(''x'')}} is the inverse composed with itself, i.e. {{math|1=''f''<sup> −2</sup>(''x'') = ''f''<sup> −1</sup>(''f''<sup> −1</sup>(''x''))}}. Fractional negative iterates are defined analogously to fractional positive ones; for example, {{math|''f''<sup> −1/2</sup>(''x'')}} is defined such that {{math|1=''f''<sup> −1/2</sup>(''f''<sup> −1/2</sup>(''x'')) = ''f''<sup> −1</sup>(''x'')}}, or, equivalently, such that {{math|1=''f''<sup> −1/2</sup>(''f''<sup> 1/2</sup>(''x'')) = ''f''<sup> 0</sup>(''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.<ref>{{cite web |title=Tetration.org |url=https://tetration.org/index.php/Fractional_Iteration }}</ref>

# First determine a fixed point for the function such that {{math|1=''f''(''a'') = ''a''}}.
# Define {{math|1=''f'' <sup>''n''</sup>(''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.
# Expand {{math|''f''<sup>''n''</sup>(''x'')}} around the fixed point ''a'' as a [[Taylor series]], <math display="block">
f^n(x) = f^n(a) + (x-a)\left.\frac{d}{dx}f^n(x)\right|_{x=a} + \frac{(x-a)^2}2\left.\frac{d^2}{dx^2}f^n(x)\right|_{x=a} +\cdots
</math>
# Expand out <math display="block">
f^n(x) = f^n(a) + (x-a) f'(a)f'(f(a))f'(f^2(a))\cdots f'(f^{n-1}(a)) + \cdots
</math>
# Substitute in for {{math|1=''f{{i sup|k}}''(''a'') = ''a''}}, for any ''k'', <math display="block">
f^n(x) = a + (x-a) f'(a)^n + \frac{(x-a)^2}2(f''(a)f'(a)^{n-1})\left(1+f'(a)+\cdots+f'(a)^{n-1} \right)+\cdots
</math>
# Make use of the [[geometric progression]] to simplify terms, <math display="block">
f^n(x) = a + (x-a) f'(a)^n + \frac{(x-a)^2}2(f''(a)f'(a)^{n-1})\frac{f'(a)^n-1}{f'(a)-1}+\cdots
</math> There is a special case when {{math|1=''f'' '(a) = 1}}, <math display="block">
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
</math>
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 {{math|''f''(''x'') {{=}} ''Cx'' + ''D''}} gives the fixed point {{math|''a'' {{=}} ''D''/(1 − ''C'')}}, so the above formula terminates to just
<math display="block">
f^n(x)=\frac{D}{1-C} + \left(x-\frac{D}{1-C}\right)C^n=C^nx+\frac{1-C^n}{1-C}D ~,
</math>
which is trivial to check.

====Example 2====
Find the value of <math>\sqrt{2}^{ \sqrt{2}^{\sqrt{2}^{\cdots}} }</math> where this is done ''n'' times (and possibly the interpolated values when ''n'' is not an integer). We have {{math|1=''f''(''x'') = {{sqrt|2}}<sup>''x''</sup>}}. A fixed point is {{math|1=''a'' = ''f''(2) = 2}}.

So set {{math|1=''x'' = 1}} and {{math|''f'' <sup>''n''</sup> (1)}} expanded around the fixed point value of 2 is then an infinite series,
<math display="block">
\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
</math>
which, taking just the first three terms, is correct to the first decimal place when ''n'' is positive. Also see [[Tetration]]: {{math|1=''f'' <sup>''n''</sup>(1) = <sup>''n''</sup>{{sqrt|2}}}}. Using the other fixed point {{math|1=''a'' = ''f''(4) {{=}} 4}} causes the series to diverge.

For {{math|1= ''n'' = −1}}, the series computes the inverse function {{sfrac|2|ln ''x''|ln 2}}.

====Example 3====
With the function {{math|''f''(''x'') {{=}} ''x''<sup>''b''</sup>}}, expand around the fixed point 1 to get the series
<math display="block">
f^n(x) = 1 + b^n(x-1) + \frac{1}2b^{n}(b^n-1)(x-1)^2 + \frac{1}{3!}b^n (b^n-1)(b^n-2)(x-1)^3 + \cdots ~,
</math>
which is simply the Taylor series of ''x''<sup>(''b''<sup>''n''</sup> )</sup> expanded around 1.

==Conjugacy==

If {{mvar|f}} and {{mvar|g}} are two iterated functions, and there exists a [[homeomorphism]] {{mvar|h}} such that  {{math| ''g'' {{=}}  ''h''<sup>−1</sup> ○ ''f'' ○ ''h'' }},  then {{mvar|f}} and {{mvar|g}} are said to be [[Topological conjugacy|topologically conjugate]].

Clearly, topological conjugacy is preserved under iteration, as {{math|''g''<sup>''n''</sup>&nbsp;{{=}}&nbsp;''h''<sup>−1</sup> &nbsp;○&nbsp;''f'' <sup>''n''</sup> ○ ''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 {{math|''f''(''x'') {{=}} ''x''&nbsp;+&nbsp;1}}, one has the iteration of {{math|''g''(''x'') {{=}} ''h''<sup>&minus;1</sup>(''h''(''x'')&nbsp;+&nbsp;1)}} as 
:{{math|''g''<sup>''n''</sup>(''x'') {{=}} ''h''<sup>&minus;1</sup>(''h''(''x'')&nbsp;+&nbsp;''n'')}},  &nbsp;  for any function {{mvar|h}}.

Making the substitution {{math|''x'' {{=}} ''h''<sup>&minus;1</sup>(''y'') {{=}} ''ϕ''(''y'')}} yields 
:{{math|''g''(''ϕ''(''y'')) {{=}} ''ϕ''(''y''+1)}},  &nbsp; a form known as the [[Abel equation]].

Even in the absence of a strict homeomorphism, near a fixed point, here taken to be at {{mvar|x}} = 0, {{mvar|f}}(0) = 0, one may often solve<ref>Kimura, Tosihusa (1971). "On the Iteration of Analytic Functions",  [http://www.math.sci.kobe-u.ac.jp/~fe/ ''Funkcialaj Ekvacioj''] {{Webarchive|url=https://web.archive.org/web/20120426011125/http://www.math.sci.kobe-u.ac.jp/~fe/|date=2012-04-26}} '''14''', 197-238.</ref> [[Schröder's equation]] for a function Ψ, which makes {{math|''f''(''x'')}} locally conjugate to a mere dilation, {{math|''g''(''x'') {{=}} ''f'' '(0) ''x''}}, that is  
:{{math|''f''(''x'') {{=}}  Ψ<sup>−1</sup>(''f'' '(0) Ψ(''x''))}}.

Thus, its iteration orbit, or flow, under suitable provisions (e.g., {{math|''f'' '(0) ≠ 1}}), amounts to the conjugate of the orbit of the monomial,
:{{math|Ψ<sup>−1</sup>(''f'' '(0)<sup>''n''</sup> Ψ(''x''))}},  
where {{mvar|n}} in this expression serves as a plain exponent: ''functional iteration has been reduced to multiplication!''  Here, however, the exponent {{mvar|n}} no longer needs be integer or positive, and is a continuous "time" of evolution for the full orbit:<ref>{{cite journal |author-last1=Curtright |author-first1=T. L. |author-link1=Thomas Curtright|author-last2=Zachos |author-first2=C. K. |author-link2=Cosmas Zachos | year=2009|title=Evolution Profiles and Functional Equations |journal=Journal of Physics A |volume=42|issue=48 |pages=485208|doi=10.1088/1751-8113/42/48/485208|arxiv=0909.2424|bibcode=2009JPhA...42V5208C|s2cid=115173476 }}</ref> the [[monoid]] of the Picard sequence (cf. [[transformation semigroup]]) has generalized to a full [[continuous group]].<ref>For explicit instance, example 2 above amounts to just {{math|''f'' <sup>''n''</sup>(''x'') {{=}} Ψ<sup>−1</sup>((ln&nbsp;2)<sup>''n''</sup> Ψ(''x''))}}, for ''any n'', not necessarily integer, where Ψ is the solution of the relevant [[Schröder's equation]], {{math|Ψ({{sqrt|2}}<sup>''x''</sup>) {{=}}&nbsp;ln&nbsp;2&nbsp;Ψ(''x'')}}. This solution is also the infinite ''m'' limit of {{math|(''f'' <sup>''m''</sup>(''x'')&nbsp;−&nbsp;2)/(ln&nbsp;2)<sup>''m''</sup>}}.</ref>

[[File:Sine_iterations.svg|right|thumb|380px|
Iterates of the sine function (<span style="color:blue">blue</span>), in the first half-period. Half-iterate (<span style="color:orange">orange</span>), 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 (<span style="color:blue">blue</span>)  sine are six integral iterates below it, starting with the second iterate (<span style="color:red">red</span>) and ending with the 64th iterate. The <span style="color:green">green</span> envelope triangle represents the limiting null iterate, a [[triangular 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.<ref>Curtright, T. L. [http://www.physics.miami.edu/~curtright/Schroeder.html Evolution surfaces and Schröder functional methods.]</ref> For the notation, see [http://www.physics.miami.edu/~curtright/TheRootsOfSin.pdf].)
]]

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 [[List of chaotic maps|many chaotic maps]]. Well-known iterated functions include the [[Mandelbrot set]] and [[iterated function systems]].

[[Ernst Schröder (mathematician)|Ernst Schröder]],<ref name="schr">{{cite journal |last=Schröder |first=Ernst |author-link=Ernst Schröder (mathematician) |year=1870 |title=Ueber iterirte Functionen|journal=Math. Ann. |volume=3 |issue= 2|pages=296–322 | doi=10.1007/BF01443992 |s2cid=116998358 }}</ref> in 1870, worked out special cases of the [[logistic map]], such as the chaotic case {{math|1=''f''(''x'') = 4''x''(1 − ''x'')}}, so that {{math|1=Ψ(''x'') = arcsin({{radic|''x''}})<sup>2</sup>}}, hence {{math|1=''f'' <sup>''n''</sup>(''x'') = sin(2<sup>''n''</sup> arcsin({{radic|''x''}}))<sup>2</sup>}}.

A nonchaotic case Schröder also illustrated with his method, {{math|1=''f''(''x'') = 2''x''(1 − ''x'')}}, yielded {{math|1=Ψ(''x'') = −{{sfrac|1|2}} ln(1 − 2''x'')}}, and hence  {{math|1=''f''<sup>''n''</sup>(''x'') = −{{sfrac|1|2}}((1 − 2''x'')<sup>2<sup>''n''</sup></sup> − 1)}}.

If {{mvar|''f''}} is the [[Group action (mathematics)|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 expression]]s for the ''n''-th iterate. The table below lists some<ref name="schr"/> that do. Note that all these expressions are valid even for non-integer and negative ''n'', as well as non-negative integer ''n''.

{| class=wikitable width=100%
!<math>f(x)</math>
!<math>f^n(x)</math>
|-
|<math>x+b</math>
|<math>x+nb</math>
|-
|<math>ax+b \ (a\ne 1)</math>
|<math>a^nx+\frac{a^n-1}{a-1}b</math>
|-
|<math>ax^b \ (b\ne 1)</math>
|<math>a^{\frac{b^n-1}{b-1}}x^{b^n}</math>
|-
|<math>ax^2 + bx + \frac{b^2 - 2b}{4a}</math> (see note)<br>
|<math>\frac{2\alpha^{2^n} - b}{2a}</math><br>
where:
*<math>\alpha = \frac{2ax + b}{2}</math>
|-
|<math>ax^2 + bx + \frac{b^2 - 2b - 8}{4a}</math> (see note)<br>
|<math>\frac{2\alpha^{2^n} + 2\alpha^{-2^n} - b}{2a}</math><br>
where:
*<math>\alpha = \frac{2ax + b \pm \sqrt{(2ax + b)^2 - 16}}{4}</math>
|-
|<math>\frac{ax + b}{cx + d}</math> &nbsp; ([[fractional linear transformation]])<ref>Brand, Louis, "A sequence defined by a difference equation," ''[[American Mathematical Monthly]]'' '''62''', September 1955, 489&ndash;492.   [https://www.jstor.org/discover/10.2307/2307362  online]</ref>
|<math>\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 ]</math><br>
where:
*<math>\alpha = \frac{a + d + \sqrt{(a - d)^2 + 4bc}}{2}</math>
*<math>\beta = \frac{a + d - \sqrt{(a - d)^2 + 4bc}}{2}</math>
|-
|<math>g^{-1}\Big(h\bigl(g(x)\bigr)\Big)</math>
|<math>g^{-1}\Bigl(h^n\bigl(g(x)\bigr)\Bigr)</math>
|-
|<math>g^{-1}\bigl(g(x)+b\bigr)</math> &nbsp; (generic [[Abel equation]])
|<math>g^{-1}\bigl(g(x)+nb\bigr)</math>
|-
| <math>\sqrt{x^2 + b}</math>
| <math>\sqrt{x^2 + bn}</math>
|-
|<math>g^{-1}\Bigl(a\ g(x)+b\Bigr) \ (a\ne 1 \vee b=0)</math>
|<math>g^{-1}\Bigl(a^ng(x)+\frac{a^n-1}{a-1}b\Bigr)</math>
|-
| <math>\sqrt{ax^2 + b}</math>
| <math>\sqrt{a^nx^2 + \frac{a^n - 1}{a - 1}b}</math>
|-
| <math>T_m (x)=\cos (m \arccos x)</math> ([[Chebyshev polynomials#Trigonometric definition|Chebyshev polynomial]] for integer ''m'')
| <math>T_{mn}=\cos(m^n \arccos x)</math>
|}
Note: these two special cases of {{math|''ax''<sup>2</sup> + ''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.

==Means of study==
Iterated functions can be studied with the [[Artin–Mazur zeta function]] and with [[transfer operator]]s.

==In computer science==
In [[computer science]], iterated functions occur as a special case of [[recursion (computer science)|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 [[functional (mathematics)|functionals]] can be defined in terms of iterated functions. These are [[summation]]:

:<math>
\left\{b+1,\sum_{i=a}^b g(i)\right\} \equiv \left( \{i,x\} \rightarrow \{ i+1 ,x+g(i) \}\right)^{b-a+1} \{a,0\}
</math>

and the equivalent product:

:<math>
\left\{b+1,\prod_{i=a}^b g(i)\right\} \equiv \left( \{i,x\} \rightarrow \{ i+1 ,x g(i) \}\right)^{b-a+1} \{a,1\}
</math>

==Functional derivative==
The [[functional derivative]] of an iterated function is given by the recursive formula:

:<math>\frac{ \delta f^N(x)}{\delta f(y)} = f'( f^{N-1}(x) ) \frac{ \delta f^{N-1}(x)}{\delta f(y)} + \delta( f^{N-1}(x) - y ) </math>

==Lie's data transport equation==
{{see also|Shift operator#Functions of a real variable}}
Iterated functions crop up in the series expansion of combined functions, such as  {{math|''g''(''f''(''x''))}}.

Given the [[Koenigs function#Structure of univalent semigroups|iteration velocity]], or [[beta function (physics)]],  
:<math>v(x) = \left. \frac{\partial f^n(x)}{\partial n} \right|_{n=0}</math> 
for the {{mvar|n}}<sup>th</sup> iterate of the function {{mvar|f}}, we have<ref>{{Cite journal | last1 = Berkson | first1 = E. | last2 = Porta | first2 = H. | doi = 10.1307/mmj/1029002009 | title = Semigroups of analytic functions and composition operators | journal = The Michigan Mathematical Journal | volume = 25 | pages = 101–115 | year = 1978 | doi-access = free }}  {{Cite journal | last1 = Curtright | first1 = T. L. | last2 = Zachos | first2 = C. K. | doi = 10.1088/1751-8113/43/44/445101 | title = Chaotic maps, Hamiltonian flows and holographic methods | journal = Journal of Physics A: Mathematical and Theoretical | volume = 43 | issue = 44 | pages = 445101 | year = 2010 | arxiv = 1002.0104 | bibcode = 2010JPhA...43R5101C | s2cid = 115176169 }}</ref>
:<math>
g(f(x)) = \exp\left[ v(x) \frac{\partial}{\partial x} \right] g(x).
</math>
For example, for rigid advection, if {{math|''f''(''x'') {{=}} ''x'' + ''t''}}, then {{math|''v''(''x'') {{=}} ''t''}}.  Consequently,  {{math|''g''(''x'' + ''t'') {{=}} exp(''t'' ∂/∂''x'')  ''g''(''x'')}}, action by a plain [[shift operator]].

Conversely, one may   specify {{math|''f''(''x'')}}  given an arbitrary {{math|''v''(''x'')}}, through the generic [[Abel equation]]  discussed above,
:<math>
f(x) = h^{-1}(h(x)+1) ,
</math>
where
:<math>
h(x) = \int \frac{1}{v(x)} \, dx .
</math>
This is evident by noting that 
:<math>f^n(x)=h^{-1}(h(x)+n)~.</math>

For continuous iteration index {{mvar|t}}, then, now written as a subscript, this amounts to Lie's celebrated exponential realization of a continuous group,
:<math>e^{t~\frac{\partial ~~}{\partial h(x)}} g(x)= g(h^{-1}(h(x )+t))= g(f_t(x)).</math>
The initial flow velocity {{mvar|v}} suffices to determine the entire flow, given this exponential realization which automatically provides the  general solution to the ''translation functional equation'',<ref  name="acz">Aczel, J. (2006), ''Lectures on Functional Equations and Their Applications'' (Dover Books on Mathematics, 2006), Ch. 6, {{ISBN|978-0486445236}}.</ref>  
:<math>f_t(f_\tau (x))=f_{t+\tau} (x)  ~.</math>

==See also==
{{Div col|colwidth=15em}}
* [[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]]
* [[Böttcher's equation]]
* [[Infinite compositions of analytic functions]]
* [[Flow (mathematics)]]
* [[Tetration]]
* [[Functional equation]]
{{div col end}}

==Notes==
{{Reflist|group="nb"|refs=
<ref group="nb" name="NB_Rucker">[[Alfred Pringsheim]]'s and [[Jules Molk]]'s (1907) notation {{math|{{i sup|''n''}}''f''(''x'')}} to denote [[function composition]]s must not be confused with [[Rudolf von Bitter Rucker]]'s (1982) [[Rudy Rucker notation|notation]] {{math|{{i sup|''n''}}''x''}}, introduced by Hans Maurer (1901) and [[Reuben Louis Goodstein]] (1947) for [[tetration]], or with [[David Patterson Ellerman]]'s (1995) {{math|{{i sup|''n''}}''x''}} pre-superscript notation for [[nth root|root]]s.<!-- See {{cite book |title=Intellectual Trespassing as a Way of Life: Essays in Philosophy, Economics, and Mathematics |chapter=Chapter 12: Parallel Addition, Series-Parallel Duality, and Financial Mathematics: Series Chauvinsism |series=G – Reference, Information and Interdisciplinary Subjects Series |work=The worldly philosophy: studies in intersection of philosophy and economics |author-first=David Patterson |author-last=Ellerman |author-link=David Patterson Ellerman |edition=illustrated |publisher=[[Rowman & Littlefield Publishers, Inc.]] |date=1995-03-21 |isbn=0-8476-7932-2 |pages=237–268 [239] |url=http://www.ellerman.org/wp-content/uploads/2012/12/IntellectualTrespassingBook.pdf |chapter-url=https://books.google.com/books?id=NgJqXXk7zAAC&pg=PA237 |access-date=2019-08-09 |url-status=live |archive-url=https://web.archive.org/web/20160305012729/http://www.ellerman.org/wp-content/uploads/2012/12/IntellectualTrespassingBook.pdf |archive-date=2016-03-05 |quote=}} [https://web.archive.org/web/20150917191423/http://www.ellerman.org/Davids-Stuff/Maths/sp_math.doc] (271 pages) --><!-- {{cite web |title=Introduction to Series-Parallel Duality |author-first=David Patterson |author-last=Ellerman |author-link=David Patterson Ellerman |publisher=[[University of California at Riverside]] |date=May 2004 |orig-year=1995-03-21 |citeseerx=10.1.1.90.3666 |url=http://www.ellerman.org/wp-content/uploads/2012/12/Series-Parallel-Duality.CV_.pdf |access-date=2019-08-09 |url-status=live |archive-url=https://web.archive.org/web/20190810011716/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&rep=rep1&type=pdf |archive-date=2019-08-10}} [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&rep=rep1&type=pdf] (24 pages) --></ref>
}}

==References==
{{Reflist|refs=
<ref name="Cajori_1929">{{cite book |author-first=Florian |author-last=Cajori |author-link=Florian Cajori |title=A History of Mathematical Notations |chapter=§472. The power of a logarithm / §473. Iterated logarithms / §533. John Herschel's notation for inverse functions / §535. Persistence of rival notations for inverse functions / §537. Powers of trigonometric functions |volume=2 |orig-year=March 1929 |publisher=[[Open court publishing company]] |location=Chicago, USA |date=1952 |edition=3rd corrected printing of 1929 issue, 2nd |pages=108, 176–179, 336, 346 |isbn=978-1-60206-714-1 |url=https://books.google.com/books?id=bT5suOONXlgC |access-date=2016-01-18 |quote=[…] §473. ''Iterated logarithms'' […] We note here the symbolism used by [[Alfred Pringsheim|Pringsheim]] and [[Jules Molk|Molk]] in their joint ''Encyclopédie'' article: "<sup>2</sup>log<sub>''b''</sub>&thinsp;''a'' = log<sub>''b''</sub> (log<sub>''b''</sub>&thinsp;''a''), …, <sup>''k''+1</sup>log<sub>''b''</sub>&thinsp;''a'' = log<sub>''b''</sub> (<sup>''k''</sup>log<sub>''b''</sub>&thinsp;''a'')."{{citeref|Pringsheim|Molk|1907|a<!-- [10] -->}} […] §533. ''[[John Frederick William Herschel|John Herschel]]'s notation for inverse functions,'' sin<sup>&minus;1</sup>&thinsp;''x'', tan<sup>&minus;1</sup>&thinsp;''x'', etc., was published by him in the ''[[Philosophical Transactions of London]]'', for the year 1813. He says ({{citeref|Herschel|1813|p.&nbsp;10|style=plain}}): "This notation cos.<sup>&minus;1</sup>&thinsp;''e'' must not be understood to signify 1/cos.&nbsp;''e'', but what is usually written thus, arc&thinsp;(cos.=''e'')." He admits that some authors use cos.<sup>''m''</sup>&thinsp;''A'' for (cos.&thinsp;''A'')<sup>''m''</sup>, but he justifies his own notation by pointing out that since ''d''<sup>2</sup>&thinsp;''x'', Δ<sup>3</sup>&thinsp;''x'', Σ<sup>2</sup>&thinsp;''x'' mean ''dd''&thinsp;''x'', ΔΔΔ&thinsp;''x'', ΣΣ&thinsp;''x'', we ought to write sin.<sup>2</sup>&thinsp;''x'' for sin.&thinsp;sin.&thinsp;''x'', log.<sup>3</sup>&thinsp;''x'' for log.&thinsp;log.&thinsp;log.&thinsp;''x''. Just as we write ''d''<sup>&minus;''n''</sup>&thinsp;V=∫<sup>''n''</sup>&thinsp;V, we may write similarly sin.<sup>&minus;1</sup>&thinsp;''x''=arc&thinsp;(sin.=''x''), log.<sup>&minus;1</sup>&thinsp;''x''.=c<sup>''x''</sup>. Some years later Herschel explained that in 1813 he used ''f''<sup>''n''</sup>(''x''), ''f''<sup>&minus;''n''</sup>(''x''), sin.<sup>&minus;1</sup>&thinsp;''x'', etc., "as he then supposed for the first time. The work of a German Analyst, [[Hans Heinrich Bürmann|Burmann]], has, however, within these few months come to his knowledge, in which the same is explained at a considerably earlier date. He[Burmann], however, does not seem to have noticed the convenience of applying this idea to the inverse functions tan<sup>&minus;1</sup>, etc., nor does he appear at all aware of the inverse calculus of functions to which it gives rise." Herschel adds, "The symmetry of this notation and above all the new and most extensive views it opens of the nature of analytical operations seem to authorize its universal adoption."{{citeref|Herschel|1820|b<!-- [4] -->}} […] §535. ''Persistence of rival notations for inverse function.''&mdash; […] The use of Herschel's notation underwent a slight change in [[Benjamin Peirce]]'s books, to remove the chief objection to them; Peirce wrote: "cos<sup>[&minus;1]</sup>&thinsp;''x''," "log<sup>[&minus;1]</sup>&thinsp;''x''."{{citeref|Peirce|1852|c<!-- [1] -->}} […] §537. ''Powers of trigonometric functions.''&mdash;Three principal notations have been used to denote, say, the square of sin&thinsp;''x'', namely, (sin&thinsp;''x'')<sup>2</sup>, sin&thinsp;''x''<sup>2</sup>, sin<sup>2</sup>&thinsp;''x''. The prevailing notation at present is sin<sup>2</sup>&thinsp;''x'', though the first is least likely to be misinterpreted. In the case of sin<sup>2</sup>&thinsp;''x'' two interpretations suggest themselves; first, sin&thinsp;''x'' &sdot; sin&thinsp;''x''; second,{{citeref|Peano|1903|d<!-- [8] -->}} sin&thinsp;(sin&thinsp;''x''). As functions of the last type do not ordinarily present themselves, the danger of misinterpretation is very much less than in case of log<sup>2</sup>&thinsp;''x'', where log&thinsp;''x'' &sdot; log&thinsp;''x'' and log&thinsp;(log&thinsp;''x'') are of frequent occurrence in analysis. […] The notation sin<sup>''n''</sup>&thinsp;''x'' for (sin&thinsp;''x'')<sup>''n''</sup> has been widely used and is now the prevailing one. […]}} (xviii+367+1 pages including 1 addenda page) (NB. ISBN and link for reprint of 2nd edition by Cosimo, Inc., New York, USA, 2013.)</ref>
<ref name="Herschel_1813">{{cite journal |author-first=John Frederick William |author-last=Herschel |author-link=John Frederick William Herschel |title=On a Remarkable Application of Cotes's Theorem |journal=[[Philosophical Transactions of the Royal Society of London]] |publisher=[[Royal Society of London]], printed by W. Bulmer and Co., Cleveland-Row, St. James's, sold by G. and W. Nicol, Pall-Mall |location=London |volume=103 |number=Part 1 |date=1813 |orig-year=1812-11-12 |jstor=107384 |pages=8–26 [10]|doi=10.1098/rstl.1813.0005 |s2cid=118124706 |doi-access=free }}</ref>
<ref name="Herschel_1820">{{cite book |author-first=John Frederick William |author-last=Herschel |author-link=John Frederick William Herschel |title=A Collection of Examples of the Applications of the Calculus of Finite Differences |chapter=Part III. Section I. Examples of the Direct Method of Differences |location=Cambridge, UK |publisher=Printed by J. Smith, sold by J. Deighton & sons |date=1820 |pages=1–13 [5–6] |chapter-url=https://books.google.com/books?id=PWcSAAAAIAAJ&pg=PA5 |access-date=2020-08-04 |url-status=live |archive-url=https://web.archive.org/web/20200804031020/https://books.google.de/books?hl=de&id=PWcSAAAAIAAJ&jtp=5 |archive-date=2020-08-04}} [https://archive.org/details/acollectionexam00lacrgoog] (NB. Inhere, Herschel refers to his {{citeref|Herschel|1813|1813 work|style=plain}} and mentions [[Hans Heinrich Bürmann]]'s older work.)</ref>
<ref name="Peirce_1852">{{cite book |author-first=Benjamin |author-last=Peirce |author-link=Benjamin Peirce |title=Curves, Functions and Forces |volume=I |edition=new |location=Boston, USA |date=1852 |page=203}}</ref>
<ref name="Peano_1903">{{cite book |author-first=Giuseppe |author-last=Peano |author-link=Giuseppe Peano |title=Formulaire mathématique |language=fr |volume=IV |date=1903 |page=229}}</ref>
<ref name="Pringsheim-Molk_1907">{{cite book |author-first1=Alfred |author-last1=Pringsheim |author-link1=Alfred Pringsheim |author-first2=Jules |author-last2=Molk |author-link2=Jules Molk |title=Encyclopédie des sciences mathématiques pures et appliquées |language=fr |id=Part I |volume=I |date=1907 |page=195}}</ref>
}}

==External links==
* {{cite web |url=https://www.researchgate.net/publication/362010262 |author-link=John Gill (climber) |first=John |last=Gill |title=A Primer on the Elementary Theory of Infinite Compositions of Complex Functions |publisher=Colorado State University |date=January 2017 }}

[[Category:Dynamical systems]]
[[Category:Fractals]]
[[Category:Sequences and series]]
[[Category:Fixed points (mathematics)]]
[[Category:Functions and mappings]]
[[Category:Functional equations]]