TP4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programmation Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[**Paul Liautaud**](https://paulliautaud.github.io) à [Sorbonne Université](http://www.sorbonne-universite.fr/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Zéro de fonctions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"ch:newton\"></div>\n",
    "\n",
    "Le but de cette série d'exercices est de déterminer les zéros de manière approchée d'une fonction notamment par la méthode de Newton et de la dichotomie. Cela permet en particulier de trouver des solutions approchées d'équations non linéaires. Ces méthodes sont fondamentales autant d'un point de vue numérique qu'analytique.\n",
    "\n",
    ">**Concepts abordés:**\n",
    ">* méthode de Newton en une et plusieurs dimensions\n",
    ">* matrice jacobienne\n",
    ">* attracteur de la méthode de Newton\n",
    ">* ensemble fractal\n",
    ">* optimisation par parallélisation\n",
    ">* équation différentielle non linéaire\n",
    ">* différences finies\n",
    "\n",
    "\n",
    "\n",
    "La réesolution analytique des éequations de la forme $f(x) = 0$ n’est pas toujours possible. Pensez par exemple à l’équation $\\sin(x) − \\ln(x) = 0$.\n",
    "En revanche, des théorèmes comme celui des valeurs intermédiaires, peuvent nous garantir l’existence d’au moins une solution.\n",
    "Il s’agit alors de construire des algorithmes qui soient capables de nous donner une approximation numérique d’une ou de la solution avec une précision arbitraire $\\varepsilon$.\n",
    "Ce TP expose deux méthodes essentielles :\n",
    "* La méthode de recherche d’un zéro par dichotomie. Elle est efficace et ses conditions d’utilisation ne sont pas trop contraingnantes.\n",
    "* La méthode de Newton qui converge très rapidement lorsque les conditions d’utilisation, drastiques, sont vérifiées."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 1 - Méthode de la dichotomie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considère $f$ une application continue sur un intervalle $[a;b]$ tels que $f(a)f(b) \\leq 0$. Le théorème des valeurs intermédiaires assure alors que l’application $f$ s’annule sur l’intervalle $[a, b]$.\n",
    "\n",
    "L’algorithme de recherche par dichotomie s’appuie sur une démonstration effective d’existence d’un zéro dans le sens où cette démonstration permet d’établir une valeur $x_0$ telle que $f(x_0) = 0$ avec une précision arbitraire. Le principe consiste à construire par récurrence une suite de segments emboîtés $[a_n,b_n]$ tels que :\n",
    "* $f$ s’annule sur les segments $[a_n, b_n]$,\n",
    "* Pour tout $n$ : $$b_{n+1} −a_{n+1} = \\frac{b_n −a_n}{2}$$\n",
    " i.e. la longueur de l’intervalle $[a_{n+1},b_{n+1}]$ est donc la moitié de celle de $[a_n,b_n]$.\n",
    " \n",
    "_Initialisation :_ <br>\n",
    "On définit $a_0 = a$ et $b_0 = b$. <br>\n",
    "_Induction :_ <br>\n",
    "On suppose $a_n$ et $b_n$ construits. On pose alors $m = \\frac{a_n + b_n}{2}$.\n",
    "* Si $f(a_n)f(m) \\leq 0$ on pose alors : $a_{n+1} = a_n, bn+1 = m$;\n",
    "* Si $f(a_n)f(m)>0$ on pose alors : $a_{n+1} = m, bn+1 =bn$.\n",
    "\n",
    "i.e. si l’application $f$ change de signe aux extrémités de l’intervalle de gauche, celui-ci devient le nouveau segment $[a_{n+1} , b_{n+1}]$, sinon on choisit l’intervalle de droite comme nouveau segment $[a_{n+1},b_{n+1}]$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Approximation de $\\sqrt{2}$\n",
    "\n",
    "On se propose dans un premier temps d'implémenter la méthode de dichotomie pour trouver une approximation de $\\sqrt{2}$, en introduisant $$f_1 : x \\mapsto x^2 - 2,$$ que l'on étudie sur l'intervalle $[0;2]$.\n",
    "\n",
    "**a)** Définir la fonction $f_1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Implémenter une fonction `dichotomie(f,a,b,e)` qui recherche le zéro d'une fonction $f$ sur l'intervalle $[a;b]$ et avec précision `e`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** Résoudre numériquement l'équation $x^2 - 2 = 0$ par l'appel de la fonction `dichotomie` pour différentes précisions `e`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)** Comparer à la valeur de $\\sqrt{2}$ donnée par Python. Conclure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 D'autres approximations\n",
    "\n",
    "On souhaite maintenant déterminer des approximations numériques des solutions de l'équation $x^2 + 6x +1 = 0$ à $10^{-12}$ près gr$ace à cette fonction `dichotomie`, en choisissant habilement les valeurs des arguments `a` et `b`. Pour cela :\n",
    "\n",
    "**a)** Définir judicieusement une fonction `f2`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Représenter graphiquement `f2` sur l'intervalle $[-7,1]$, le tracé de la droite $y=0$ ainsi que des tracés sur des intervalles bien choisis (permettant d'évaluer les zéros de la fonction).\n",
    "\n",
    "**Indication :** On pourra utiliser la fonction [`axhline`](https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.axhline.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** En déduire les bornes de deux intervalles incluant les solutions de l'équation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)** Déterminer alors les approximations numériques recherchées par l'appel de la fonction `dichotomie`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**e)** On pourrait montrer que le nombre d'itérations prévues jusqu'à convergence pour la fonction `dichotomie` est de $$\\left\\lfloor \\log_2\\left(\\frac{b-a}{\\varepsilon}\\right)\\right\\rfloor,$$\n",
    "où $\\varepsilon >0$ est la précision souhaitée dans l'approximation de la racine.\n",
    "\n",
    "Proposer alors une fonction `dichotomie_iteration` basée sur `dichotomie` et permet de calculer exactement le nombre d'itérations effectuées dans la mise en oeuvre de `dichotomie`. Tester `dichotomie_iteration` et conclure avec une représentation graphique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3. Les soucis commencent..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considère maintenant l'application polynomiale $$f_3 : x \\in \\mathbb R \\mapsto 10^{-8}x^2 - \\frac{4}{5}x + 10^{-8}.$$\n",
    "\n",
    "Les racines théoriques de $f_3$ sont données par : $$x_1 = 2\\frac{10^8}{5} - \\sqrt{4\\frac{10^{16}}{25} - 1} \\quad x_2 = 2\\frac{10^8}{5} + \\sqrt{4\\frac{10^{16}}{25} - 1}.$$\n",
    "\n",
    "*Remarque :* On peut noter que les deux racines sont positives et proches de $0$ et $8\\times 10^{7}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)** Déterminer comme précédemment des valeurs approchées de la racine de $f_3$ comprise dans $[0;1]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** *Pour cette question, il vous sera certainement utile d'utiliser le boutton d'interruption de cellule* <br>\n",
    "Rechercher avec `dichotomie` une approximation numérique de la seconde racine de $f_3$, avec précision minimale $\\varepsilon = 10^{-12}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** Afin d'analyser le problème, on propose de modifier la fonction `dichotomie` pour coder une fonction `dichotomie_analyse` qui au début de chaque itération affiche les différentes valeurs utilisées. Lancer alors votre recherche avec `dichotomie_analyse` et expliquer l'origine du problème."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)** Pour s'assurer de contourner ce problème, on propose alors de modifier `dichotomie` en `dichotomie_bis` qui :\n",
    "- calcule le nombre théorique d'itérations pour atteindre la précisions souhaitée,\n",
    "- arrête le calcul lorsque la précision souhaitée est atteinte ou que le nombre d'itérations théorique est atteint.\n",
    "\n",
    "Tester alors cette fonction sur l'expemple pathologique suivant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 Une autre méthode\n",
    "\n",
    "Une autre méthode de recherche des solutions d'une équation de la forme $f(x)=0$ sur un intervalle $[a;b]$ consiste à \"balayer\" l'intervalle à pas constant. À chaque fois qu'un changement de signe est detecté entre deux valeurs successives, c'est qu'un zéro se chache entre ces dernières.\n",
    "\n",
    "**a)** Proposer une fonction `balayage(f,a,b,n)` d'arguments une fonction $f$ et les bornes d'un intervalle $[a;b]$ sur lequel on cherchera les potentiels racines de $f$ sur $n$ subdivisions de même longueur. `balayage` renverra une liste de couples de points entre lesquels se trouvent ces racines."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Tester alors `balayage` sur $f_4(x) = 40000x^5 - 12000x^4 - 2700x^3 + 740x^2 + 51x -9$ sur l'intervalle $[-1;1]$ subdivisé en $n=100$ intervalles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** Proposer une amélioration `balayage_pro` de `balayage` qui précise les intervalles auxquels appartiennent les zéros de $f_4$ en balayant une seconde fois, avec le même nombre de subdivisions, sur chacun des intervalles mis en évidence au premier passage."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 2 - Méthode de Newton en une dimension"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En une dimension, la méthode de Newton consiste à trouver une solution approchée d'une seule équation. Cette équation peut être mise sous la forme générale $F(x)=0$ où $F:\\mathbb{R}\\to\\mathbb{R}$ est une fonction assez régulière, donc le but est de trouver un zéro de la fonction $F$. L'équation $F(x)=0$ est équivalente (si $F^\\prime(x) \\neq 0$) à l'équation $G(x)=x$ où $G$ est la fonction définie par:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "G(x) = x - \\frac{F(x)}{F^\\prime(x)} \\,.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La méthode de Newton consiste à trouver un point fixe de $G$, *i.e.* résoudre $G(x)=x$ par itérations successives:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "x_{i+1} = G(x_i) = x_i - \\frac{F(x_i)}{F^\\prime(x_i)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "à partir d'une valeur initiale $x_0\\in\\mathbb{R}$.\n",
    "Lorsque la suite $(x_i)_ {i\\in\\mathbb{N}}$ converge, alors la limite $x$ est une solution de $G(x)=x$ donc de $F(x)=0$.\n",
    "\n",
    "**a)**\n",
    "Écrire une fonction `newton1d(F, DF, x0, eps=1e-10, N=1000)` qui pour une fonction $F$, sa dérivée $F^\\prime$ et une valeur initiale $x_0$ données calcule les itérations de Newton jusqu'à ce que  $|F(x_{i})| < \\varepsilon$ et retourne $x_{i}$. Si $N$ itérations n'ont pas suffi à atteindre ce critère de convergence, alors retourner une erreur.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**b)**\n",
    "En utilisant la fonction définie précédemment, trouver une solution approchée de l'équation $e^{-x} = x$.\n",
    "\n",
    "**Réponse:**\n",
    "La solution est approximativement donnée par $x=0.56714$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**c)**\n",
    "Sans utiliser les fonctions `sqrt` et `log` ni les puissances fractionnaires, définir une fonction `racine(x,n)` qui calcule $\\sqrt[n]{x}$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Parfois, la dérivée de la fonction $F$ n'étant pas calculable analytiquement, il est alors nécessaire de l'approcher numériquement:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "F^\\prime(x_i) \\approx \\frac{F(x_i) - F(x_{i-1})}{x_i-x_{i-1}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ce qui mène à la méthode de la sécante:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "x_{i+1} =  x_i - F(x_i) \\frac{x_i-x_{i-1}}{F(x_i) - F(x_{i-1})} = \\frac{x_{i-1}F(x_{i})-x_{i}F(x_{i-1})}{F(x_{i})-F(x_{i-1})}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "où $x_0$ et $x_1$ doivent être choisis.\n",
    "\n",
    "**d)**\n",
    "Écrire une méthode `secant1d(F, x0, x1, eps=1e-10, N=1000)` implémentant la méthode de la sécante et la tester sur l'exemple précédent.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bonus\n",
    "# Exercice 3 - <span style=\"color:red\">!</span> Méthode de Newton en plusieurs dimensions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"exer:newton-Rn\"></div>\n",
    "\n",
    "La méthode de Newton en une dimension est facilement généralisable à plusieurs dimensions pour résoudre des équations de la forme $F(\\boldsymbol{x})=\\boldsymbol{0}$ où $F:\\mathbb{R}^n \\to \\mathbb{R}^n$ est une fonction assez régulière. Conceptuellement la méthode est identique: l'équation $F(\\boldsymbol{x})=\\boldsymbol{0}$ est équivalente à $G(\\boldsymbol{x})=\\boldsymbol{x}$ avec la fonction $G$ définie par:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "G(\\boldsymbol{x}) = \\boldsymbol{x} - \\big(F^\\prime(\\boldsymbol{x})\\big)^{-1} F(\\boldsymbol{x})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "où $F^\\prime(\\boldsymbol{x})$ désigne la matrice jacobienne de taille $n \\times n$ de $F$ en $x$.\n",
    "Ainsi les itérations de Newton s'écrivent:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\boldsymbol{x}_{i+1} = \\boldsymbol{x}_{i} - \\big(F^\\prime(\\boldsymbol{x}_i)\\big)^{-1} F(\\boldsymbol{x}_i)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)**\n",
    "Écrire une fonction `newton(F, DF, x0, eps=1e-12, N=10000)` implémentant la méthode de Newton en plus d'une dimension.\n",
    "\n",
    "**Indication:**\n",
    "Pour avoir une performance optimale, il ne faut pas inverser la matrice jacobienne mais résoudre un système linéaire avec $F(\\boldsymbol{x}_i)$ comme second membre.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**b)**\n",
    "Utiliser la fonction précédente pour résoudre le système suivant:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "\\cos(x) & =\\sin(y)\\,, & e^{-x} & =\\cos(y)\\,.\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**Réponse:**\n",
    "Une solution est approximativement donnée par $x=0.58853$ et $y=0.98226$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 4 - <span style=\"color:red\">!</span> Attracteur de la méthode de Newton"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le but de cet exercice est de résoudre l'équation $z^3 = 1$ dans le plan complexe à l'aide de la méthode de Newton et d’analyser vers laquelle des trois racines de l'unité la méthode va converger suivant le choix du point initial $z_0$.\n",
    "\n",
    "**a)**\n",
    "Si nécessaire adapter la fonction `newton1d` pour que celle-ci s'applique également aux nombres complexes et la tester pour résoudre $z^3 = 1$ à partir de différentes valeurs de $z_0$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**b)**\n",
    "Déterminer pour chaque $z_0 \\in \\big\\{x_0+iy_0: x_0\\in[-3,3] \\; \\text{et} \\; y_0\\in[-3,3]\\big\\}$ vers quelle racine de l'unité la méthode de Newton va converger. Représenter graphiquement cet ensemble.\n",
    "\n",
    "**Indication:**\n",
    "La fonction `meshgrid` de Numpy peut être utile pour construire la matrice correspondant à l'ensemble des $z_0$.\n",
    "\n",
    "**Réponse:**\n",
    "Le graphique donnant la convergence de $z_0$ vers une des trois racines est le suivant:\n",
    "\n",
    "<center><img src=\"https://python.guillod.org/fig/newton-z3.png\" style=\"width:90%;max-width:600px;\"></center>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**c)**\n",
    "<span style=\"color:red\">!</span> La méthode précédente a le désavantage de procéder séquentiellement au calcul pour chaque valeur de $z_0$, ce qui rend cette évaluation assez lente. Proposer une nouvelle implémentation permettant de calculer parallèlement toutes les valeurs de $z_0$ en utilisant les indexages Numpy.\n",
    "\n",
    "**Indication:**\n",
    "Pour encore plus de rapidité, les itérations de Newton de $F(z)=z^3-1$ peuvent être calculées à la main:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "z_{n+1} = \\frac{1}{3z_n^2} + \\frac{2z_n}{3} \\,.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "<!-- --- end exercise --- -->\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "<!-- --- begin exercise --- -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 5 - <span style=\"color:red\">!!</span> Équation différentielle non linéaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"exer:newton-nonlinear\"></div>\n",
    "\n",
    "Le but est de résoudre l'équation différentielle suivante avec conditions de valeurs limites:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "u^{\\prime\\prime}(x)+u^{3}(x) & = \\sin(x) \\,, & u(0) & = u(2\\pi) = 0 \\,,\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "sur l'intervalle $[0,2\\pi]$. Cette équation est un modèle simplifié pour une équation de Schrödinger non linéaire.\n",
    "\n",
    "La méthode employée est celle des différences finies qui consistent à chercher les valeurs de $u$ aux points $x_n = \\frac{2\\pi n}{N}$ pour $n=0,1,\\dots,N$. Les inconnues sont alors les nombres $u_n = u(x_n)$ et forment un vecteur de dimension $N+1$. La méthode des différences finies consiste à approximer la dérivée seconde par:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "u^{\\prime\\prime}(x) \\approx \\frac{u(x+h)-2u(x)+u(x-h)}{h^{2}} \\,,\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "lorsque $h$ est petit.\n",
    "En prenant $h=\\frac{2\\pi}{N}$, alors:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "u^{\\prime\\prime}(x_n) \\approx \\frac{u_{n+1}-2u_n+u_{n-1}}{h^{2}} \\,,\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "et donc l'équation initiale s'approxime par:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "\\frac{u_{n+1}-2u_{n}+u_{n-1}}{h^{2}}+u_{n}^{3} & = \\sin(x_{n}) \\,, & u_{0} & = u_{N} = 0 \\,,\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "pour $n=1,2,\\dots,N-1$.\n",
    "Cette équation peut être vue comme une équation du type $F(\\boldsymbol{u})=\\boldsymbol{0}$ pour $\\boldsymbol{u} = (u_n)_ {n=0}^{N+1}$ et donc être résolue par la méthode de Newton.\n",
    "\n",
    "**a)**\n",
    "Montrer l'approximation suivante:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "u^{\\prime\\prime}(x) = \\frac{u(x+h)-2u(x)+u(x-h)}{h^{2}} + O(h^2) \\quad \\text{lorsque} \\quad h \\to 0 \\,.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "**Indication:**\n",
    "Utiliser le théorème de Taylor.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "**b)**\n",
    "Définir un vecteur `x` représentant les $N+1$ points équidistribués dans $[0,2\\pi]$ et `h` la distance entre les points, avec par exemple $N=200$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**c)**\n",
    "Définir une fonction `F(u)` représentant la fonction $F:\\mathbb{R}^{N+1} \\to \\mathbb{R}^{N+1}$ permettant de mettre l'équation approchée sous la forme $F(\\boldsymbol{u})=\\boldsymbol{0}$.\n",
    "\n",
    "**Indication:**\n",
    "Pour avoir une implémentation rapide, il est impératif pour construire $F$ d'utiliser non pas une boucle, mais le slicing Numpy.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**d)**\n",
    "Définir une fonction `DF(u)` représentant la jacobienne de la fonction précédente.\n",
    "\n",
    "**Indication:**\n",
    "La jacobienne est la dérivée de $F(\\boldsymbol{u})=F(u_0,u_1,\\dots,u_{N})$ par rapport à $\\boldsymbol{u} = (u_0,u_1,\\dots,u_{N})$, c'est-à-dire:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "F^{\\prime}(\\boldsymbol{u})=\\begin{pmatrix}\\partial_{0}F(\\boldsymbol{u}) & \\partial_{1}F(\\boldsymbol{u}) & \\partial_{2}F(\\boldsymbol{u}) & \\cdots & \\partial_{N-1}F(\\boldsymbol{u}) & \\partial_{N}F(\\boldsymbol{u})\\end{pmatrix}\\,,\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "et peut se calculer explicitement à la main.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "**e)**\n",
    "Utiliser la fonction `newton` définie précédemment pour calculer une solution approchée de l'équation. En changeant de valeurs initiales, est-il possible de trouver d'autres solutions ?\n",
    "\n",
    "**Indication:**\n",
    "Essayer avec la donnée initiale $u_0(x) = (1+k)\\sin(kx)$ pour $k=1,2,3,4$ comme point de départ de la méthode de Newton.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}