{ "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 }