Iterated function: Difference between revisions

Revision as of 13:35, 18 January 2024

Latest revision as of 19:04, 30 July 2025

(19 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Result of repeatedly applying a mathematical function}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

{{MOS|article|date=July 2025| [[MOS:FORMULA]] - avoid mixing {{tag|math}} and {{tl|math}} in the same expression}}

[[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 a certain number oftwo 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.

[[File:An iterated direct similarity yields spirals.svg|thumb|upright=1.8|[[Function composition|Composed]]  with  itself  '''repeatedly''',  [[Similarity (geometry)|similarity]]  {{math|''F''}}<br

/>of [[Similarity (geometry)#Similarity_with_a_center|center]] ''S '' enlarges the smallest [[Regular polygon|'''regular''']] [[pentagon]]<br

/>into successive [[Concentric objects|concentric]] pentagons,  in manner that the outline<br

/>of each one passes through all vertices of the previous pentagon,<br

/>of which it is the [[Image_(mathematics)#Image_of_an_element|image]] under {{math|''F''}}.  If  [[Transformation (function)|transformation]]  {{math|''F''}}<br

/>is  '''iterated'''  indefinitely,   then  ''A ''  and  ''K''   are<br

/>the  starting  points  of  two  infinite  [[spiral]]s.]]

In [[mathematics]], an '''iterated function''' is a function that is obtained by [[function composition|composing]] another function 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 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>}}

Line 21 ⟶ 16:

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

Defining {{math| ''f'' ^''n''}} as the ''n''-th iterate of {{mvar|''f''}} (a notation introduced by [[Hans Heinrich Bürmann]]{{citation needed|date=August 2020|reason=The fact is undisputable, but for historical completeness, let's find Bürmann's original work on this and add here as a citation. It must be dated significantly before 1813 (according to Herschel in 1820 und Cajori in 1929.)}} and [[John Frederick William Herschel]]<!-- in 1813 --><ref name="Herschel_1813"/><ref name="Herschel_1820"/><ref name="Peano_1903"/><ref name="Cajori_1929"/>), 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_''X''}} 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'' ^''n''}} 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'' ^[''n''](''x'')}} was used by [[Benjamin Peirce]]<ref name="Peirce_1852"/><ref name="Cajori_1929"/><ref group="nb">while {{math|''f'' ^(''n'')}} 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"/>

Line 55 ⟶ 50:

==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'''.

Line 70 ⟶ 65:

==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'''⁺→'''R'''⁺, ''f''(''x'') = sin(''x'')}}. The computation of ''f''({{frac|π|6}}) = {{frac|1|2}} = ''g''⁵({{frac|π|6}}) is shown.]]

The notion {{math|''f''{{i sup|1/''n''}}}} must be used with care when the equation {{math|1=''g''^''n''(''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''^1/2(''x'')}} does not denote a unique function, just as numbers have multiple algebraic roots. The issue is quite similar to the expression "[[division by zero#Algebra|0/0]]" in arithmetic. 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''^1/2(''x'')}} . Similarly, {{math|''f''^1/3(''x'')}} is the function defined such that {{math|1=''f''^1/3(''f''^1/3(''f''^1/3(''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''^''m'' ○ ''f''^''n'' = ''f''^{''m'' + ''n''}}}. 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>

Line 80 ⟶ 75:

=== 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_iterationFractional_Iteration }}</ref>

# First determine a fixed point for the function such that {{math|1=''f''(''a'') = ''a''}}.

Line 135 ⟶ 130:

:{{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'') {{=}} Ψ⁻¹(''f'' '(0) Ψ(''x''))}}.

Line 143 ⟶ 138:

[[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, thea sawtooth[[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].)

]]

Line 278 ⟶ 273:

* [[Functional square root]]

* [[Abel function]]

* [[Schröder's equation]]

* [[Böttcher's equation]]

* [[Infinite compositions of analytic functions]]

Line 293 ⟶ 287:

==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: "²log_''b''&thinsp;''a'' = log_''b'' (log_''b''&thinsp;''a''), …, ^''k''+1log_''b''&thinsp;''a'' = log_''b'' (^''k''log_''b''&thinsp;''a'')."{{citeref|Pringsheim|Molk|1907|a<!-- [10] -->}} […] §533. ''[[John Frederick William Herschel|John Herschel]]'s notation for inverse functions,'' sin^&minus;1&thinsp;''x'', tan^&minus;1&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.^&minus;1&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.^''m''&thinsp;''A'' for (cos.&thinsp;''A'')^''m'', but he justifies his own notation by pointing out that since ''d''²&thinsp;''x'', Δ³&thinsp;''x'', Σ²&thinsp;''x'' mean ''dd''&thinsp;''x'', ΔΔΔ&thinsp;''x'', ΣΣ&thinsp;''x'', we ought to write sin.²&thinsp;''x'' for sin.&thinsp;sin.&thinsp;''x'', log.³&thinsp;''x'' for log.&thinsp;log.&thinsp;log.&thinsp;''x''. Just as we write ''d''^&minus;''n''&thinsp;V=∫^''n''&thinsp;V, we may write similarly sin.^&minus;1&thinsp;''x''=arc&thinsp;(sin.=''x''), log.^&minus;1&thinsp;''x''.=c^''x''. Some years later Herschel explained that in 1813 he used ''f''^''n''(''x''), ''f''^&minus;''n''(''x''), sin.^&minus;1&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^&minus;1, 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^[&minus;1]&thinsp;''x''," "log^[&minus;1]&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'')², sin&thinsp;''x''², sin²&thinsp;''x''. The prevailing notation at present is sin²&thinsp;''x'', though the first is least likely to be misinterpreted. In the case of sin²&thinsp;''x'' two interpretations suggest themselves; first, sin&thinsp;''x'' &middotsdot; 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²&thinsp;''x'', where log&thinsp;''x'' &middotsdot; log&thinsp;''x'' and log&thinsp;(log&thinsp;''x'') are of frequent occurrence in analysis. […] The notation sin^''n''&thinsp;''x'' for (sin&thinsp;''x'')^''n'' 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>

Line 301 ⟶ 295:

}}

==External Linkslinks==

* {{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 }}