Iterated function

Iterated function

In mathematics, iterated functions are the objects of deep study in computer science, fractals and dynamical systems. An iterated function is a function which is composed with itself, repeatedly, a process called iteration.

Definition

The formal definition of an iterated function on a set X follows:

Let X be a set and f:X ightarrow X be a function. Define the n'th iterate f^n of f by f^0=operatorname{id}_X where operatorname{id}_X is the identity function on X, and f^{n+1} = f circ f^n.

In the above, f circ g denotes function composition; that is, (f circ g)(x)=f(g(x)).

Creating sequences from iteration

The sequence of functions f^n is called a Picard sequence, named after Charles Émile Picard. For a given x in X, the sequence of values f^n(x) is called the orbit of x.

If f^n(x) = f^{n+m}(x) for some integer m, the orbit is called a periodic orbit. The smallest such value of m for a given x is called the period of the orbit. The point x 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 of the iterated sequence. The set of fixed points is often denoted as Fix("f"). There exist a number of fixed-point theorems 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 points 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 sets and unstable sets, according to the behaviour of small neighborhoods under iteration.

Other limiting behaviours are possible; for example, wandering points 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.

Conjugacy

If "f" and "g" are two iterated functions, and there exists a homeomorphism "h" such that g=h^{-1} circ f circ h, then "f" and "g" are said to be topologically conjugate. Clearly, topological conjugacy is preserved under iteration, as one has that g^n=h^{-1}circ f^n circ h, 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 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 operators.

In computer science

In computer science, iterated functions occur as a special case of recursive functions, which in turn anchor the study of such broad topics as lambda calculus, or narrower onces, such as the denotational semantics of computer programs.

ee also

* Irrational rotation
* Iterated function system
* Rotation number
* Sarkovskii's theorem

References

* Vasile I. Istratescu, "Fixed Point Theory, An Introduction", D.Reidel, Holland (1981). ISBN 90-277-1224-7


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Iterated function system — In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self similar.IFS fractals as they are normally called can be of any number of dimensions, but are commonly computed… …   Wikipedia

  • Iterated logarithm — In computer science, the iterated logarithm of n , written log* n (usually read log star ), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition is… …   Wikipedia

  • Iterated binary operation — In mathematics, an iterated binary operation is an extension of a binary operation on a set S to a function on finite sequences of elements of S through repeated application. Common examples include the extension of the addition operation to the… …   Wikipedia

  • Iterated monodromy group — In geometric group theory and dynamical systems the iterated monodromy group of a covering map is a group describing the monodromy action of the fundamental group on all iterations of the covering. It encodes the combinatorics and symbolic… …   Wikipedia

  • Function composition — For function composition in computer science, see function composition (computer science). g ∘ f, the composition of f and g. For example, (g ∘ f)(c) = #. In mathematics, function composition is the application of one function to the resul …   Wikipedia

  • iterated integral — noun : an integral of a function of several variables that is evaluated by finding the definite integral with respect to one variable and then the definite integral of the result with respect to the second and so continuing until the desired… …   Useful english dictionary

  • iterated integral — Math. 1. a double integral that is evaluated by first integrating the integrand with respect to one variable with the second variable being held constant and then integrating the resulting function with respect to the second variable. 2. a… …   Universalium

  • Ultra exponential function — Articleissues OR=January 2008 other=This article uses nonstandard notations, which are confusing and superfluous.In mathematics the ultra exponential function is a special case of the iterated exponential function more commonly known as tetration …   Wikipedia

  • Refinable function — In mathematics, in the area of wavelet analysis, a refinable function is a function which fulfills some kind of self similarity. A function varphi is called refinable with respect to the mask h if:varphi(x)=2cdotsum {k=0}^{N 1} h… …   Wikipedia

  • Artin-Mazur zeta function — In mathematics, the Artin Mazur zeta function is a tool for studying the iterated functions that occur in dynamical systems and fractals.It is defined as the formal power series :zeta f(z)=exp sum {n=1}^infty extrm{card} left( extrm{Fix} (f^n)… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”