====== Méthode de Newton ======

La méthode de Newton consiste à chercher une **racine de fonction**. La seule condition est que la fonction soit **dérivable** sur tout l'intervalle considéré. C'est une méthode **très efficace**.

===== Exemple =====

Considérons la fonction $f: x \mapsto 0,5\,x^4 - 2\,x^3 + x^2 + x +1$

===== Tracé de la fonction =====

Commençons par tracer la fonction. On peut bien sûr utiliser un grapheur comme [[https://www.desmos.com/calculator/pduemy885m|desmos]]. Mais on peut aussi tracer la courbe avec Python et [[nsi:modules:matplolib_pyplot|matplotlib.pyplot]].

<code python linenums>
import matplotlib.pyplot as plt
import numpy as np

def f(x):
    return 0.5*x**4 - 2*x**3 + x**2 + x + 1

# tracé du graphique de f sur [-1;3.5]
liste_x = np.linspace(-1, 3.5 , num = 100) # 100 valeurs de x sur [-1;3.5]
liste_y = [f(x) for x in liste_x] # valeurs y correspondantes

plt.plot(liste_x, liste_y)
</code>

===== Principe de la méthode =====

Il s'agit //en gros// de suivre le sens de la pente. La dérivée d'une fonction me dit comment la fonction varie. Par exemple, supposons que $x = 1$, alors $y = f(1) = 1,5$. Si je veux diminuer $y$, je dois diminuer $f(x)$ et pour savoir comment diminuer $f(x)$ j'ai besoin de $f'(x)$.

$f'(x) = 2\,x^3 - 6\,x^2 + 2\,x + 1 \Rightarrow f'(1) = -1 < 0$

On voit donc que $f$ décroît en $x = 1$ et donc pour diminuer $f(x)$ il faut augmenter $x$.

<WRAP box>
La figure ci-dessous vous montre la situation pour l'exemple $x_0 = 1$, $f(1) = 1,5$ et $f'(1) = -1$.

{{ :nsi:tds:maths:methode_newton.png?direct&400 |}}

L'équation de la tangente est $\mathcal{T_1}: y = -1\times (x - 1) + 1,5$

On veut $y = 0$ donc $x_1 = x = 1 - \frac{1,5}{-1}$.

Si on généralise, ce sera : $x_{1} = x_{0} - \frac{f\left(x_{0}\right)}{f'\left(x_{0}\right)}$
</WRAP>

<WRAP tip>
**Retenez :** j'essaie une racine $x_0$.

Si elle n'est pas suffisamment bonne, je change de valeur de $x$ en prenant $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$ et je recommence.
</WRAP>

===== Calcul de la dérivée =====

Plutôt que calculer $f'(x)$ de façon exacte, on va se contenter d'une approximation. On se fixe un $\varepsilon$ petit, par exemple $\varepsilon = 1E-6$, et on calcule :

$$f'(x) \approx \frac{f(x+\varepsilon) - f(x)}{\varepsilon}$$


<code python>
EPSILON = 1e-6

# définition de la dérivée approximative
def der_f(fonction, x):
    '''
    x: réel, antécédent de la fonction
    fonction: fonction de x
    renvoie une approximation de fonction'(x)
    '''
    return (fonction(x + EPSILON) - fonction(x)) / EPSILON
</code>

===== Algorithme =====

<code lang-none linenums>
ENTRÉES : réel x0, fonction f, réel positif seuil_erreur
SORTIE : estimation d'une racine x de la fonction f
DÉBUT
    soit x = x0
    TANT QUE l'écart entre f(x) et 0 est supérieur à seuil_erreur RÉPÉTER
        x prend la valeur x - f(x) / f'(x)
    FIN
    RENVOYER x
FIN
</code>

===== À vous =====

Reprenons ce que nous avons déjà :

<code python linenums>
EPSILON = 1e-10

# définition de la dérivée approximative
def der_f(fonction, x):
    """
    x: réel, antécédent de la fonction
    fonction: fonction de x
    renvoie une approximation de fonction'(x)
    """
    return (fonction(x + EPSILON) - fonction(x)) / EPSILON
    
# Votre travail
def newton(x0, fonction, seuil_erreur = 1e-5):
    """
    x0: réel, valeur initiale de la recherche
    fonction: fonction de x
    seuil_erreur: réel positif, par défaut = 1e-5
      si écart entre f(x) et 0 < seuil_erreur, on considère x comme une racine
    renvoie une racine approximative de la fonction
    """
    
    # à vous

# Exemple d'utilisation
def f(x):
    return 0.5*x**4 - 2*x**3 + x**2 + x + 1

r = newton(1, f)
print(f"Une racine approximative de f est {r}")
</code>

===== Autres exemples =====

Modifiez le code pour résoudre $3x\cdot \exp(-x) = 1$