en>Ahmadalkhairy at 23:22, 2 January 2015

2015-01-02T23:22:19Z

en>R'n'B: Fix links to disambiguation page Polarization

2010-01-05T16:24:44Z

Fix links to disambiguation page Polarization

New page

In [[mathematics]], an '''iterated function''' is a function which is [[function composition|composed]] with itself, possibly ''[[ad infinitum]]'', in a process called [[iteration]]. In this process, starting from some initial number, the result of applying a given function is fed again in the function as input, and this process is repeated. The sequence of functions that is obtained from this process is called the ''splinter'' or the discrete part of the iteration [[Orbit (dynamics)|orbit]].

Iterated functions are objects of study in [[computer science]], [[fractals]], [[dynamical system]]s, mathematics and [[renormalization group]] physics.

==Definition==
The formal definition of an iterated function on a [[Set (mathematics)|set]] ''X'' follows.

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

Define {{math| ''f'' ''n''}} as the ''n''-th iterate of {{mvar|''f''}}, where ''n'' is a non-negative integer, by:

:: <math>f^0 ~ \stackrel{\mathrm{def}}{=} ~ \operatorname{id}_X\,</math>
and
:: <math>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''○''g''}} denotes [[function composition]]. That is,
::{{math|(''f''○''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]] of the function {{mvar|''f''}} (the latter is used in trigonometry), some mathematicians choose to write {{math|''f'' °''n''}} for the ''n''-th iterate of the function {{mvar|''f''}}.

==Abelian property and Iteration sequences==
In general, the following identity holds for all non-negative integers {{mvar|m}} and {{mvar|n}},

: <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|''a''''m''''a''''n'' {{=}} ''a''''m''+''n''}}, i.e. the special case {{math|''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]]. On a logarithmic scale, this reduces to the '''nesting property''' of [[Chebyshev polynomials]], {{math|''T''''m''(''T''''n''(''x'')){{=}}''T''''m n''(''x'')}}, since {{math|''T''''n''(''x'') {{=}} cos(''n'' arcos(''x'' ))}}.

The relation {{math|(''f'' ''m'' )''n''(''x'') {{=}} (''f'' ''n'' )''m''(''x'') {{=}} ''f'' ''mn''(''x'')}} also holds, analogous to the property of exponentiation that {{math|(''a''''m'' )''n'' {{=}}(''a''''n'' )''m'' {{=}} ''a''''mn''}}.

The sequence of functions {{math|''f'' ''n''}} is called a '''Picard sequence''',<ref>{{cite book |title=Functional equations in a single variable |last=Kuczma |first=Marek| authorlink=Marek Kuczma|series=Monografie Matematyczne |year=1968 |publisher=PWN – Polish Scientific Publishers |location=Warszawa}}</ref><ref>{{cite book|title=Iterative Functional Equations| last=Kuczma| first=M., Choczewski B., and Ger, R. |year=1990|publisher=Cambridge University Press|ISBN= 0-521-35561-3}}</ref> named after [[Charles Émile Picard]].

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|''f'' ''n'' (''x'') {{=}} ''f'' ''n''+''m'' (''x'')}} for some integer {{mvar|m}}, 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 ''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]].<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'''.

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.

==Fractional iterates and flows, and negative iterates==

In some instances, 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|''g''(''g''(''x'')) {{=}} ''f''(''x'')}}. This function {{math|''g''(''x'')}} can be written using the index notation as {{math|''f'' ½(''x'')}} . Similarly, {{math|''f'' ⅓(''x'')}} is the function defined such that {{math|''f''⅓(''f''⅓(''f''⅓(''x''))) {{=}} ''f''(''x'')}}, while {{math|''f'' ⅔(''x'')}} may be defined equal to {{math|''f'' ⅓(''f'' ⅓(''x''))}}, and so forth, all based on the principle, mentioned earlier, that {{math|''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]].

In such cases, one refers to the system as a [[flow (mathematics)|flow]], specified by [[Schröder's equation]]. (cf. Section on [[#Conjugacy|conjugacy]] below.)

Negative iterates correspond to function inverses and their compositions. For example, {{math|''f'' −1(''x'')}} is the normal inverse of {{mvar|f}}, while {{math|''f'' −2(''x'')}} is the inverse composed with itself, i.e. {{math|''f'' −2(''x'') {{=}} ''f'' −1(''f'' −1(''x''))}}. Fractional negative iterates are defined analogously to fractional positive ones; for example, {{math|''f'' −½(''x'')}} is defined such that {{math|''f'' − ½(''f'' −½(''x'')) {{=}} ''f'' −1(''x'')}}, or, equivalently, such that {{math|''f'' −½(''f'' ½(''x'')) {{=}} ''f'' 0(''x'') {{=}} ''x''}}.

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

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

'''(2)''' Define {{math|''f n(a)''{{=}}''a''}} for all ''n'' belonging to the reals. This, in some ways, is the most natural extra condition to place upon the fractional iterates.

'''(3)''' Expand {{math|''f n(x)''}} around the fixed point ''a'' as a [[Taylor series]],
:<math>
f^n(x) = f^n(a) + (x-a)\frac{d}{dx}f^n(x)|_{x=a} + \frac{(x-a)^2}{2!}\frac{d^2}{dx^2}f^n(x)|_{x=a} +\cdots
</math>

'''(4)''' Expand out
:<math>
f^n\left(x\right) = f^n(a) + (x-a) f'(a)f'(f(a))f'(f^2(a))\cdots f'(f^{n-1}(a)) + \cdots
</math>

'''(5)''' Substitute in for {{math|''f k(a)''{{=}} ''a''}}, for any ''k'',
:<math>
f^n\left(x\right) = a + (x-a) f'(a)^{n} + \frac{(x-a)^2}{2!}(f''(a)f'(a)^{n-1})\left(1+f'(a)+\cdots+f'(a)^{n-1} \right)+\cdots
</math>

'''(6)''' Make use of the [[geometric progression]] to simplify terms,
:<math>
f^n\left(x\right) = a + (x-a) f'(a)^{n} + \frac{(x-a)^2}{2!}(f''(a)f'(a)^{n-1})\frac{f'(a)^n-1}{f'(a)-1}+\cdots
</math>

'''(6b)''' There is a special case when {{math|''f '(a)''{{=}}1}},
:<math>
f^n\left(x\right) = x + \frac{(x-a)^2}{2!}(n f''(a))+ \frac{(x-a)^3}{3!}\left(\frac{3}{2}n(n-1) f''(a)^2 + n f'''(a)\right)+\cdots
</math>

'''(7)''' When ''n'' is not an integer, make use of the power formula {{math| ''y'' ''n'' {{=}} exp(''n'' ln(''y''))}}.

This can be carried on indefinitely, although inefficiently, as the latter terms become increasingly complicated.

A more systematic procedure is outlined in the following section on '''Conjugacy'''.

===Example 1===
For example, setting {{math|''f''(''x'') {{=}} ''Cx''+''D''}} gives the fixed point {{math|''a'' {{=}} ''D''/(1-''C'')}}, so the above formula terminates to just
:<math>
f^n(x) = \frac{D}{1-C} + (x-\frac{D}{1-C})C^n = C^n x + \frac{1-C^n}{1-C}D ~,
</math>
which is trivial to check.

===Example 2===
Find the value of <math>\sqrt{2}^{ \sqrt{2}^{\sqrt{2}^{\cdots}} }</math> where this is done ''n'' times (and possibly the interpolated values when ''n'' is not an integer). We have {{math|''f''(''x''){{=}}{{sqrt|2}}''x''}}. A fixed point is {{math|''a''{{=}}''f''(2){{=}}2}}.

So set ''x''=1 and {{math|''f'' n (1)}} expanded around the fixed point value of 2 is then an infinite series,
:<math>
\sqrt{2}^{ \sqrt{2}^{\sqrt{2}^{\cdots}} } = f^n(1) = 2 - (\ln 2)^n + \frac{(\ln 2)^{n+1}((\ln 2)^n-1)}{4(\ln 2-1)} - \cdots
</math>
which, taking just the first three terms, is correct to the first decimal place when ''n'' is positive—cf. [[Tetration]]: {{math|''f'' n(1) {{=}} n{{sqrt|2}} }}. (Using the other fixed point {{math|''a'' {{=}} ''f''(4) {{=}} 4}} causes the series to diverge.)

===Example 3===
For {{math| ''n'' {{=}} −1}}, the series computes the inverse function, {{math| 2 ln''x''/ln2}}.

===Example 4===
With the function {{math|''f(x)'' {{=}} ''x''''b''}}, expand around the fixed point 1 to get the series
: <math>
f^n(x) = 1 + b^n(x-1) + \frac{1}{2!}b^{n}(b^n-1)(x-1)^2 + \frac{1}{3!}b^n (b^n-1)(b^n-2)(x-1)^3 + \cdots ~,
</math>
which is simply the Taylor series of ''x''(''b''''n'' ) expanded around 1.

==Conjugacy==

If {{mvar|f}} and {{mvar|g}} are two iterated functions, and there exists a [[homeomorphism]] {{mvar|h}} such that {{math| ''g'' {{=}} ''h''−1 ○ ''f'' ○ ''h'' }}, then {{mvar|f}} and {{mvar|g}} are said to be [[topologically conjugate]].

Clearly, topological conjugacy is preserved under iteration, as {{math|''g''n{{=}}''h''−1 ○ ''f'' n ○ ''h''}}. Thus, if one can solve for one iterated function system, one also has solutions for all topologically conjugate systems. For example, the [[tent map]] is topologically conjugate to the [[logistic map]]. As a special case, taking {{math|''f''(''x'') {{=}} ''x''+1}}, one has the iteration of {{math|''g''(''x'') {{=}} ''h''−1(''h''(''x'')+1)}} as {{math|''g''''n''(''x'') {{=}} ''h''−1(''h''(''x'') + ''n'')}}, for any function {{mvar|h}}.

Making the substitution {{math|''x'' {{=}} ''h''−1(''y'') {{=}} ''ϕ''(''y'')}} yields {{math|''g''(''ϕ''(''y'')) {{=}} ''ϕ''(''y''+1)}}, a form known as the [[Abel equation]].

Even in the absence of a strict homeomorphism, near a fixed point, here taken to be at ''x'' = 0, ''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''] '''14''', 197-238.</ref> [[Schröder's equation]] for a function {{mvar|Ψ}}, which makes {{math|''f''(''x'')}} locally conjugate to a mere dilation, {{math|''g''(''x'') {{=}} ''f'' '(0) ''x''}}, that is {{math|''f''(''x'') {{=}} ''Ψ''−1(''f'' '(0) ''Ψ''(''x''))}}.

Thus, its iteration orbit, or flow, under suitable provisions (e.g., {{math|''f'' '(0) ≠ 1}}), amounts to the conjugate of the orbit of the monomial,
:{{math|''Ψ''−1(''f'' '(0)''n'' ''Ψ''(''x''))}},
where {{mvar|n}} in this expression serves as a plain exponent: functional iteration has been reduced to multiplication! Here, however, the exponent {{mvar|n}} no longer needs be integer or positive, and is a continuous "time" of evolution for the full orbit:<ref>{{cite journal |last=Curtright |first=T.L. |authorlink=Thomas Curtright|coauthors=[[Cosmas Zachos|Zachos, C.K.]]| year=2009|title=Evolution Profiles and Functional Equations |journal=Journal of Physics A |volume=42|issue=48 |pages=485208|doi=10.1088/1751-8113/42/48/485208}}</ref> the [[monoid]] of the Picard sequence (cf. [[transformation semigroup]]) has generalized to a full [[continuous group]].<ref>For explicit instance, example 2 above amounts to just {{math|''f'' n(''x'') {{=}} ''Ψ''−1((ln2)n ''Ψ''(''x''))}}, for ''any n'', not necessarily integer, where {{mvar|''Ψ''}} is the solution of the relevant [[Schröder's equation]], {{math|''Ψ''({{sqrt|2}}''x''){{=}} ln2 ''Ψ''(''x'')}}. This solution is also the infinite ''m'' limit of {{math|(''f'' m(''x'') −2)/(ln2)m}}.</ref>

This method (perturbative determination of the principal [[eigenfunction]] {{mvar|Ψ}}, cf. [[Carleman matrix]]) is equivalent to the algorithm of the preceding section, albeit, in practice, more powerful and systematic.

==Markov chains==

If the function is linear and 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==

There are [[List of chaotic maps|many chaotic maps]].
Famous iterated functions include the [[Mandelbrot set]] and [[Iterated function systems]].

[[Ernst Schröder]],<ref name="schr">{{cite journal |last=Schröder |first=Ernst |authorlink=Ernst Schröder |year=1870 |title=Ueber iterirte Functionen|journal=Math. Ann. |volume=3 |issue= 2|pages=296–322 | doi=10.1007/BF01443992 }}</ref> in 1870, worked out special cases of the [[logistic map]], such as the chaotic case {{math|''f''(''x'') {{=}} 4''x''(1−''x'')}}, so that {{math|''Ψ''(''x'') {{=}} arcsin2(√''x'')}}, hence {{math|''f'' ''n''(''x'') {{=}} sin2(2''n'' arcsin(√''x''))}}.

A nonchaotic case Schröder also illustrated with his method, {{math|''f''(''x'') {{=}} 2''x''(1 − ''x'')}}, yielded {{math|''Ψ''(''x'') {{=}} −½ ln(1−2''x'')}}, and hence {{math|''f'' ''n''(''x'') {{=}} −½((1−2''x'')2''n''−1)}}.

If {{mvar|''f''}} is the [[group action|action]] of a group element on a set, then the iterated function corresponds to a [[free group]].

Most functions do not have explicit general closed-form expressions for the ''n''-th iterate. The table below lists some<ref name="schr"/> that do. Note that all these expressions "work" for non-integer and negative ''n'', as well as positive integer ''n''.

{| class=wikitable width=100%
!<math>f(x)</math>
!<math>f^n(x)</math>
|-
|<math>x + b</math>
|<math>x + nb</math>
|-
|<math>ax + b \ (a \ne 1)</math>
|<math>a^nx + \frac{a^n - 1}{a - 1}b</math>
|-
|<math>ax^b \ (b \ne 1)</math>
|<math>a^{\frac{b^n - 1}{b - 1}}x^{b^n}</math>
|-
|<math>ax^2 + bx + \frac{b^2 - 2b}{4a}</math> (see note) 
|<math>\frac{2\alpha^{2^n} - b}{2a}</math> 
where:
:<math>\alpha = \frac{2ax + b}{2}</math>
|-
|<math>ax^2 + bx + \frac{b^2 - 2b - 8}{4a}</math> (see note) 
|<math>\frac{2\alpha^{2^n} + 2\alpha^{-2^n} - b}{2a}</math> 
where:
:<math>\alpha = \frac{2ax + b \pm \sqrt{(2ax + b)^2 - 16}}{4}</math>
|-
|<math>\frac{ax + b}{cx + d}</math>
|<math>\frac{a}{c} + \frac{bc - ad}{c} \left [ \frac{(cx - a + \alpha)\alpha^{n - 1} - (cx - a + \beta)\beta^{n - 1}}{(cx - a + \alpha)\alpha^{n} - (cx - a + \beta)\beta^{n}} \right ]</math> 
where:
:<math>\alpha = \frac{a + d + \sqrt{(a - d)^2 + 4bc}}{2}</math>
:<math>\beta = \frac{a + d - \sqrt{(a - d)^2 + 4bc}}{2}</math>
|-
|<math>\sqrt{x^2 + b}</math>
|<math>\sqrt{x^2 + bn}</math>
|-
|<math>\sqrt{ax^2 + b} \ (a \ne 1)</math>
|<math>\sqrt{a^nx^2 + \frac{a^n - 1}{a - 1}b}</math>
|}
Note: these two special cases of {{math|''ax''2 + ''bx'' + ''c''}} are the only cases that have a closed-form solution. Choosing ''b'' = 2 and ''b'' = 4, respectively, reduces them to the nonchaotic and chaotic special cases above.

Some of these examples are related among themselves by simple conjugacies. A few further examples, essentially amounting to simple conjugacies of Schröder's examples can be found in ref.<ref>{{cite doi|10.1016/0378-4371(85)90048-2|noedit}}</ref>

==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 [[recursion (computer science)|recursive functions]], which in turn anchor the study of such broad topics as [[lambda calculus]], or narrower ones, such as the [[denotational semantics]] of computer programs.

==Definitions in terms of Iterated Functions==
Two important [[functional (mathematics)|functionals]] can be defined in terms of iterated functions. These are [[Summation]]:

:<math>
\left\{b+1,\sum_{i=a}^b g(i)\right\} \equiv \left( \{i,x\} \rightarrow \{ i+1 ,x+g(i) \}\right)^{b-a+1} \{a,0\}
</math>

and the equivalent product:

:<math>
\left\{b+1,\prod_{i=a}^b g(i)\right\} \equiv \left( \{i,x\} \rightarrow \{ i+1 ,x g(i) \}\right)^{b-a+1} \{a,1\}
</math>

==Lie's data transport equation==
Iterated functions crop up in the series expansion of the combined functions, such as ''g''(''f''(''x'')). Given the [[Koenigs_function#Structure_of_univalent_semigroups|iteration velocity]], or [[beta function (physics)]], <math>v(x)=\partial f^n(x) / \partial n |_{n=0}</math> for the ''n''th iterate of the function ''f'', we have<ref>{{cite doi|10.1307/mmj/1029002009|noedit}} {{cite doi|10.1088/1751-8113/43/44/445101|noedit}}</ref>

:<math>
g(f(x)) = \exp\left[ v(x) \dfrac{\partial}{\partial x} \right] g(x).
</math>
For example, for rigid advection, if ''f''(''x'') = ''x'' + ''a'', then ''v''(''x'') = ''a''. Consequently ''g''(''x'' + ''a'') = exp(''a'' ∂/∂''x'') ''g''(''x''), a plain [[shift operator]].

One may further find ''f''(''x'') given ''v''(''x''), through the [[Abel equation]] discussed above,
:<math>
f(x) = h^{-1}(h(x)+1) ,
</math>
where
:<math>
h(x) = \int{\frac{1}{v(x)}dx} .
</math>
This is evident by noting that <math>f^n(x)=h^{-1}(h(x)+n)</math>.

==See also==
{{Col-begin}}
{{Col-1-of-2}}
* [[Irrational rotation]]
* [[Iterated function system]]
* [[Iterative method]]
* [[Rotation number]]
* [[Sarkovskii's theorem]]
{{Col-2-of-2}}
* [[Recurrence relation]]
* [[Schröder's equation]]
* [[Functional square root]]
* [[Superfunction]]
* [[Infinite compositions of analytic functions]]
{{col-end}}

==References==
{{Reflist}}

[[Category:Dynamical systems]]
[[Category:Fractals]]
[[Category:Sequences and series]]
[[Category:Fixed points (mathematics)]]
[[Category:Functions and mappings]]
[[Category:Functional equations]]

Gravitational plane wave - Revision history

en>Ahmadalkhairy at 23:22, 2 January 2015

en>R'n'B: Fix links to disambiguation page Polarization