Iteration and orbits

What it means to apply a rule over and over, what the resulting sequence is called, and why some starting points settle down while others run away.

August 31, 2026

9 minutes read

1752 words

Contents14

Applying one rule repeatedly, with each answer becoming the next question, produces a sequence. Which sequence depends entirely on where the process starts. Two starting points a hair apart can produce sequences that end in different places.

Assumed knowledge

Arithmetic, and what a rule that turns one number into another is. Reading a point off a graph with a horizontal and a vertical axis.

Nothing here needs complex numbers. Every example is an ordinary number, and the definitions carry over to complex numbers without change.

Ground covered

What a map is, and what its orbit from a starting point is. Fixed points, and how to find them. The cobweb, which reads an orbit off the graph of the map without arithmetic. Bounded and escaping orbits. Why some fixed points draw nearby orbits in while others push them away. Then the linear map, the same map for vectors, and a rule that remembers further back than one step. Last, what a cycle is.

A reader who can already say why the orbit of 0.8 under $x \mapsto x^2$ converges and the orbit of 1.05 does not can skip the page.

Maps

A map is a rule that turns one number into another. The rule $x \mapsto x^2$ turns 3 into 9 and turns 0.5 into 0.25. Written as a function it is $f(x) = x^2$ .

Repeated application is why the rule is called a map here. The same rule is applied to its own output, and then to that output again.

x_{n+1} = f(x_n) \tag{1}

Equation (1) says that each term comes from the one before it by one application of $f$ . Nothing else is needed to generate the whole sequence once the first term is chosen.

Orbits

The orbit of a starting point is the sequence that equation (1) produces from it. The starting point is written $x_0$ , and the terms that follow are $x_1, x_2, x_3$ and onward.

x_0, \quad f(x_0), \quad f(f(x_0)), \quad f(f(f(x_0))), \quad \ldots \tag{2}

Under $f(x) = x^2$ the orbit of $0.8$ runs $0.8,\; 0.64,\; 0.41,\; 0.168,\; 0.028$ and shrinks towards zero. The orbit of $1.05$ runs $1.05,\; 1.10,\; 1.22,\; 1.48,\; 2.18$ and grows without limit.

Both starting points lie within a quarter of each other, and their orbits go opposite ways. The value 1 is what separates them, and the next two sections say why.

Applying the map $n$ times is written $f^n$ , so $f^3(x)$ means $f(f(f(x)))$ . The superscript counts applications of the map. It is not a power, and $f^2(x)$ is not $f(x)^2$ .

Cobweb diagrams

An orbit can be read off the graph of the map with no arithmetic at all. Draw $y = f(x)$ and the diagonal line $y = x$ on the same axes.

Start on the horizontal axis at $x_0$ and go vertically to the curve. The height reached is $f(x_0)$ , which is the next term. To apply the map again that height has to become the next input, which means moving it onto the horizontal axis. Going horizontally to the diagonal does exactly that, because a point on the diagonal has its height and its position equal.

Repeating the pair of moves draws a staircase, and the corners of the staircase are the terms of the orbit.

Two orbits of the same map, read off its graph. Up to the curve, across to the diagonal, and repeat. The staircase from 0.8 falls into the origin, and the one from 1.05 climbs away.

The diagonal is where the curve is compared against the input. Where the curve lies below the diagonal the map returns something smaller than it was given, and the staircase steps down. Where the curve lies above it the map returns something larger, and the staircase steps up.

Fixed points

A fixed point is a number the map leaves alone.

f(p) = p \tag{3}

Its orbit is the same value forever, because every application returns it unchanged. On the graph a fixed point is where the curve crosses the diagonal, since that is where the output equals the input.

Fixed points are found by solving equation (3). For $f(x) = x^2$ that means solving $x^2 = x$ , which factors as $x(x - 1) = 0$ .

x^2 = x \quad\Longrightarrow\quad x = 0 \;\text{ or }\; x = 1 \tag{4}

The two crossings in the figure are exactly those two values.

Bounded and escaping orbits

An orbit is bounded when one fixed distance holds every term of it. There has to be a number $R$ that no term ever exceeds in size.

|x_n| \le R \quad \text{for every } n \tag{5}

Which value $R$ takes does not matter. What matters is whether any such value exists.

An orbit escapes when no such $R$ exists, which means its terms grow without limit. Every orbit of a given map is one or the other.

The same two orbits written as sequences. The dashed line at 1 is the fixed point that separates the two behaviours.

Under $x \mapsto x^2$ the boundary is the fixed point 1. A starting point smaller than 1 in size has an orbit that falls to zero. A starting point larger than 1 in size has an orbit that escapes. A starting point of exactly 1 stays there.

Attracting and repelling

The two fixed points of $x \mapsto x^2$ behave in opposite ways. Orbits that begin near zero move towards it. Orbits that begin near 1, on either side, move away from it.

The difference is how much the map stretches a small step. The derivative of a map at a point measures that stretch. For $f(x) = x^2$ the derivative is $f'(x) = 2x$ .

A step near a fixed point $p$ is multiplied by $f'(p)$ at each application. A multiplier smaller than 1 in size shrinks the step every time, so the orbit is drawn in. A multiplier larger than 1 grows it, so the orbit is pushed away.

|f'(p)| < 1 \;\text{ attracting}, \qquad |f'(p)| > 1 \;\text{ repelling} \tag{6}

At $p = 0$ the derivative is 0, so zero is attracting. At $p = 1$ the derivative is 2, so 1 is repelling. That is why the boundary between the two behaviours sits exactly at 1.

A multiplier of exactly 1 in size decides nothing, and those cases need a closer argument than this page gives.

The linear map

The simplest map of all is multiplication by a constant, $f(x) = g\,x$ . Its orbit from $x_0$ is a list of powers.

x_0,\ g\,x_0,\ g^2 x_0,\ g^3 x_0,\ \dots, \qquad x_n = g^n x_0 \tag{7}

Its only fixed point is $0$ , unless $g = 1$ , when every point is fixed. The derivative is $g$ everywhere, so by equation (6) the fixed point attracts when $|g| < 1$ and repels when $|g| > 1$ . The orbit shrinks towards zero by the same factor at every step, or grows by it. A shrinking orbit of this kind is a geometric sequence. When the steps are instants of time it is an exponential decay, and decibels and exponential decay measures how fast.

Iterating a matrix

The same idea works when the state is a vector and the rule is a matrix, so that $v_{n+1} = M\,v_n$ and $v_n = M^n v_0$ . Whether the orbit shrinks depends on what $M$ does to lengths. Take the case where $M$ is $g$ times a matrix that keeps every length $Q$ .

|v_n| = |g|^n\,|Q^n v_0| = |g|^n\,|v_0| \tag{8}

The orbit then behaves exactly like the one-dimensional map of equation (7). The direction of $v_n$ swings about as $Q$ turns it, and its length follows $|g|^n$ . More generally, take a number $\gamma < 1$ for which $|Mv| \le \gamma\,|v|$ at every $v$ . The map is then a contraction, and every orbit falls to zero at least as fast as $\gamma^n$ . The feedback loop of a reverb is built to be a contraction, with a length-keeping mixing matrix preceded by gains all below 1.

A rule with memory

The maps on this page use only the previous value. A rule may reach further back than one step.

x_n = g\,x_{n-D} \tag{9}

Nothing new happens. The sequence splits into $D$ interleaved orbits of the map $x \mapsto g\,x$ , one for each remainder of $n$ on division by $D$ . Each of them shrinks by $g$ every $D$ steps. Measured per step the factor is $g^{1/D}$ , so a longer memory decays more slowly for the same $g$ . When several such rules with different $D$ have to fade in the same time, each one needs its own $g$ . Decibels and exponential decay says which.

Cycles

An orbit can return to a value it has already taken without that value being fixed. It then repeats forever, and the repeating block is a cycle.

f^k(p) = p, \quad \text{with } k \text{ the smallest such count} \tag{10}

The count $k$ is the period. A fixed point is the case $k = 1$ .

Under $f(x) = x^2 - 1$ the starting point 0 gives the orbit $0,\; -1,\; 0,\; -1$ and repeats with period 2. Neither value is fixed, because the map moves each of them, but the pair together is left alone.

A cycle is attracting or repelling by the same test as a fixed point, applied to $f^k$ rather than to $f$ . An attracting cycle draws in every orbit that starts near enough to it.

Figure sources

Both drawings come from one script kept beside this page. It draws the map $x \mapsto x^2$ , two of its orbits, and its two fixed points. The script needs NumPy and Matplotlib.

iterate.py

uv run --with numpy --with matplotlib python3 iterate.py