Iterated function
1448702
204268205
2008-04-08T18:27:32Z
Linas
159886
add a sentence about recursive functions in comp sci
In [[mathematics]], '''iterated functions''' are the objects of deep study in [[computer science]], [[fractals]] and [[dynamical system]]s. An iterated function is a function which is [[function composition|composed]] with itself, repeatedly, a process called [[iteration]].
==Definition==
The formal definition of an iterated function on a [[set]] <math>X</math> follows:
Let <math>X</math> be a set and <math>f:X\rightarrow X</math>
be a [[function (mathematics)|function]]. Define the <math>n</math>'th iterate
<math>f^n</math> of <math>f</math> by <math>f^0=\operatorname{id}_X</math>
where <math>\operatorname{id}_X</math> is the [[identity function]] on <math>X</math>, and <math>f^{n+1} = f \circ f^n</math>.
In the above, <math>f \circ g</math> denotes [[function composition]]; that is, <math>(f \circ g)(x)=f(g(x))</math>.
==Creating sequences from iteration==
The sequence of functions <math>f^n</math> is called a '''Picard sequence''', named after [[Charles Émile Picard]]. For a given <math>x</math> in <math>X</math>, the [[sequence]] of values <math>f^n(x)</math> is called the [[orbit (dynamics)|'''orbit''']] of <math>x</math>.
If <math>f^n(x) = f^{n+m}(x)</math> for some integer <math>m</math>, the orbit is called a '''periodic orbit'''. The smallest such value of <math>m</math> for a given <math>x</math> is called the '''period of the orbit'''. The point <math>x</math> itself is called a [[periodic point]].
==Fixed points==
If m=1, that is, if ''f''(''x'') = ''x'' for some ''x'' in ''X'', then ''x'' is called a [[fixed point (mathematics)|'''fixed point''']] of the iterated sequence. The set of fixed points is often denoted as '''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]]. 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]].
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 behaviour of small [[neighborhood]]s under iteration.
Other limiting behaviours are possible; for example, [[wandering point]]s are points that move away, and never come back even close to where they started.
==Flows==
The idea of iteration can be generalized so that the iteration count ''n'' becomes a [[continuous]] parameter; in this case, such a system is called a [[flow (mathematics)|flow]].
==Conjugacy==
If ''f'' and ''g'' are two iterated functions, and there exists a [[homeomorphism]] ''h'' such that <math>g=h^{-1} \circ f \circ h</math>, then ''f'' and ''g'' are said to be [[topologically conjugate]]. Clearly, topological conjugacy is preserved under iteration, as one has that <math>g^n=h^{-1}\circ f^n \circ h</math>, so that if one can solve one iterated function system, one has solutions for all topologically conjugate systems. For example, the [[tent map]] is topologically conjugate to the [[logistic map]].
==Markov chains==
If the function 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==
Famous iterated functions include the [[Mandelbrot set]] and [[Iterated function systems]].
If ''f'' is the [[group action|action]] of a group element on a set, then the iterated function corresponds to a [[free group]].
==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 [[recursive function]]s, which in turn anchor the study of such broad topics as [[lambda calculus]], or narrower onces, such as the [[denotational semantics]] of computer programs.
==See also==
* [[Irrational rotation]]
* [[Rotation number]]
* [[Sarkovskii's theorem]]
==References==
* Vasile I. Istratescu, ''Fixed Point Theory, An Introduction'', D.Reidel, Holland (1981). ISBN 90-277-1224-7
[[Category:Dynamical systems]]
[[Category:Fractals]]
[[Category:Sequences and series]]
[[Category:Fixed points]]
[[Category:Functions and mappings]]
[[es:Función iterada]]
[[pt:Função iterada]]
[[zh:迭代函数]]