Loading [MathJax]/jax/output/CommonHTML/jax.js
Back
Close

Recueil d'exercices pour apprendre Python au lycée

M_C
300.7K views

La méthode de Newton

Difficulté : Moyenne à difficile
Prérequis : Notion de dérivée

Le but de cette page est de présenter la méthode de Newton pour rechercher les solutions d'une équation de la forme f(x)=0. Cette méthode ne fonctionne pas toujours parfaitement (selon la situation qu'on pourrait souvent contourner mais nous n'en parlerons pas ici) mais quand elle fonctionne, elle donne rapidement la solution. Pour donner un ordre d'idée grossier, une recherche par dichotomie (qui est déjà efficace) divise l'erreur par 2 alors que dans les cas favorables, la méthode de Newton va quasiment doubler le nombre de décimales justes. Autrement dit, il faut beaucoup moins de calcul pour obtenir le résultat ce qui est indispensable en programmation.

Calcul du nombre dérivé (version améliorée)

Pour utiliser la méthode de Newton, nous aurons besoin d'avoir le nombre dérivé d'une fonction. Une première façon de faire est d'utiliser une conséquence de la définition du nombre dérivé : f(a)f(a+h)f(a)h.

Or une petite astuce toute simple donne de bien meilleurs résultats dans les cas favorables (mais dans certains cas ne marchera pas du tout mais nous n'allons pas en croiser ici). On va utiliser le résultat : f(a)f(a+h2)f(ah2)h. Cette simple astuce permet de doubler la précision. C'est ce qu'on appelle la méthode des différences finies. Elle est souvent utilisée dans les logiciels de calcul formel pour calculer les nombres dérivées.

Créer une fonction deriver(f,a,h) qui donne le nombre dérivé de f en a en utilisant la méthode des différences finies.

Calcul du nombre dérivé
def deriver(f,a,h):
# Ne pas toucher ce qui précède
# Les valeurs pour les variables en entrée seront automatiquement données
# Ecrire ci-dessous en n'oubliant pas d'indenter et d'utiliser return pour renvoyer un résultat
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

La méthode de Newton

Passons à présent aux choses sérieuses : On cherche à trouver une approximation d'une solution de l'équation f(x)=0 pour une fonction f donnée. L'idée est, comme sur la figure ci-dessous, de : Méthode de Newton

  • prendre un point d'abscisse x0 (pas trop loin de là où on imagine que la solution se trouve),
  • tracer la tangente à la courbe représentative de f et regarder pour quelle valeur x1 la tangente coupe l'axe des abscisses
  • On considère alors le point de la courbe représentative de f ayant pour abscisse cette valeur trouvée x1 dans l'étape précédente et on recommence...

Question mathématique : Prouver que la méthode revient à considérer la suite des abscisses (xn) définie par la relation de récurrence xn+1=xnf(xk)f(xk).

Créer une fonction Newton(f,x0,n) qui calcule la valeur de xn definie juste avant en prenant comme valeur initiale x0. Pour cela vous devrez faire un copier coller de votre fonction deriver précédente. On fixera la valeur de h pour le calcul du nombre dérivé à 0.000001.

Remarque : Les tests sont faits avec n=5 seulement. On pourra remarquer la précision de l'approximation obtenue en calculant seulement x5. C'est cette rapidité de convergence qui fait la force de cette méthode.

Méthode de Newton
# Copier ci dessous votre fonction deriver(f,a,h)
def Newton(f,x0,n):
# Les valeurs pour les variables en entrée seront automatiquement données
# Ecrire ci-dessous en n'oubliant pas d'indenter et d'utiliser return pour renvoyer un résultat
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Pour aller plus loin

Difficulté : Difficile

Créer ci-dessous un script qui permet d'afficher graphiquement la fonction ainsi que les 5 tangentes successives de la méthode de Newton.

Pour cela, on utilisera le module matplotlib et les fonctions précédentes (en les modifiant si besoin)

Remarques : La fonction f et la valeur de départ sont données pour l'exemple mais vous pouvez les modifier pour observer d'autres cas.
Cette fenêtre n'a pas d'auto correction, le résultat étant visuel, vous devriez voir si cela fonctionne ou pas.

Méthode de Newton - Graphique
import matplotlib.pyplot as plt
import numpy as np
# La fonction f à tracer
def f(x) :
return x**4 - 2
# La valeur initiale
x0 = 3
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants