Algorithme : la méthode de Newton
Énoncé
On cherche une valeur approchée de √(3), solution positive de l'équation f(x) = 0 avec f(x) = x² - 3.
a) Soit a un réel non nul. Montrer que la tangente à la courbe de f au point d'abscisse a coupe l'axe des abscisses au point d'abscisse a - (f(a))/(f'(a)).
b) La méthode de Newton part de x₀ = 2 et calcule xₙ₊₁ = xₙ - (f(xₙ))/(f'(xₙ)). Calculer x₁ et x₂ sous forme de fractions.
c) On considère le programme suivant.
```python
def f(x):
return x * x - 3
def fprime(x):
return 2 * x
def newton(x0, n):
valeurs = [x0]
x = x0
for k in range(n):
x = x - f(x) / fprime(x)
valeurs.append(x)
return valeurs
```
Que contient la liste renvoyée par `newton(2, 3)` ? L'instruction `print(newton(2, 3))` affiche `[2, 1.75, 1.7321428571428572, 1.7320508100147276]`. Comparer à √(3) ≈ 1,732 050 808.
Indice : La tangente en a a pour équation y = f(a) + f'(a)(x - a) : résous y = 0. Ici, f'(x) = 2x.
Correction
- Étape 1 : Ce qu'il faut voir. La méthode de Newton remplace la courbe par sa tangente, et l'équation f(x) = 0, qu'on ne sait pas résoudre, par une équation du premier degré. Le point où la tangente coupe l'axe des abscisses est plus proche de la solution que le point de départ : on recommence à partir de lui.
L'idée :
La tangente au point d'abscisse a a pour équation y = f(a) + f'(a)(x - a). Elle coupe l'axe des abscisses là où y = 0.
👉 Au programme, on se limite à des « cas favorables », comme celui-ci : une courbe régulière, et un point de départ assez proche de la solution.
- Étape 2 : a) On cherche x tel que f(a) + f'(a)(x - a) = 0. Ici f'(a) = 2a ≠ 0, puisque a ≠ 0 : on peut diviser par f'(a), ce qui donne x - a = -(f(a))/(f'(a)), soit x = a - (f(a))/(f'(a)).
x = a - (f(a))/(f'(a))
- Étape 3 : b) Avec f'(x) = 2x :
x₁ = 2 - (f(2))/(f'(2)) = 2 - (4 - 3)/4 = 2 - 1/4 = 7/4.
Puis f(7/4) = 49/16 - 3 = 1/16 et f'(7/4) = 7/2, donc :
x₂ = 7/4 - 1/16 × 2/7 = 7/4 - 1/56 = (98 - 1)/56 = 97/56.
x₁ = 7/4 = 1,75 ; x₂ = 97/56 ≈ 1,732 14
- Étape 4 : c) La liste « valeurs » commence par x₀. À chaque tour de boucle, « x » prend la valeur du terme suivant de la méthode, qui est ajouté à la fin de la liste par « append ». L'appel « newton(2, 3) » renvoie donc la liste [x₀, x₁, x₂, x₃].
On y retrouve x₁ = 1,75 et x₂ = 97/56 ≈ 1,732 142 857. Le terme x₃ ≈ 1,732 050 810 ne diffère de √(3) ≈ 1,732 050 808 que d'environ 2,4 × 10⁻⁹ : en trois étapes, on a déjà sept décimales exactes.
- Étape 5 : L'erreur classique :
Inverser le quotient et écrire xₙ₊₁ = xₙ - (f'(xₙ))/(f(xₙ)). Avec x₀ = 2, on obtiendrait 2 - 4/1 = -2 : on s'éloigne de √(3) au lieu de s'en rapprocher.
Autre oubli : la méthode a besoin de f'(xₙ) ≠ 0. Partir de x₀ = 0 ferait diviser par f'(0) = 0 : la tangente en 0 est horizontale, et elle ne coupe jamais l'axe des abscisses.
À retenir :
Newton : xₙ₊₁ = xₙ - (f(xₙ))/(f'(xₙ)), l'abscisse où la tangente en xₙ coupe l'axe. En Python, on range les valeurs successives dans une liste, créée avec x₀ et complétée par « append » à chaque tour.