Discrete Maps

Discrete map

Is a function $F:X →X$, defined on a space X, such that the evolution of the system is given by the iteration $x_{n+1} =F(x_n)$, with $n =0,1,2,...$

The sequence $\{x_n\}$ generated by repeated applications of $F$ is called the orbit of the initial condition $x_0$.

How to draw cobweb plots

1. Plot the given function $y= f(x)$ and the line $y=x$.

2. For $x_n$, draw a vertical line $x =x_n$ that hits the curve $y= f(x)$.
   This gives $f (x_n)$, which is equal to $x_{n+1}$.

3. Draw a horizontal line for $f(x_n)$ until it hits the line $y = x$.

4. Repeat steps 2. and 3. using $x_{n+1}$.

The cobweb plot is expected to converge to the intersection of f(x) with x=y.

Fixed point

Since $x_{n+1} = F(x_n)$, a fixed point of a discrete map must satisfy the condition $x_F =F(x_F)$.

Stability conditions for fixed points

Can find that $δx_{n+1} = f'(x_F)δx_n$

• If |f'(x_F)| > 1, we have |δx_{n+1}| > |δx_n|, which leads to an unstable fixed point.
  That is, the deviation from the fixed point increases with every iteration.

• If |f'(x_F)|< 1, we have |δx_{n+1}| < |δx_n|, which leads to a stable fixed point.
  That is, the deviation from the fixed point decreases with every iteration.

• If $|f'(x_F)|=1$, the stability of the fixed point is undetermined and the fixed point is marginal.

• If $f'(x_F) = 0$, then there is a special case: a super-stable fixed point, with $δx_{n+1} = \frac{1}2 f ''(x_F)(δx_n)^2$. In this case $δx_{n+1}$ is very small and we have a very fast convergence to the fixed point.

Marginal fixed point

Occurs if $|f'(x_F)|=1$, and stability is undetermined so must go to higher orders in the Taylor expansion:

$$x_{n+1} = f(x_F +δx_n)=x_F ±δx_n+ \frac{1} 2 f ''(x_F)(δx_n)^2 +\mathcal{O}((δx_n)^3)$$

Issues with a marginal fixed point

A fixed point with derivative =1 is not asymptotically stable, so small errors are not reduced: $x_{n+1}−x^∗≈x_{n}−x^∗$

Hence the iteration generally converges very slowly or may fail to converge.

(Any maps producing a marginal fixed point are not suitable choices to find roots, as they do not reliably converge)

Logistic map

Its evolution is given by the difference equation $N_{n+1} =aN_n−bN^2_ n$, where $N_n$ is the population of the $n^\text{th}$ generation, and often a, b>0.

This can be simplified by considering $x_n =bN_n/a$, and gives

$x_{n+1} =ax_n(1−x_n)$.

Fixed points of the logistic map

The fixed points are determined by setting $x_F =ax_F(1−x_F)$ to zero, which gives:

$x_F =0$ and $x_F =1−\frac{1} a$

Stability is given by $\frac{dF}{dx}|_{x_F}$, which is:

• $x_F=0$: stable for a<1, and unstable for a>1.

• $x_F =1−\frac{1} a$: stable for |2−a| <1, (so for 1<a<3), and unstable otherwise.

Condition to have a two-cycle (solution with period of two)

The condition $f ^2(x) = f(f(x)) = x$ must be met.

Stability of a two-cycle

If $x^∗$ is one of the points at the cycle, then $x^∗ = f^2(x^∗)$, and $x_n =x^∗+δx_n$ (close to this point). This leads to

$$x_{n+2}=f^2(x^∗+δx_n)≈x^∗+\frac{df^2(x) }{dx} δx_n$$

with stability defined by \bigg|\frac{df^2(x) }{dx}\bigg| <1 \qquad⇒\qquad\text{stable two-cycle} \bigg|\frac{df^2(x) }{dx}\bigg| >1 \qquad⇒\qquad\text{unstable two-cycle}

Using the chain rule, $\frac{df^2(x)}{ dx }=f'(f(x))f'(x)$, and for a two-cycle with $x=x_1$ and $f(x_1)=x_2$ there will be stability if f'(x_1)f'(x_2)< 1.

Shape of logistic map

The two-cycle is only stable for set values of $a$, then there is a bifurcation to a stable four-cycle, and the two-cycle becomes unstable. As $a$ increases, more bifurcations occur, and cycles appear in powers of 2, which the stability of each cycle shorter than the last.

Eventually chaos occurs, and there are no stable cycles for any finite power of two, and trajectories become non-periodic.

This is shown as a series of continuous bands at a>a_\infty\approx 3.56995.

If there are more than one solutions (roots) to an equation, what determines which one is found?

The root obtained depends on the initial condition.

Different initial guesses lie in different basins of attraction of the various fixed points, so the iteration converges to the root whose basin contains.

Why it is advantageous that a fixed point of the map is superstable?

(Errors shrink faster than linearly near the fixed point). The iteration converges extremely rapidly to the root.

Near a fixed point, $x_{n+1}−x^∗≈f’(x^∗)(x_n−x^∗)$, and for a superstable fixed point, $f’(x^*)=0$, so the linear error term vanishes and convergence is much faster.