{
"nbformat_minor": 2,
"nbformat": 4,
"cells": [
{
"source": [
"$$\n",
"\\def\\CC{\\bf C}\n",
"\\def\\QQ{\\bf Q}\n",
"\\def\\RR{\\bf R}\n",
"\\def\\ZZ{\\bf Z}\n",
"\\def\\NN{\\bf N}\n",
"$$\n",
"# The logistic map\n",
"\n",
"Authors \n",
"- Thierry Monteil\n",
"- Vincent Delecroix\n",
"\n",
"## Some general definitions\n",
"\n",
"Let $X$ be a set and $f$ be a function from $X$ to $X$. Since the domain and the codomain of $f$ are equal, we can *iterate* the function $f$ *i.e.* the functions $f$, $f^2 := f \\circ f$, $f^3 := f\\circ f\\circ f$, ... are well defined. For every $x_0$ in $X$, we can define the *orbit* of $x_0$ under $f$ as the sequence $x_0, x_1, x_2, \\dots$ where $x_{i+1}:=f(x_i)=f^{i+1}(x_0)$.\n",
"\n",
"A point $p\\in X$ is said to be a *fixed point* if $f(p)=p$. Such points $p$ have a constant orbit.\n",
"\n",
"A point $p$ in $X$ is said to be *periodic* if there exists a positive integer $n$ such that $f^n(p)=p$. The smallest such $n$ is called the *period* of $f$.\n",
"\n",
"## A family of functions\n",
"\n",
"For every fixed $r \\in [0,4]$, we define the function $g_r:[0,1]\\to [0,1]$ by $g_r(x):=rx(1-x)$. Such map is called a *logistic map*.\n",
"\n",
"**Prove** that for any parameter $r \\in [0,4]$, the function $g_r$ preserves the interval $[0,1]$ (hence it is well defined, and we can iterate it).\n",
"\n",
"**Draw** the graph of the map $g_r$ for various values of the parameter $r$\n",
"\n",
"*Hint:* Look at the function `plot` (to draw the graph of a function) and `Graphics()` (that creates an empty graphics). To superpose images you need to use `+`."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## Drawing orbits\n",
"\n",
"**Write** a Python function `logistic_orbit(r, x0, itermin, itermax)` that returns the list $[x_{\\mbox{itermin}},\\dots,x_{\\mbox{itermax}-1}]$ of the orbit of $x_0$ under the map $g_r$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Write** a Python function `plot_logistic_orbit(r, x0, itermin, itermax)` that draws this chunk of orbit as the function $\\{\\mbox{itermin},\\dots,\\mbox{itermax}-1\\} \\to [0,1]$, $n\\mapsto f^n(x_0)$.\n",
"\n",
"*Hint:* you can have a look at the `point2d` and `line2d` functions."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Write** a Python function `logistic_cobweb(r, x0, itermin, itermax)` that draws this chunk of orbit directly on the graph of the map $g_r:[0,1]\\to [0,1]$, as a *cobweb plot* (see the left part of the picture below).\n",
"\n",
"*Hint:* you can have a look at this [wikipedia article](https://en.wikipedia.org/wiki/Cobweb_plot)."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"The following interact allows to change the values of the four parameters easily and observe the different behaviours of the orbits.\n",
"\n",
"*Hint*: to align images, you can tune the `aspect_ratio` option of the plotting functions in the previous questions."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"@interact\n",
"def _(r = slider(0.0, 4, step_size=0.01, label='r'), x0 = slider(0, 1, step_size=0.01, default=0.5, label='x0'), itermin = slider(0, 500, step_size=1, default=0, label='itermin'), itermax = slider(0, 500, step_size=1, default=100, label='itermax')):\n",
" graphics_array(((logistic_cobweb(r, x0, itermin, itermax),plot_logistic_orbit(r, x0, itermin, itermax))),1,2).show()"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"The interact could look like this:\n",
"\n",
"![image](logistic_orbit_interact.png)\n",
"\n",
"Here, we can observe the first $100$ iterates of the orbit of the point $x_0=0.39$ for the map $g_{3.63}$. It is approaching a periodic orbit of period $6$.\n",
"\n",
"## Attractive fixed points\n",
"\n",
"**Prove** that $g_r$ has two fixed points, namely $0$ and $1-1/r$ (if it belongs to $[0,1]$).\n",
"\n",
"**Observe** that the graph of $g_r$ intersects the line $y=x$ exactly at the fixed points"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"A *fixed point* $p$ of $g_r$ is said to be *attractive* if $|g_r'(p)| < 1$ and *repulsive* if $|g_r'(p)| > 1$.\n",
"\n",
"When a fixed point $p$ is attractive, there exists a neighborhood $N$ of $p$ such that the orbit of every $x_0$ in $N$ converges to $p$. The set of points $x_0$ whose orbits converge to $p$ is called the *basin of attraction* of $p$.\n",
"\n",
"**For which** values of $r$ is $0$ attractive ? **For which** values of $r$ is $1-1/r$ attractive ?\n",
"\n",
"**Check** this behaviour for $r = 0.6$, $r = 1.8$ and $r = 2.2$ with your interact.\n",
"\n",
"**Prove** that, when $0$ is an attractive fixed point, its basin of attraction is $[0,1]\\setminus \\{1-1/r\\}$.\n",
"\n",
"**Prove** that, when $1-1/r$ is an attractive fixed point, its basin of attraction is $(0,1)$.\n",
"\n",
"When $1-1/r$ is an attractive periodic point, the orbit $g_r^n(1/2)$ converges to $1-1/r$. **Find** the speed of convergence"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"When $1-1/r$ is repulsive, **find** the speed at which a point close to $0.5$ drifts away from $0.5$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"A periodic point $p$ is called *super-attractive* if $|g_r'(p)| = 0$. Find the parameter for which $1-1/r$ is a super-attractive fixed point."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"For this parameter, find the convergence speed"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## Attractive periodic orbits\n",
"\n",
"This definition of attraction and repulsion extend to periodic points. Let $p$ be a periodic point of $g_r$ with period $n$. That is $g_r^n(p)\n",
"= p$ and $g_r^m(p) \\not= p$ for $m < n$. In order to see the behavior of orbits in a neighborhood of a fixed point one need to study the derivative of $g_r^n$ which equals\n",
"\n",
"$$(g_r^n)'(x) = g_r'(x) g_r'(g_r(x)) \\dots g_r'(g_r^{n-1}(x)).$$\n",
"\n",
"Hence, a periodic orbit $p, g_r(p), \\dots, g_r^{n-1}(p)$ of $g_r$ is is said to be respectively *attractive*, *super-attractive* or *repulsive* if $|g_r'(p) g_r'(g_r(p)) \\dots g_r'(g_r^{n-1}(p)) |$ is $< 1$, $=0$ or $> 1$.\n",
"\n",
"**Check** that, for $r=3.3$, there is no attractive fixed point, but an attractive periodic orbit of period 2."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Compute** an exact expression (with radicals) of the two points of this attractive orbit (you can also give their minimal polynomial)."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## Bifurcation diagram\n",
"\n",
"Up to now we worked with a fixed parameter $r$ and studied the behaviour of the iterations of $g_r$. We will now try to understand how the dynamics evolve with $r$. We will hence work in the parameter space $[0,4]$.\n",
"\n",
"The *bifurcation diagram* $B$ of the family $\\{g_r\\}$ is the subset of $[0,4]\\times[0,1]$ of points $(r,x)$ such that $x$ is an accumulation point of the orbit of $1/2$ for $g_r$. We will denote by $B_r$ the slice at $r$, that is the set of accumulation point of the orbit of $1/2$ for $g_r$. We hence have\n",
"\n",
"$$B = \\cup_{r \\in [0,4]} \\{r\\} \\times B_r.$$\n",
"\n",
"**Compute** an approximation of the slices $B_r$ for various values of $r$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Check** that the set of accumulation point of a random orbit is also $B_r$\n",
"\n",
"*Hint:* you can have a look at `RDF.random_element`."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Write** a Python function `logistic_bifurcation_diagram(rmin, rmax, rstep)` that returns an approximation of the slice $B\\cap [\\mbox{rmin},\n",
"\\mbox{rmax}]\\times [0,1]$ of the bifurcation diagram, where two consecutive values of $r$ are at distance `rstep`.\n",
"\n",
"*Hint:* you can have a look at `srange`."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Draw** the complete bifurcation diagram"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Observe**, when $r$ increases, the evolution of attractive periodic orbits of period $1,2,4,8,\\dots$.\n",
"\n",
"## Islands of stability\n",
"\n",
"**Prove** that for all $r \\in [3, 4]$ the map $g_r$ has a (unique) periodic point of period 2"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Prove** that the segment $[3, 1 + \\sqrt{6}]$ corresponds to the regime where this orbit of period $2$ is attractive"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Prove** that for $r = 1 + \\sqrt{5}$ the critical point $1/2$ is part of the periodic orbit. In other words, the orbit of period 2 is super-attractive. We say that $1 + \\sqrt{5}$ is the *center* of the *island of stability* $[3, 1 + \\sqrt{6}]$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Drw** the bifurcation diagram with vertical lines at the parameters $3$ and $1 + \\sqrt{5}$ and $1 + \\sqrt{6}$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Find** the upper bound of the island of stability corresponding to the periodic orbit of period $4$ starting from $1 + \\sqrt{5}$ as well as its center"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Draw** the bifurcation diagram together with vertical lines delimiting the islands of stability for period 2 and 4 as well as their centers"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Could** you compute the center for the next bifurcations with period $8$, $16, $32\\`, ..."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"The behavior of the sequence of islands of stability for this sequence of period doubling was intensively studied on computers in the 70's by Feigenbaum. Let us denote by $c_n$ the center of the island of stability of period $2^n$. He observed the existence of a constant $\\delta$ so that as $n \\to \\infty$ we have a convergence\n",
"\n",
"$$\\frac{c_{n+1} - c_n}{c_n - c_{n-1}} \\to \\delta$$\n",
"\n",
"where $\\delta \\simeq 4.6692\\ldots$ is called the *Feigenbaum constant*. This was later proven by Lanford (1982), Eckmann-Wittwer (1987) and generalized by Lyubitch (1999).\n",
"\n",
"**Could** you compute a better approximation of the Feigenbaum constant?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Prove** that if for some parameter $r$ there is an attractive orbit, then for an interval around $r$ there is an attractive orbit with the same period and a center with a super attractive orbit.\n",
"\n",
"**Show** that there is a unique island of stability with period $3$\n",
"\n",
"*Hint:* solve the equation satisfied by the center"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Could you find an explicit rational number $r$ that belongs to this island?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## Chaotic parameters\n",
"\n",
"A famous result of Jakobson (1981) claims that in the space of parameters $[0,\n",
"4]$ if we remove all islands of stability, there remain a set of positive Lebesgue measure with interesting dynamics. More precisely, there are maps $g_r$ with invariant measures absolutely continuous with respect to Lebesgue.\n",
"\n",
"**Plot** an histogram of the orbit of a random point for $g_4$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Coud you find an explicit formula for the shape that you see?\n",
"\n",
"**Prove** that if $r_3\\simeq 3.6785$ is twice the maximal real root of the polynomial $x^3-x^2-x-1$, then $g_{r_3}^3(1/2) = 1-1/r$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Plot** an histogram of the orbit of a random point, with 300 bins, and 100000 iterates."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"We say that a parameter $r$ is *post-critically finite* if there exists $m < n$ so that \n",
"$g_r^n(1/2) = g_r^m(1/2)$ (in other words, the orbit of the critical point $1/2$ terminates into a periodic orbit). We will consider the simple case where $n = m+1$ that is when the critical point lands into the fixed point. The example $r_3$ above is a particular case of this situation with $m = 3$.\n",
"\n",
"**Solve** the equation $g_r^n(1/2) = 1-1/r$ in $r$ for $n=2,3,4,5,6$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Draw** for each of the parameters found in the above question, the histogram of the orbit of $1/2$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Observe** that the peaks of the density can be seen on the bifurcation diagram.\n",
"\n",
"## Symbolic coding\n",
"\n",
"Given a map $g_r$ with $r \\in [0,4]$ we can give a *coding* to the orbits. More precisely, given a point $x\\in [0,1]$, we associate the sequence $\\pi(x) = (w_0, w_1, w_2, \\dots) \\in \\{L,R,C\\}^\\mathbb{N}$, where $w_i = L$ if $g_r^i(x) \\in [0,1/2)$, $w_i = R$ if $g_r^i(x) \\in (1/2,1]$, and $w_i = C$ if $g_r^i(x) = 1/2$.\n",
"\n",
"Note that $\\pi \\circ g_r = S \\circ \\pi$, where $S : \\{L,R,C\\}^\\mathbb{N} \\to\n",
"\\{L,R,C\\}^\\mathbb{N}$ is the *shift map* $(w_0, w_1, w_2, \\dots) \\mapsto (w_1,\n",
"w_2, \\dots)$.\n",
"\n",
"This coding provides a dictionary between dynamical properties of orbits of $g_r$ and combinatorial properties of the produced words. For example, the coding of a periodic orbit is an infinite periodic word.\n",
"\n",
"**Write** a Python function `logistic_coding(r, x0, itermin, itermax)` that returns the sequence $(w_{itermin}, w_{itermin+1}, \\ldots, w_{itermax-1})$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Recall that on the left of the bifurcation diagram we have a sequence of islands of stability whose associated maps present an attractive orbit of period $2^n$. Moreover, each of this island has an associated center.\n",
"\n",
"For $n=1,2,3,4$ determine how the coding of the periodic orbit vary as we move inside the islands"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Could you find an explicit construction for the coding of all the period doubling sequence?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"We now study the parameter $r=4$. What is the coding of the orbit of the critical point $x=1/2$ under $g_4$?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"**Prove** that any sequence of $L$ and $R$ is the coding of a unique element $x \\in [0,1]$\n",
"\n",
"**Write** a function `logistic_coding_to_point(seq)` that given a sequence `seq` of $L$ and $R$ returns the unique point `x` so that its associated sequence is the period word $seq\\ seq\\ seq\\ \\ldots$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
}
],
"metadata": {
"kernelspec": {
"display_name": "sagemath",
"name": "sagemath"
}
}
}