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