Masar
Masar
Bac Tunisie
Informatique/AP-B
Entraîner la reconnaissance
AP-BAlgorithmes d’approximation

Méthode de Newton (tangente)

Idée directrice

L'énoncé donne une fonction ff dérivable et demande d'approcher une racine par la méthode de Newton : à partir d'un point x0x_0, on suit la tangente jusqu'à l'axe des abscisses pour obtenir x1x_1, et ainsi de suite. La suite de récurrence est xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}. L'arrêt se fait quand ∣xn+1−xn∣<ε|x_{n+1} - x_n| < \varepsilon (ou ∣f(xn)∣<ε|f(x_n)| < \varepsilon). La convergence est quadratique — bien plus rapide que la dichotomie — mais exige f′(xn)≠0f'(x_n) \neq 0.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Écrire un algorithme utilisant la méthode de Newton pour approcher la solution de f(x)=0f(x)=0 » ; « Donner la formule de récurrence xn+1x_{n+1} en fonction de xnx_n » ; « Quel est le critère d'arrêt de l'algorithme ? » ; « Donner la trace pour les trois premières itérations » ; « Comparer la convergence de Newton et de la dichotomie »

Sujet principal

Exercice — dans l'esprit des sujets du bac

4 questionsCorrigé masqué

On veut approcher 3\sqrt{3} en cherchant la racine positive de f(x)=x2−3f(x) = x^2 - 3 sur [1,2][1, 2].

  1. Rappeler la formule de récurrence de la méthode de Newton appliquée à cette fonction. Simplifier l'expression de xn+1x_{n+1} en fonction de xnx_n.
  2. Écrire l'algorithme de Newton permettant de calculer une valeur approchée de 3\sqrt{3} avec une précision ε>0\varepsilon > 0 donnée.
    1. Identifier les données d'entrée et de sortie.
    2. Quel risque existe-t-il si f′(xn)=0f'(x_n) = 0 ? Comment s'en prémunir ?
  3. Donner la trace de l'algorithme pour x0=2x_0 = 2 et ε=10−4\varepsilon = 10^{-4} (3 premières itérations). Compléter le tableau (nn, xnx_n, f(xn)f(x_n), xn+1x_{n+1}).
  4. Comparer la rapidité de convergence de Newton et de la dichotomie. Quel inconvénient majeur présente Newton ?
Voir la correction commentéeAprès avoir posé votre démarche

1. Formule de Newton pour f(x)=x2−3f(x)=x^2-3 sur [1,2][1,2], racine positive 3\sqrt{3}.

f′(x)=2xf'(x)=2x, donc xn+1=xn−xn2−32xn=xn2+32xn=xn+3/xn2x_{n+1}=x_n-\dfrac{x_n^2-3}{2x_n}=\dfrac{x_n}{2}+\dfrac{3}{2x_n}=\dfrac{x_n+3/x_n}{2} (moyenne arithmético-harmonique, aussi méthode de Héron).

2. Algorithme. TDOL — objets locaux :

  • x, xnew : réel — itéré courant et suivant
  • x0, eps : réel — donnée initiale et précision (Type/Nature : paramètres d'entrée)

DEF PROC Newton(x0, eps : réel)
Variables x, xnew : réel
Début
  x ← x0
  xnew ← (x + 3/x) / 2
  TantQue ABS(xnew - x) > eps faire
    x ← xnew
    xnew ← (x + 3/x) / 2
  FinTantQue
  Écrire(xnew)
Fin

3. Trace d'exécution (x0=2x_0=2, ε=10−4\varepsilon=10^{-4}) :

nnxnx_nf(xn)=xn2−3f(x_n)=x_n^2-3xn+1x_{n+1}∣xn+1−xn∣\lvert x_{n+1}-x_n\rvert
0211,750,25
11,750,06251,7321430,0179
21,7321430,0003191,7320519,2×10−5<ε9{,}2\times10^{-5}<\varepsilon → arrêt


On retourne x3≈1,732051x_3\approx1{,}732051, soit 3\sqrt3 à 10−410^{-4} près en trois itérations (valeur exacte 1,7320508…).

Contrainte : x≠0x\neq 0 (division par f′(x)f'(x)) ; eps dans ]0 ; 1]. Critère d'arrêt : ∣xn+1−xn∣<ε|x_{n+1}-x_n|<\varepsilon, pas f(x)=0f(x)=0 exact.

Équivalent Python (extrait).

def newton(x0, eps):
    x = x0
    xnew = (x + 3/x) / 2
    while abs(xnew - x) > eps:
        x = xnew
        xnew = (x + 3/x) / 2
    return xnew
print(newton(2.0, 1e-4))

4. Newton contre dichotomie. La dichotomie divise l'intervalle par 2 à chaque étape : pour passer d'une largeur 1 à 10−410^{-4} il lui faut ⌈log⁡2104⌉=14\lceil\log_2 10^4\rceil=14 itérations, et elle converge toujours dès que ff change de signe. Newton double environ le nombre de décimales exactes à chaque itération (convergence quadratique) : trois itérations ici. Son inconvénient majeur : il exige la dérivée et un bon point de départ ; si f′(xn)f'(x_n) est nul ou très petit, la tangente est presque horizontale et l'itéré suivant part très loin — l'algorithme peut diverger, ce que la dichotomie ne fait jamais.

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 01

Drill AP-B.1 — méthode de Newton

1 questionCorrigé masqué

Donner la formule d'itération de la méthode de Newton pour approcher une racine de f.

Voir la correction commentéeAprès avoir posé votre démarche

xn+1=xn−f(xn)/f′(xn)x_{n+1}=x_n-f(x_n)/f'(x_n) si f′≠0f'\neq 0. TDOL : x réel. Type/Nature : itéré.

DEF FN IterNewton(x : réel) : réel
Début
  Retourner x - f(x)/f'(x)
Fin

On retourne le nouvel itéré ; convergence quadratique près de la racine.

Méthode / Automatismes
  • Calculer f′(x)f'(x) explicitement avant d'écrire l'algorithme — la formule de récurrence en dépend.
  • Critère d'arrêt le plus courant au bac : ∣xn+1−xn∣<ε|x_{n+1} - x_n| < \varepsilon. Parfois ∣f(xn)∣<ε|f(x_n)| < \varepsilon.
  • Toujours vérifier f′(xn)≠0f'(x_n) \neq 0 pour éviter la division par zéro (signaler dans l'algorithme).
  • Newton converge en O(log⁡log⁡(1/ε))O(\log \log(1/\varepsilon)) itérations (quadratique), dichotomie en O(log⁡(1/ε))O(\log(1/\varepsilon)).
  • Si l'énoncé parle de tangente, c'est Newton ; si de bissection ou couper en deux, c'est la dichotomie.
Pièges classiques

Pièges fréquents : (1) Oublier de simplifier la formule de récurrence (écrire xn+1=xn−f(xn)/f′(xn)x_{n+1} = x_n - f(x_n)/f'(x_n) sans substituer ff et f′f'). (2) Utiliser f(x)=0f(x) = 0 comme critère d'arrêt au lieu de ∣xn+1−xn∣<ε|x_{n+1}-x_n| < \varepsilon : en virgule flottante, f(x)f(x) n'atteint jamais exactement 0. (3) Mauvais choix de x0x_0 qui fait diverger la suite (ex. x0x_0 loin de la racine sur une fonction non monotone).

Variantes rencontrées : Newton appliqué à f(x)=x2−af(x) = x^2 - a donne la méthode de Héron pour a\sqrt{a} (voir AP-D). Parfois l'énoncé demande de montrer la convergence en calculant ∣xn+1−α∣|x_{n+1} - \alpha| en fonction de ∣xn−α∣2|x_n - \alpha|^2. On rencontre aussi f(x)=ex−2f(x) = e^x - 2 ou f(x)=ln⁡(x)−1f(x) = \ln(x) - 1.