Méthode de Newton

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

• Comprendre le principe géométrique de la méthode de Newton (tangente)
• Implémenter l'algorithme de Newton
• Identifier les conditions de convergence et les cas problématiques
• Apprécier la convergence quadratique de la méthode

Principe géométrique

La méthode de Newton, aussi appelée méthode de Newton-Raphson, est l'une des méthodes les plus puissantes pour résoudre $F(X) = 0$.

Idée fondamentale

Au lieu d'utiliser une sécante (droite passant par deux points de la courbe), on utilise la tangente à la courbe en un seul point.

Construction géométrique

Partant d'un point $X_1$, on trace la tangente à la courbe $y = F(X)$ au point $(X_1, F(X_1))$. Le point $X_2$ est l'abscisse où cette tangente coupe l'axe des $x$.

La pente de la tangente est la dérivée $F'(X_1)$, donc :

Dérivation de la formule

En résolvant pour $X_2$ :

Développement formel (Taylor)

On peut aussi dériver la formule de Newton par un développement de Taylor.

Raisonnement

Supposons que $X_n$ est une approximation de la racine $r$, avec $F(X_n) \neq 0$.

Cherchons une correction $\delta$ telle que :

Développement de Taylor au premier ordre

En imposant $F(X_{n+1}) = 0$ :

On retrouve bien la formule de Newton :

Algorithme

Algorithme : Méthode de Newton
Entrées : F, F' (fonctions), X1 (valeur initiale), δ (tolérance sur x), ε (tolérance sur F)
Sortie : X (approximation de la racine)

Poser X2 = X1
Calculer X1 = X1 - F(X1) / F'(X1)

Tant que (|X1 - X2| ≥ δ) ET (|F(X1)| ≥ ε) ET (F'(X1) ≠ 0) faire
  Poser X2 = X1
  Calculer X1 = X1 - F(X1) / F'(X1)
Fin Tant que

Retourner X = X1

Implémentation en Python

def newton(f, df, x1, tol_x=1e-6, tol_f=1e-10, max_iter=100):
  """
  Méthode de Newton.

  Paramètres:
      f : fonction dont on cherche la racine
      df : dérivée de f
      x1 : valeur initiale
      tol_x : tolérance sur x
      tol_f : tolérance sur f(x)
      max_iter : nombre maximum d'itérations

  Retourne:
      x : approximation de la racine
      iterations : liste des itérés
  """
  iterations = []
  x2 = x1

  for n in range(max_iter):
      fx1 = f(x1)
      dfx1 = df(x1)

      # Vérification de la dérivée
      if dfx1 == 0:
          raise ValueError(f"Dérivée nulle en x = {x1}")

      # Formule de Newton
      x_new = x1 - fx1 / dfx1

      iterations.append({
          'n': n + 1,
          'x': x1,
          'x_new': x_new,
          'f(x)': fx1,
          'erreur': abs(x_new - x1)
      })

      # Critères d'arrêt
      if abs(x_new - x1) < tol_x or abs(f(x_new)) < tol_f:
          return x_new, iterations

      x2 = x1
      x1 = x_new

  return x1, iterations

Exemple numérique

Appliquons la méthode de Newton à $F(X) = X^3 + X^2 - 3X - 3$ avec $X_1 = 2$.

La dérivée est : $F'(X) = 3X^2 + 2X - 3$

Résultat : Convergence en 3 itérations seulement !

Convergence quadratique

Définition

On dit qu'une méthode a une convergence quadratique si l'erreur à l'itération $n+1$ est proportionnelle au carré de l'erreur à l'itération $n$ :

où $e_n = |X_n - r|$ est l'erreur par rapport à la racine exacte $r$.

Conséquence pratique

À chaque itération, le nombre de décimales correctes double (approximativement).

Par exemple :

• Itération 1 : 1 décimale correcte
• Itération 2 : 2 décimales correctes
• Itération 3 : 4 décimales correctes
• Itération 4 : 8 décimales correctes

Avantages et inconvénients

Avantages

Inconvénients

Cas problématiques

La méthode de Newton n'est pas garantie de converger. Le graphique interactif ci-dessous présente quatre fonctions classiques illustrant différents comportements problématiques. Explorez chaque onglet et testez différents points de départ.

Problème 1 : Cycles stables (2-cycle)

Pour certaines fonctions, Newton peut entrer dans un cycle où les itérés alternent entre deux valeurs sans jamais converger.

Ce phénomène se produit quand la fonction de Newton $g(x) = x - F(x)/F'(x)$ satisfait $g(g(x)) = x$ pour certaines valeurs.

Problème 2 : Divergence oscillante

Pour $F(x) = x^{1/3}$ (racine cubique), la formule de Newton donne :

Chaque itération double la distance à la racine tout en changeant de signe : les itérés divergent vers $\pm\infty$ en oscillant.

Problème 3 : Trichotomie (arctan)

La fonction $F(x) = \arctan(x)$ présente trois comportements distincts selon $X_0$ :

La valeur critique $R \approx 1.3917$ est la solution de $(1 + x^2)\arctan(x) = 2x$.

Problème 4 : Dérivée nulle et région asymptotique

Si $F'(X_n) = 0$, la formule de Newton implique une division par zéro.

De plus, pour $X_0 > 1$, les itérés fuient vers $+\infty$ car la fonction décroît asymptotiquement vers 0 sans jamais l'atteindre.

Problème 5 : Racines multiples

Si $r$ est une racine de multiplicité $m > 1$ (c'est-à-dire $F(r) = F'(r) = \ldots = F^{(m-1)}(r) = 0$), la convergence devient linéaire au lieu de quadratique.

Critères de convergence

Condition suffisante (théorème)

Si $F$ est deux fois dérivable et si $X_1$ est suffisamment proche de la racine simple $r$, alors la méthode de Newton converge.

En pratique

Toujours tracer un graphique de la fonction avant d'appliquer la méthode pour :

1. Localiser approximativement les racines
2. Choisir un bon point de départ
3. Identifier les zones problématiques (extremums, asymptotes)

Résumé

Dans cette leçon, nous avons étudié la méthode de Newton :

1. Principe géométrique : intersection de la tangente avec l'axe des $x$

2. Formule : $X_{n+1} = X_n - \frac{F(X_n)}{F'(X_n)}$

3. Développement formel : correction $\delta = -F(X_n)/F'(X_n)$ issue du développement de Taylor

4. Convergence quadratique : le nombre de décimales correctes double à chaque itération

5. Avantages : très rapide, une seule valeur de départ

6. Inconvénients : nécessite la dérivée, sensible au point de départ

7. Cas problématiques : cycles stables, divergence oscillante, trichotomie, $F'(X) = 0$, racines multiples