Open Source Your Knowledge, Become a Contributor
Technology knowledge has to be shared and made accessible for free. Join the movement.
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 . 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é :
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 :
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.
La méthode de Newton
Passons à présent aux choses sérieuses : On cherche à trouver une approximation d'une solution de l'équation
- prendre un point d'abscisse
(pas trop loin de là où on imagine que la solution se trouve),x 0 - tracer la tangente à la courbe représentative de
et regarder pour quelle valeurf la tangente coupe l'axe des abscissesx 1 - On considère alors le point de la courbe représentative de
ayant pour abscisse cette valeur trouvéef dans l'étape précédente et on recommence...x 1
Question mathématique : Prouver que la méthode revient à considérer la suite des abscisses
définie par la relation de récurrence ( x n ) . x n + 1 = x n − f ( x k ) f ′ ( x k )
Créer une fonction Newton(f,x0,n)
qui calcule la valeur de 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
. C'est cette rapidité de convergence qui fait la force de cette méthode. x 5
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.