AP-BAlgorithmes d’approximation

Méthode de Newton (tangente)

Idée directrice

L'énoncé donne une fonction $f$ dérivable et demande d'approcher une racine par la méthode de Newton : à partir d'un point $x_0$ , on suit la tangente jusqu'à l'axe des abscisses pour obtenir $x_1$ , et ainsi de suite. La suite de récurrence est $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ . L'arrêt se fait quand $|x_{n+1} - x_n| < \varepsilon$ (ou $|f(x_n)| < \varepsilon$ ). La convergence est quadratique — bien plus rapide que la dichotomie — mais exige $f'(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)=0$ » ; « Donner la formule de récurrence $x_{n+1}$ en fonction de $x_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 $\sqrt{3}$ en cherchant la racine positive de $f(x) = x^2 - 3$ sur $[1, 2]$ .

Rappeler la formule de récurrence de la méthode de Newton appliquée à cette fonction. Simplifier l'expression de $x_{n+1}$ en fonction de $x_n$ .
Écrire l'algorithme de Newton permettant de calculer une valeur approchée de $\sqrt{3}$ avec une précision $\varepsilon > 0$ donnée.
1. Identifier les données d'entrée et de sortie.
2. Quel risque existe-t-il si $f'(x_n) = 0$ ? Comment s'en prémunir ?
Donner la trace de l'algorithme pour $x_0 = 2$ et $\varepsilon = 10^{-4}$ (3 premières itérations). Compléter le tableau ( $n$ , $x_n$ , $f(x_n)$ , $x_{n+1}$ ).
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)=x^2-3$ sur $[1,2]$ , racine positive $\sqrt{3}$ .

$f'(x)=2x$ , donc $x_{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 (exemple $x_0=2$ , $\varepsilon=10^{-3}$ ) :

x=2 ; xnew=(2+3/2)/2=1,75 ; |1,75-2|=0,25 > eps
x=1,75 ; xnew≈1,73214 ; écart ≈0,0179
poursuite jusqu'à |xnew-x|≤eps ; On retourne une approximation de $\sqrt{3}\approx 1{,}732$

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

Équivalent Python (extrait).
```python
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-3))
```

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

$x_{n+1}=x_n-f(x_n)/f'(x_n)$ si $f'\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)$ explicitement avant d'écrire l'algorithme — la formule de récurrence en dépend.
Critère d'arrêt le plus courant au bac : $|x_{n+1} - x_n| < \varepsilon$ . Parfois $|f(x_n)| < \varepsilon$ .
Toujours vérifier $f'(x_n) \neq 0$ pour éviter la division par zéro (signaler dans l'algorithme).
Newton converge en $O(\log \log(1/\varepsilon))$ itérations (quadratique), dichotomie en $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 $x_{n+1} = x_n - f(x_n)/f'(x_n)$ sans substituer $f$ et $f'$ ). (2) Utiliser $f(x) = 0$ comme critère d'arrêt au lieu de $|x_{n+1}-x_n| < \varepsilon$ : en virgule flottante, $f(x)$ n'atteint jamais exactement 0. (3) Mauvais choix de $x_0$ qui fait diverger la suite (ex. $x_0$ loin de la racine sur une fonction non monotone).

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