Iterated function: Difference between revisions

Revision as of 17:49, 7 January 2024

Revision as of 21:45, 7 January 2024

Line 40:

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

If {{math|1=''f'' ^''n'' (''x'') = ''f'' ^''n''+''m'' (''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.

Line 61:

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'''⁺→'''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'')}} doesn'tdoes 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>

In such cases, one refers to the system as a [[flow (mathematics)|flow]]. (cf. Sectionsection 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''⁻¹(''x'')}} is the normal inverse of {{mvar|f}}, while {{math|''f''⁻²(''x'')}} is the inverse composed with itself, i.e. {{math|1=''f''⁻²(''x'') = ''f''⁻¹(''f''⁻¹(''x''))}}. Fractional negative iterates are defined analogously to fractional positive ones; for example, {{math|''f''^−1/2(''x'')}} is defined such that {{math|1=''f''^−1/2(''f''^−1/2(''x'')) = ''f''⁻¹(''x'')}}, or, equivalently, such that {{math|1=''f''^−1/2(''f''^1/2(''x'')) = ''f''⁰(''x'') = ''x''}}.