{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4491e638-15f8-4074-aaba-9cdd6c75d86b",
   "metadata": {},
   "source": [
    "---\n",
    "## MT94 - P2026\n",
    "### Chapitre Problèmes non linéaires 1 (F. De Vuyst)\n",
    "### TP n° 1\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd4dfe4c-fd95-4b4d-986a-36a49a0dc453",
   "metadata": {},
   "source": [
    "#### Exercice 1 - Dichotomie\n",
    "\n",
    "Ecrire une fonction\n",
    "\n",
    "```\n",
    "function [xstar, n] = dichotomie(f, a, b, tol)\n",
    "```\n",
    "\n",
    "qui retourne une solution approchée $x^\\star$ de $f(x)=0$ dans l'intervalle $[a,b]$ sous la condition de sortie $|f(x)|< \\text{tol}$. On retournera aussi le nombre d'itérations $n$ nécessaire pour atteindre la condition de sortie. \n",
    "\n",
    "On retournera un message d'erreur si $f(a).f(b)\\geq 0$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8ff75e0e-83ea-4bfd-aae2-df8537d0ffa1",
   "metadata": {},
   "outputs": [],
   "source": [
    "function [xstar, n] = dichotomie(f, a, b, tol)\n",
    "    // ...\n",
    "endfunction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38c37d70-54d4-4b20-b5bd-14dce49ba887",
   "metadata": {},
   "source": [
    "Appliquer à\n",
    "\n",
    "$$\n",
    "f(x) = e^x - 2.\n",
    "$$\n",
    "\n",
    "avec $a=0$ et $b=1$, et vérifier que $x^\\star$ est proche de $\\ln(2)$.\n",
    "\n",
    "Comparer $n$ à l'estimation du cours\n",
    "\n",
    "$$\n",
    "n = \\text{int}\\Big[ \\log_2(\\frac{b-a}{\\text{tol}}) \\Big] + 1.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6489914b-582c-4d43-a831-050375d95e49",
   "metadata": {},
   "outputs": [],
   "source": [
    "// ...\n",
    "\n",
    "[xstar, n] = dichotomie(f, a, b, tol)\n",
    "\n",
    "mtlb_fprintf(\"[xstar, n] = %e, \\t %d\\n\", xstar, n);\n",
    "mtlb_fprintf(\"|xstar - ln(2)| = %e \\n\", abs(xstar - log(2)));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35a14107-0cb1-4d04-a762-6e4db01b8188",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "812d8a48-de98-4703-9fca-b937b23d24e1",
   "metadata": {},
   "source": [
    "---\n",
    "#### Exercice 2 - Point fixe, Newton, sécante et autres\n",
    "#### Mesure expérimentale de la vitesse de convergence"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b3dfe74-02d6-4742-b7d4-921fce918052",
   "metadata": {},
   "source": [
    "#### a) Méthode de point fixe de Picard\n",
    "\n",
    "Soit $g(x) = \\dfrac{x+2}{x+1}$. Vérifier sur papier que les points fixes de $g$ vérifient\n",
    "$f(x) = x^2-2 = 0$.\n",
    "\n",
    "Ecrire une fonction `Scilab`\n",
    "\n",
    "```\n",
    "function [xstar, n, err] = pointFixe(g, x0, tol, nmax)\n",
    "```\n",
    "\n",
    "qui met en oeuvre la méthode de point fixe de Picard\n",
    "\n",
    "$$\n",
    "x_{n+1} = g(x_n)\n",
    "$$\n",
    "\n",
    "partant de $x_0$, avec un nombre maximum d'itérations `nmax` (en cas de non-convergence), un critère d'arrêt\n",
    "\n",
    "$$\n",
    "|x_{n+1} - g(x_n)| < \\text{tol},\n",
    "$$\n",
    "\n",
    "et qui retourne le point fixe $x_n$ à l'itération de sortie $n$, ainsi que la résidu\n",
    "$\\text{err} = |x_{n+1} - g(x_n)|$. Appliquer à la fonction $g(x) = \\dfrac{x+2}{x+1}$\n",
    "en partant de $x_0=2$. Prendre $\\text{tol}=10^{-12}$, `nmax=100`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3f3e3a09-90f2-4e7e-83d8-95451748b867",
   "metadata": {},
   "outputs": [],
   "source": [
    "function [xstar, n, err] = pointFixe(g, x0, tol, nmax)\n",
    "    // ...\n",
    "endfunction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "927e4639-5024-492a-805c-12ca69f9954f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a533627c-15dd-466c-a051-cf23fd69ca0e",
   "metadata": {},
   "source": [
    "#### b) Méthode de Newton\n",
    "\n",
    "On rappelle la méthode de Newton vue en cours :\n",
    "\n",
    "$$\n",
    "x_{n+1} = x_n - \\frac{f(x_n)}{f'(x_n)}.\n",
    "$$\n",
    "\n",
    "Ecrire une fonction `Scilab`\n",
    "\n",
    "```\n",
    "function [xstar, n, residu] = Newton(ffprim, x0, tol, nmax)\n",
    "```\n",
    "\n",
    "qui met en oeuvre la méthode de Newton, partant de $x_0$, avec un nombre maximum d'itérations `nmax` (en cas de non-convergence), un critère d'arrêt\n",
    "\n",
    "$$\n",
    "|f(x_n)| < \\text{tol},\n",
    "$$\n",
    "\n",
    "et qui retourne le point fixe $x_n$ à l'itération de sortie $n$, ainsi que la résidu\n",
    "$\\text{residu} = |f(x_n)|$. La fonction `ffrim`\n",
    "\n",
    "```\n",
    "function [fx, fprimx] = ffprim(x)\n",
    "```\n",
    "retourne à la fois la valeur $f(x)$ et la valeur $f'(x)$.\n",
    "\n",
    "Appliquer à la fonction $f(x) = x^2-2$ en partant de $x_0=2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "bd27a10b-2aba-4d2e-b766-a635ae096597",
   "metadata": {},
   "outputs": [],
   "source": [
    "function [xstar, n, residu] = Newton(ffprim, x0, tol, nmax)\n",
    "    // ...\n",
    "endfunction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c4154fdf-33d2-4d45-a1d5-d1f97dc8d3f2",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9ef143e8-7867-436e-9b50-ec5bce12535e",
   "metadata": {},
   "source": [
    "#### Méthode de la sécante\n",
    "\n",
    "Pour éviter le calcul de la dérivée, il existe une méthode, proche de Newton, appelée méthode de la sécante, qui approche la dérivée par une formule de différence finie. La méthode de la sécante a besoin de 2 points d'initialisation $x_0$ et $x_1$,\n",
    "$x_0\\neq x_1$.\n",
    "\n",
    "L'itération $(n+1)$ s'écrit\n",
    "\n",
    "$$\n",
    "x_{n+1} = x_n - \\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}\\, f(x_n),\\qquad\n",
    "n\\geq 1.\n",
    "$$\n",
    "\n",
    "Ecrire une fonction `Scilab`\n",
    "\n",
    "```\n",
    "function [xstar, n, residu] = Secante(f, x0, x1, tol, nmax)\n",
    "```\n",
    "\n",
    "qui met en oeuvre la méthode de la sécante, partant de $x_0$ et $x_1$, avec un nombre maximum d'itérations `nmax` (en cas de non-convergence), un critère d'arrêt\n",
    "\n",
    "$$\n",
    "|f(x_n)| < \\text{tol},\n",
    "$$\n",
    "\n",
    "et qui retourne le point fixe $x_n$ à l'itération de sortie $n$, ainsi que la résidu\n",
    "$\\text{residu} = |f(x_n)|$.\n",
    "\n",
    "Appliquer à la fonction $f(x) = x^2-2$ en partant de $x_0=3$ et $x_1=2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "3ab95e84-98f9-4c1f-a243-86583fcb8a4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "function [xstar, n, residu] = Secante(f, x0, x1, tol, nmax)\n",
    "    // ...\n",
    "endfunction\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04827b1d-9a07-441b-ac8e-fb3caa2e81a2",
   "metadata": {},
   "source": [
    "#### Stockage/historique des itérés\n",
    "\n",
    "Modifier les fonctions ``pointFixe()``, ``Newton()`` et ``Secante`` de façon à conserver tous les itérés $x_n$, stockés dans un tableau ``xstor`` :\n",
    "\n",
    "```\n",
    "[xstar, n, err, xstor] = pointFixe(g, x0, tol, nmax)\n",
    "[xstar, n, residu, xstor] = Newton(ffprim, x0, tol, nmax)\n",
    "[xstar, n, residu, xstor] = Secante(f, x0, x1, tol, nmax)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05dd5f5d-96b9-4137-97c1-bdca04ea85b8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "78cc9f52-bba9-4b17-be51-63e10fec568e",
   "metadata": {},
   "source": [
    "#### Mesure expérimentale de la vitesse de convergence\n",
    "\n",
    "Soit $e_n = |x_n-x^\\star|$, où $x^\\star$ est la racine qui a été déterminée par la méthode itérative.\n",
    "\n",
    "La convergence de la méthode est d'ordre $p$ si \n",
    "\n",
    "$$\n",
    "e_{n+1} \\sim C\\, {e_n}^p\n",
    "$$\n",
    "\n",
    "pour une certaine constante $C>0$. En passant au logarithme, on a\n",
    "\n",
    "$$\n",
    "\\ln(e_{n+1}) \\sim \\ln(C) + p\\, \\ln(e_n).\n",
    "$$\n",
    "\n",
    "Notant $w_n = \\ln(e_n)$ et $K=\\ln(C)$, on a donc\n",
    "\n",
    "$$\n",
    "w_{n+1} = K + p\\, w_n.\n",
    "$$\n",
    "\n",
    "En déduire une méthodologie pour estimer numériquement $p$.\n",
    "\n",
    "Appliquer cette méthodologique pour évaluer $p$ pour les trois méthodes respectives : méthode de point fixe, méthode de Newton, et méthode de sécante.\n",
    "\n",
    "ps : on peut montrer théoriquement que la vitesse de convergence de la méthode de la sécante est le nombre d'or $\\phi = \\dfrac{1+\\sqrt{5}}{2}\\approx 1.62$. \n",
    "Encore lui !!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c29cac1e-a2dc-4ef7-bd3d-55ad8ddc77dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " ans = \n",
      "   1.6180340"
     ]
    }
   ],
   "source": [
    "(1+sqrt(5))/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d06a72ca-83fa-4623-b708-309d7e5d677b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scilab",
   "language": "scilab",
   "name": "scilab"
  },
  "language_info": {
   "file_extension": ".sci",
   "help_links": [
    {
     "text": "MetaKernel Magics",
     "url": "https://metakernel.readthedocs.io/en/latest/source/README.html"
    }
   ],
   "mimetype": "text/x-scilab",
   "name": "scilab",
   "version": "0.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}