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:迭代函数]]