{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FEUILLE DE TP 11\n",
    "\n",
    "# Introduction aux schémas numériques pour f(x) = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'retina'\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 1 : Méthode d'itération (ou de point fixe)\n",
    "\n",
    "Dans cette exercice, on va utiliser les fonctions et les données initiales $x_0$ correspondantes \n",
    "\n",
    "> * a) $\\quad f(x) =  e^{x} - 1 - x  \\quad \\text{sur} \\quad   [-1, 1],  \\quad  x_0 = -0.5$ \n",
    "> * b) $\\quad f(x) =  x - \\sin(x) \\quad \\text{sur} \\quad   [-\\frac{\\pi}{2}, \\frac{5\\pi}{2}],  \\quad  x_0 = 1$ \n",
    "> * c) $\\quad f(x) =  x + \\sin(x) \\quad \\text{sur} \\quad   [-\\frac{\\pi}{2}, \\frac{5\\pi}{2}],  \\quad  x_0 = 1$ \n",
    "> * d) $\\quad f(x) =  x + \\cos(x) -1 \\quad \\text{sur} \\quad   [-\\frac{\\pi}{2}, \\frac{5\\pi}{2}],  \\quad  x_0 = 1$ \n",
    "> * e) $\\quad f(x) =  x - \\cos(x) +1 \\quad \\text{sur} \\quad   [-\\frac{\\pi}{2}, \\frac{5\\pi}{2}],  \\quad  x_0 = 1$ \n",
    "\n",
    "**Remarque**: \n",
    ">* Dans a) on cherche la racine $x^\\star=0$ de $e^{x} - 1 - 2 x = 0$.\n",
    ">* Dans les cas tests b), c), d), e), on cherche la racine simple $x^\\star = 0$ de $\\sin(x) = 0$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 1**\n",
    "\n",
    "> 1. Implémentez les différentes fonctions demandées dans cet exercice.\n",
    "> 2. Tracez dans des sous-figures séparées le graphe de chaque fonction et ajoutez la droite d'équation $y=x$.\n",
    "> 3. Déterminez visuellement les points fixes de chaque fonction dans l'intervalle considéré.\n",
    "> 4. Ajoutez un point (`scatter`) pour chaque point fixe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def f1(x):\n",
    "    return np.exp(x) - 1 - x\n",
    "def f2(x):\n",
    "    return x - np.sin(x)\n",
    "def f3(x):\n",
    "    return x + np.sin(x)\n",
    "def f4(x):\n",
    "    return x + np.cos(x) - 1\n",
    "def f5(x):\n",
    "    return x - np.cos(x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 219120 characters]\n",
      "text/plain": [
       "<Figure size 1200x1200 with 5 Axes>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 641,
       "width": 1002
      }
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig = plt.figure(figsize=(12, 12))\n",
    "\n",
    "x = np.linspace(-1, 1, 200)\n",
    "ax = fig.add_subplot(3, 3, 1)\n",
    "ax.plot(x, f1(x), label=\"Courbe f\")\n",
    "ax.plot(x, x, label=\"$y=x$\")\n",
    "ax.scatter([i for i in x if f1(i) == i], [f1(i) for i in x if f1(i) == i])\n",
    "ax.legend()\n",
    "\n",
    "x = np.linspace(-np.pi / 2, 5 * np.pi / 2)\n",
    "for fk, f in enumerate([f2, f3, f4, f5]):\n",
    "    ax = fig.add_subplot(3, 3, fk + 2)\n",
    "    ax.plot(x, f(x), label=\"Courbe f\")\n",
    "    ax.plot(x, x, label=\"$y=x$\")\n",
    "    ax.scatter([i for i in x if f(i) == i], [f(i) for i in x if f(i) == i])\n",
    "    ax.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 2**\n",
    "\n",
    "> Implémentez la méthode du point fixe à travers une fonction `x, niter, xL = point_fixe(f, x0, tol, itermax)`. Les valeurs par défaut de `tol` et de `itermax` seront respectivement `1.e-6` et `5000`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def point_fixe(f, x0, tol=1.0e-6, itermax=5000):\n",
    "    \"\"\"\n",
    "    Recherche de point fixe : méthode brute x_{n+1} = f(x_n)\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "\n",
    "    f: function\n",
    "        la fonction dont on cherche le point fixe\n",
    "    x0: float\n",
    "        initialisation de la suite\n",
    "    tol: float (default 1.e-6)\n",
    "        critère d'arrêt : |x_{n+1} - x_n| < tol\n",
    "    itermax: int\n",
    "        le nombre maximal d'itérations autorisées\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "\n",
    "    x: float\n",
    "        la valeur trouvée pour le point fixe\n",
    "    niter: int\n",
    "        le nombre d'itérations effectuées\n",
    "    xL: ndarray\n",
    "        la suite des itérés de la suite\n",
    "    \"\"\"\n",
    "    xL = [x0]\n",
    "    niter = 0\n",
    "    rk = tol + 1\n",
    "    while rk > tol and niter < itermax:\n",
    "        xL.append(f(xL[-1]))\n",
    "        rk = np.abs(f(xL[-1]) - xL[-1])\n",
    "        niter += 1\n",
    "    return xL[-1], niter, np.array(xL)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question**\n",
    "\n",
    "> Pour chacun des cas tests ci-dessus faire\n",
    ">   * Tracez dans un même graphique la courbe de la fonction $f$ et celle de la droite $x \\mapsto x$. \n",
    ">   * Générez la suite des itérés $x_n$ de la méthode d'itération du point fixe. \n",
    ">   * Représentez sur le même graphique la solution numérique  $x^\\star$ obtenue en dessinant un point à la position $(x^\\star, f(x^\\star))$ \n",
    ">   * Ajoutez en titre le nombre d'itérations effectuées pour atteindre le critère d'arrêt.\n",
    ">   * Représentez la ligne brisée joignant les points\n",
    "$(x_0,x_0)$, $(x_0,x_1)$, $(x_1, x_1)$, $(x_1, x_2)$, $\\ldots$, $(x_n,x_n)$.\n",
    ">   * Que remarquez-vous ?\n",
    "\n",
    "**Question**\n",
    "\n",
    "> Pour chacun des cas tests ci-dessus, faites une figure illustrant l'ordre de convergence de la suite vers le point fixe (attention, le point fixe obtenu n'est pas toujours le même). \n",
    "> - Vous pourrez tracer par exemple le nuage de points $(e_n, e_{n+1})$ où $e_n$ est l'erreur $|x_n-\\ell|$ à l'étape $n$ avec $\\ell$ la valeur limite du point fixe.\n",
    "> - Pour visualiser l'ordre, vous pourrez ajouter aux graphiques des droites de pente $1$, $2$ ou $3$.\n",
    ">\n",
    "> Pouvez-vous expliquer les différents comportements ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0.5, 1.0, \"Nombre d'itérations : 4\")"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 100752 characters]\n",
      "text/plain": [
       "<Figure size 600x600 with 1 Axes>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 527,
       "width": 537
      }
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# F1\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(6, 6))\n",
    "\n",
    "x, niter, xL = point_fixe(f1, -0.5)\n",
    "xx = np.linspace(-1, 1, 200)\n",
    "\n",
    "ax.plot(xx, f1(xx), label=\"Courbe f1\")\n",
    "ax.plot(xx, xx, label=\"$y=x$\")\n",
    "ax.scatter(x, f1(x), label=\"Point Fixe\")\n",
    "ax.legend()\n",
    "ax.set_title(f\"Nombre d'itérations : {niter}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.0, 4, array([1.00000000e+00, 1.58529015e-01, 6.63176756e-04, 4.86112320e-11,\n",
      "       0.00000000e+00]))\n"
     ]
    }
   ],
   "source": [
    "# F2\n",
    "print(point_fixe(f2, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(3.141592653589793, 5, array([1.        , 1.84147098, 2.80506171, 3.13527633, 3.14159261,\n",
      "       3.14159265]))\n"
     ]
    }
   ],
   "source": [
    "# F3\n",
    "print(point_fixe(f3, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.0014127204454923437, 1407, array([1.        , 0.54030231, 0.39785552, ..., 0.00141472, 0.00141372,\n",
      "       0.00141272]))\n"
     ]
    }
   ],
   "source": [
    "# F4\n",
    "print(point_fixe(f4, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 2 (facultatif): convergence de la méthode \n",
    "\n",
    ">* Pour chacun des cas tests ci-dessus faire\n",
    " * si la méthode converge, \n",
    "    * calculer la vitesse de convergence de la suite *(on pourra utiliser la fonction ``traquer_ordre`` du TP10)*\n",
    "    * calculer la constante asymptotique de convergence de la méthode  \n",
    "    * estimer le nombre d'itérations nécessaires pour gagner un chiffre exacte et vérifier que c'est le cas effectivement.\n",
    " * calculer eventuellement $f^{'}(x^*), f^{''}(x^*), f^{'''}(x^*) $ où $x^*$ est le point fixe de $f$ vers lequel la méthode semble converger et justifier le comportement de la suite générée à la lueur de ces valeurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
