Iterated function

From Wikipedia, the free encyclopedia

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

1 Definition
2 Creating sequences from iteration
3 Fixed points
4 Limiting behaviour
5 Flows
6 Conjugacy
7 Markov chains
8 Examples
- 8.1 Visual example
9 Means of study
10 See also
11 References

[edit] Definition

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

Let X be a set and

$f:X\rightarrow X$

be a function. Define the n 'th iterate

f n

of f by

f 0 = id X

where $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))$ .

[edit] Creating sequences from iteration

The sequence of functions

fⁿ

is called a Picard sequence, named after Charles Émile Picard. For a fixed x in X, the sequence of values

fⁿ(x)

is called the orbit of x.

fⁿ(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.

[edit] 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.

[edit] 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.

[edit] Flows

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

[edit] 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.

[edit] 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.

[edit] 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.

[edit] Visual example

This pyramid will be iterated many times to form a pyramid made out of the Sierpinski triangle.	The basic structure of the pyramid can now be seen.	Further iterations can clarify the structure further.	The pyramid from the previous image can be thought of as the top of this pyramid; three more identical to it are attached, an apex for every angle of the base.
The size of theses images are the same, but the size of the figure increases in every image; the viewer is "zooming out" with every iteration.	With each iteration, the original pyramid becomes relatively smaller...	...until it cannot be seen at all, lost in all of the other pyramids just like it.	Eventually, sequential iterations may appear similar to each other to the human eye, but they are not mathematically similar. Not counting the original pyramid, this is the seventh iteration.