{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c46e5a9b",
   "metadata": {},
   "source": [
    "# Calcul d'un zéro d'une fonction par recherche linéaire itérative\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$.\n",
    "\n",
    "On s'appuie sur la **recherche par balayage** vue en cours, dont la complexité est: $\\Omicron(\\frac{1}{\\epsilon} \\cdot (b-a))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "decf0d81",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *\n",
    "\n",
    "def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:\n",
    "    x: float = a\n",
    "    while x < b:\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": "markdown",
   "id": "64077999",
   "metadata": {},
   "source": [
    "## Principe de l'algorithme itératif\n",
    "\n",
    "On propose d'améliorer la complexité de cet algorithme en l'appliquant **de manière itérative**, sur des intervalles de plus en plus petits, et avec une précision $\\epsilon$ croissante.\n",
    "\n",
    "Principe de l'algorithme:\n",
    "- on débute en appelant `findZeroLinear(f, a, b, p)` avec $p = \\frac{(b-a)}{N}$. Cela revient à découper $[a; b]$ en $N$ sous-intervalles pour une certaine constante $N > 1$\n",
    "- la fonction `findZeroLinear` retourne une valeur `x` telle que `f` a un zéro dans $[x; x+p]$\n",
    "- on recommence sur l'intervalle $[x; x+p]$ avec une précision plus élevée: $p/N$, en appelant `findZeroLinear(f, x, x+p, p/N)`, et ainsi de suite.\n",
    "- on arrête lorsque le l'intervalle devient petit: $p \\le \\epsilon$\n",
    "\n",
    "*NB:* si le premier appel à `findZeroLinear` retourne `None`, on arrête l'algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1aa2abff",
   "metadata": {},
   "source": [
    "## Question 1\n",
    "\n",
    "Écrire la fonction `findZeroIterative` qui calcule un zéro d'une fonction `f` dans un intervalle `[a; b]` avec une précision `eps`. La fonction parcourt `N` sous-intervalles à chaque itération.\n",
    "\n",
    "- PRECOND:\n",
    "  - a < b\n",
    "  - f est une fonction continue sur [a; b]\n",
    "  - eps > 0\n",
    "  - N > 1\n",
    "- POSTCOND:\n",
    "  - si `findZeroIterative` retourne x != None, alors x appartient à [a; b] et f a un zéro dans [x; x+eps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42b7f8e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findZeroIterative(f: Function, a: float , b: float, eps: float, N: int) -> float | None:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b15bc3fa",
   "metadata": {},
   "source": [
    "## Question 2\n",
    "\n",
    "Quelle est la longueur des intervalles passés lors des appels successifs à `findZeroLinear`?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e8e686c",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "73d014e1",
   "metadata": {},
   "source": [
    "## Question 3\n",
    "\n",
    "Quel est le nombre d'appels à la fonction `findZeroLinear`?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d8a5283",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b9ad5c4e",
   "metadata": {},
   "source": [
    "## Question 4\n",
    "\n",
    "La complexité d'un appel `findZeroLinear(f, l, r, p)` est $\\Omicron(\\frac{1}{p} \\cdot (r - l))$. Déterminer la complexité de `findZeroIterative`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64babb2a",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d516bc38",
   "metadata": {},
   "source": [
    "## Question 5\n",
    "\n",
    "Que pouvez-vous dire du cas `N=2`?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83174b60",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "103fbf15",
   "metadata": {},
   "source": [
    "## Question 6\n",
    "\n",
    "Évaluez expérimentalement la complexité de la fonction `findZeroIterative`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "608cbceb",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# Définir la fonction f\n",
    "def f(x):\n",
    "    return np.cos(x) - x\n",
    "\n",
    "# Définir l'intervalle [a; b]\n",
    "a = 0.0\n",
    "b = 2.5\n",
    "\n",
    "# Définir le facteur de raffinement de la précision (divisée par N à chaque itération)\n",
    "N = 10\n",
    "\n",
    "if False:\n",
    "    # On teste les valeurs eps=10*(-i) jusqu'à i=max_pow\n",
    "    max_pow = 10\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 findZeroIterative(f, a, b, eps, N)\n",
    "else:\n",
    "    print(\"Évaluation de performance désactivée\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "defaultInterpreterPath: 3.14.7.final.0",
   "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
}