{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e2dab9cf",
   "metadata": {},
   "source": [
    "# Recherche d'un zéro d'une fonction\n",
    "\n",
    "On cherche à **résoudre numériquement** une équation de la forme:\n",
    "\n",
    "$$f(x) = 0 \\qquad \\text{ avec } \\ f \\, : \\, \\mathbb{R} \\to \\mathbb{R} \\text{ continue}$$\n",
    "\n",
    "Il n'est généralement pas possible de calculer $\\alpha$ telle que $f(\\alpha) = 0$, **ni même de la représenter en machine**. On cherche donc à l'**approximer finement**. Étant donnée une constante réelle $\\epsilon > 0$, on souhaite calculer une valeur $x$ telle que $|x - \\alpha| \\le \\epsilon$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1870c9b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# Definition de la fonction f\n",
    "def f(x: float) -> float:\n",
    "    return np.cos(x) - x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4de5af0",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *\n",
    "\n",
    "# Intervalle sur l'axe x\n",
    "xrange = (-10, 10)\n",
    "\n",
    "# Représente la fonction f ci-dessus, et la ligne y=0\n",
    "plt = plotFunction(f, xrange)\n",
    "plt.axhline(y=0, color='y', linestyle='-', label=\"y=0\")\n",
    "plt.grid(visible = True)\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c181ca9",
   "metadata": {},
   "source": [
    "## Résolution par balayage\n",
    "\n",
    "On suppose connus:\n",
    "- un intervalle $[a; b] \\subseteq \\mathbb{R}$,\n",
    "- une fonction $f$ continue sur $[a; b]$\n",
    "- et une constante réelle $\\epsilon > 0$.\n",
    "\n",
    "Si $f$ admet un zéro $\\alpha \\in [a;b]$, on veut calculer $x \\in [a;b]$ qui approxime $\\alpha$ à $\\epsilon$ près: $|x - \\alpha| \\le \\epsilon$.\n",
    "\n",
    "On procède par **balayage** de l'intervalle $[a; b]$ par pas de $\\epsilon$:\n",
    "- On considère les valeurs successives: $x=a$, puis $x=a + \\epsilon$, puis $x = a + 2\\epsilon$,...\n",
    "- En tout point $x$, si $f(x)$ et $f(x+\\epsilon)$ sont de *signes opposés*, alors $f$ admet un zéro dans l'intervalle $[x; x+\\epsilon]$ (sous hypothèse que $f$ est continue ou du moins qu'elle respecte le [théorème des valeurs intermédiaires](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_valeurs_interm%C3%A9diaires#Le_th%C3%A9or%C3%A8me_des_valeurs_interm%C3%A9diaires)).\n",
    "- une telle valeur de $x$ est une approximation à $\\epsilon$ près de $\\alpha$: $|x - \\alpha| \\le \\epsilon$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63a80cdb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None :\n",
    "    x: float = a\n",
    "    while x <= b:\n",
    "        print(f\"x={x}\")\n",
    "        xx: float = min(b, x + eps)\n",
    "        if f(x) * f(xx) <= 0:\n",
    "            return x\n",
    "        x += eps\n",
    "    return None # pas de zéro trouvé"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d8e426f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Intervalle de recherche du zéro\n",
    "a = 0.0\n",
    "b = 2.5\n",
    "\n",
    "# Représente la fonction f sur [a; b], et la ligne y=0\n",
    "plt = plotFunction(f, (a, b))\n",
    "plt.axhline(y=0, color='y', linestyle='-', label=\"y=0\")\n",
    "plt.grid(visible = True)\n",
    "plt.legend()\n",
    "plt.show()\n",
    "\n",
    "# Précision\n",
    "eps = 0.1\n",
    "\n",
    "x = findZeroLinear(f, a, b, eps)\n",
    "\n",
    "if x is None:\n",
    "    print(\"Aucun zéro trouvé\")\n",
    "else:\n",
    "    print(f\"Approximation calculée: x={x}, donne f(x)={f(x)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e7f055a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Évaluation de la perforance de findZeroLinear\n",
    "# Remplacer False par True pour activer\n",
    "if False:\n",
    "    # On teste les valeurs eps=10*(-i) jusqu'à i=max_pow\n",
    "    max_pow = 7\n",
    "\n",
    "    for pow in range(1, max_pow + 1):\n",
    "        eps = 10**(-pow)\n",
    "        print(f\"eps={eps} \", end='')\n",
    "        %timeit -r 1 -n 10 findZeroLinear(f, a, b, eps)\n",
    "else:\n",
    "    print(\"Évaluation de performance désactivée\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c5f0a50",
   "metadata": {},
   "source": [
    "## Recherche dichotomique\n",
    "\n",
    "- On suppose que $f(a)$ et $f(b)$ n'ont pas le même signe\n",
    "- Par le théorème des valeur intermédiaires, $f$ admet un zéro dans $[a; b]$\n",
    "- On examine la valeur $f(p)$ pour $p$ au milieu de $[a; b]$\n",
    "  - si $f(a)$ et $f(p)$ n'ont pas le même signe, alors $f$ a un zéro dans $[a; p]$\n",
    "  - sinon, $f(p)$ et $f(b)$ n'ont pas le même signe, donc $f$ admet un zéro dans $[p; b]$\n",
    "- On recommence jusqu'à avoir un intervalle de largeur inférieure à $\\epsilon$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1619b007",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findZeroBin(f: Function, a: float, b: float, eps: float) -> float:\n",
    "    assert f(a) * f(b) < 0\n",
    "    l: float = a; r: float = b\n",
    "    while r - l > eps:\n",
    "        p: float = (l + r) / 2\n",
    "        if f(a) * f(p) <= 0:\n",
    "            r = p\n",
    "        else:\n",
    "            l = p\n",
    "    return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be71a354",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Intervalle de recherche du zéro\n",
    "a = 0.0\n",
    "b = 2.5\n",
    "\n",
    "if f(a) * f(b) >= 0:\n",
    "    raise Exception(\"f doit avoir des signes opposés en a et b\")\n",
    "\n",
    "# Représente la fonction f sur [a; b], et la ligne y=0\n",
    "plt = plotFunction(f, (a, b))\n",
    "plt.axhline(y=0, color='y', linestyle='-', label=\"y=0\")\n",
    "plt.grid(visible = True)\n",
    "plt.legend()\n",
    "plt.show()\n",
    "\n",
    "# Précision\n",
    "eps = 10**(-7)\n",
    "\n",
    "x = findZeroBin(f, a, b, eps)\n",
    "\n",
    "print(f\"Approximation calculée: x={x}, donne f(x)={f(x)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5958f83",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Évaluation de la perforance de findZeroBin\n",
    "# Remplacer False par True pour activer\n",
    "if False:\n",
    "    # On teste les valeurs eps=10*(-i) jusqu'à i=max_pow\n",
    "    max_pow = 7\n",
    "\n",
    "    for pow in range(1, max_pow + 1):\n",
    "        eps = 10**(-pow)\n",
    "        print(f\"eps={eps} \", end='')\n",
    "        %timeit -r 100 -n 100 findZeroBin(f, a, b, eps)\n",
    "else:\n",
    "    print(\"Évaluation de performance désactivée\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0134cc0f",
   "metadata": {},
   "source": [
    "## Méthode de Newton\n",
    "\n",
    "La [méthode de Newton](https://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton#L'algorithme) consiste à approximer un zéro $\\alpha$ de $f$ par calcul d'une suite $(x_k)_{k \\in \\mathbb{N}}$ qui converge vers $\\alpha$.\n",
    "\n",
    "![width:50%](https://upload.wikimedia.org/wikipedia/commons/8/83/Methode_newton.png)\n",
    "\n",
    "- À partir de $x_0=a$ (une valeur choisie)\n",
    "- On approxime $f$ en $x_0$ par sa **tangente $t_0$ en $x_0$**\n",
    "- La solution de $t_0(x)=0$ donne $x_1$\n",
    "- On recommence à partir de $x_1$, jusqu'à obtenir $|x_{k+1} - x_k| \\le \\epsilon$\n",
    "\n",
    "La tangente en $x_k$ est la droite d'équation:\n",
    "\n",
    "$$t_k(x) = f(x_k) + f'(x_k) \\cdot (x - x_k)$$\n",
    "\n",
    "Le point $x_{k+1}$ est la solution de $t_k(x)=0$.\n",
    "\n",
    "La méthode de Newton calcule la suite $(x_k)_{k \\in \\mathbb{N}}$:\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "x_0 = a & \\\\\n",
    "x_{k+1} = x_k - \\frac{f(x_k)}{f'(x_k)}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "jusqu'à $|x_{k+1} - x_k| \\le \\epsilon$\n",
    "\n",
    "Le calcul de la suite $(x_k)_{k \\in \\mathbb{N}}$ nécessite de connaître $f'(x_k)$:\n",
    "- soit $f'$ est connue\n",
    "- soit $f'(x_k)$ peut-être approximée comme le taux d'accroissement entre $f(x_k)$ et $f(x_k + \\epsilon)$, c'est à dire: $\\frac{f(x_k + \\epsilon) - f(x_k)}{\\epsilon}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0095250a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findZeroNewton(f: Function, a: float, eps: float, df: Function | None = None) -> float:\n",
    "    x=a\n",
    "    while True:\n",
    "        if df is None :\n",
    "            dfx:float = (f(x+eps)-f(x))/eps  # dérivée approchée\n",
    "        else :\n",
    "            dfx:float = df(x)\n",
    "        nx: float = x - f(x)/dfx # calcul du prochain x\n",
    "        if abs(nx - x) <= eps:\n",
    "            return x\n",
    "        x = nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1dfeeb3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Intervalle de recherche du zéro\n",
    "a = 0.0\n",
    "b = 2.5\n",
    "\n",
    "# Représente la fonction f sur [a; b], et la ligne y=0\n",
    "plt = plotFunction(f, (a, b))\n",
    "plt.axhline(y=0, color='y', linestyle='-', label=\"y=0\")\n",
    "plt.grid(visible = True)\n",
    "plt.legend()\n",
    "plt.show()\n",
    "\n",
    "# Dérivée de f\n",
    "def df(x: float) -> float:\n",
    "    return -np.sin(x) - 1\n",
    "\n",
    "# Précision\n",
    "eps = 10**(-10)\n",
    "\n",
    "x = findZeroNewton(f, a, eps, df)\n",
    "\n",
    "print(f\"Approximation calculée: x={x}, donne f(x)={f(x)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63d39902",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Évaluation de la perforance de findZeroNewton\n",
    "# Remplacer False par True pour activer\n",
    "if False:\n",
    "    # On teste les valeurs eps=10*(-i) jusqu'à i=max_pow\n",
    "    max_pow = 7\n",
    "\n",
    "    for pow in range(1, max_pow + 1):\n",
    "        eps = 10**(-pow)\n",
    "        print(f\"eps={eps} \", end='')\n",
    "        %timeit -r 100 -n 100 findZeroNewton(f, a, eps)\n",
    "else:\n",
    "    print(\"Évaluation de performance désactivée\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pyvenv-3.14 (3.14.7)",
   "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.14.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}