Iterated function: Difference between revisions

Revision as of 18:23, 27 October 2023

Revision as of 01:02, 21 November 2023

Line 25:

where {{math|id_''X''}} is the [[identity function]] on {{mvar|''X''}} and {{math|''f'' <math>\circ</math> ''g''}} denotes [[function composition]]. That is,

:{{math|(''f'' {{text| {{math| <math>\circ</math> }} }} ''g'')(''x'') {{=}} ''f'' (''g''(''x''))}},

always [[associative]].

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 35:

: <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''^''m''''a''^''n'' = ''a''^{''m'' + ''n''}}}, i.e. the special case {{math|1=''f''(''x'') = ''ax''}}.

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''_''m''(''T''_''n''(''x'')) = ''T''_{''m n''}(''x'')}}, since {{math|1=''T''_''n''(''x'') = cos(''n'' arccos(''x''))}}.

Line 49 ⟶ 50:

==Fixed points==

If {{math|1=''f''( ''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.