24 février 2022

Méthode Newton – Zéros de fonction (Python)

Les calculatrices programmables en Python sont désormais bien représentées en France. Nous avons déjà étudié plusieurs volets de la programmation en calculatrice Python sur notre blog. Le Python est devenu le langage principal pour l’enseignement de l’algorithmie au lycée. Rechercher les valeurs de x pour lesquelles f(x)=0 est un cas courant de problèmes mathématiques que les étudiants ont souvent à résoudre.

La dichotomie

Explications

Le point de départ de cette méthode est le théorème de Bolzano encore appelé « théorème des valeurs intermédiaires ». Il indique que si une fonction continue sur un intervalle prend deux valeurs m et n, alors elle prend toutes les valeurs intermédiaires entre m et n.

Une conséquence directe du théorème de Bolzano est :

Soit f une fonction de ℝ dans ℝ, elle est continue et strictement monotone sur l’intervalle [a, b].

La dichotomie ou bissection (bisection en anglais) est une méthode stable qui garantit la convergence vers une valeur approchée de r dès lors que les hypothèses sur f sur [a, b] sont bien respectées. La méthode va consister à réduire l’intervalle de recherche en le divisant par 2 à chaque itération. Par récurrence, l’erreur absolue sera au maximum de 2-n-1*(b-a). Le défaut de cette méthode est d’avoir une convergence lente par rapport à la méthode de Newton ou celle de la sécante.

Algorithme

On a un intervalle [an, bn] avec f(an)*f(bn)<0.

On calcule le milieu de l’intervalle m=( an + bn)/2.

Programme Python

On ne va pas stocker une suite de valeurs, on va se contenter de mettre à jour la valeur de a ou de b successivement. epsilon sera la valeur d’arrêt de l’algorithme.

from math import cos

def bisection( f, a, b, epsilon=1.E-6 ):
while b - a > epsilon:
m  = 0.5 * ( a + b )
if f( a ) * f( m ) <= 0:
b = m
else:
a = m
return 0.5 * ( a + b )
r = bisection( cos, 0.5, 2, 1.0E-10 )
print( "f(", r, ") =", cos(r) )

L’algorithme converge en 34 itérations dans le cas de l’exemple sous la fonction.

La méthode de Newton-Raphson

Explications

La méthode de Newton est basée sur l’approximation locale de la fonction f par son développement de Taylor-Young à l’ordre 1. Supposons que nous sommes autour d’un point x0 proche de la racine recherchée. En utilisant l’approximation de f (qui se trouve être une droite), on va pouvoir trouver l’intersection de cette droite avec l’axe (Ox) et obtenir un point x1 qui permet de se rapprocher de la racine.

Dans l’exemple suivant, nous allons travailler sur la fonction f(x)=x²-1. Les racines de ce polynôme sont évidentes : r1=-1 et r2=1. Cependant si on lui applique l’approximation de Taylor-Young en x0=2, nous obtenons sur la calculatrice Numworks :

  • La courbe f(x) en rouge
  • la tangente à f au point x=2 est en bleu

L’équation de la tangente est T0(x)=4x-5. Et le zéro de la tangente se produit pour x1=5/4. Si on recommence l’algorithme en x1, on trouve T1(x)=5x/2-41/16. Et donc le zéro de la tangente se produit en x2=41/40.

Cette méthode a le mérite de converger rapidement si l’on part d’un point proche de la solution.

L’algorithme

Le développement de Taylor-Young en x0 de f nous donne :

Donc la valeur de x1 se calculera grâce à la formule suivante :

Par définition la valeur de la dérivée de f en x se calcule comme suit :

Une bonne approximation de la dérivée pourra donc être obtenue en utilisant une valeur de h suffisamment petite (10-6 par exemple). On peut ainsi construire une suite de nombres xn à partir d’une valeur de x0 de la manière suivante :

On s’arrêtera si |f(xn)|<e avec e suffisamment petit car on aura une bonne approximation de la racine recherchée. Mais pour éviter le risque de divergence, nous allons adjoindre un compteur d’itérations qui s’il dépasse une valeur définit à l’avance on arrête la boucle et on sort en erreur.

Fonction Newton( f, x, h=10-6, epsilon=10-8 )
	99 -> NbIterationMax
	0 -> n
	Tant que ( |f(x)| > epsilon ) et ( n < NbIterationMax )
		x - 2 * h * f( x ) / (f(x+h) - f(x-h)) -> x
		n+1 -> n
	Fin Tant que
	Si n=NbIterationMax Alors
			Sors en erreur
		Sinon
			Retourne x
	Fin Si
Fin Fonction

En recherchant Newton( cos, 0.5 ) l’algorithme converge en 4 itérations ce qui est très efficace en comparaison de la dichotomie.

Code Python

Au lieu de sortir en erreur, en Python, nous retournerons None.

from math import fabs

def Newton( f, x, h=1.0E-6, epsilon=1.0E-8 ):
    NbIterationMax = 99
    n = 0
    while ( fabs( f(x) ) > epsilon ) and ( n < NbIterationMax ):
        x = x - 2 * h * f( x ) / ( f( x + h ) - f( x - h ) )
        n += 1
    return x if n < NbIterationMax else None

La méthode de la sécante

Explications

L’idée de la méthode de la sécante est très simple : pour une fonction f continue et monotone sur un intervalle [a, b], on trace le segment [AB]A=(a, f(a)) et B=(b, f(b)). On calcule M=(m, 0) le point d’intersection de la droite (AB) avec l’axe des abscisses. La droite (AB) s’appelle la sécante. Si f(a)*f(m)<0 alors le 0 de f se trouvera sur [a, m], sinon il sera sur [m, b]. Il suffit de réitérer sur le sous-intervalle jusqu’à ce que |f(m)|<ε ou que b-a<ε.

L’algorithme

La valeur de m se calcule facilement :

Ce qui nous permet de construire l’algorithme suivant :

Fonction methode_secante( f, a, b,  )
Tant que b – a <  faire
a – f( a ) * ( b – a ) / ( f( b ) – f( a ) ) -> m
f( m ) -> fm
Si |fm| <  alors
Retourne m
Sinon si f( a ) * fm < 0 alors
m -> b
Sinon
m -> a
Fin si
Fin tant que
Retourne ( a + b ) / 2
Fin fonction

Code Python

Transformons cet algorithme en programme Python :

def methode_secante( f, a, b, epsilon=1.0E-6 ):
   while b - a > epsilon:
        m  = a - f( a ) * ( b - a ) / ( f( b ) - f( a ) )
        fm = f( m )
        if fabs( fm ) < epsilon:
            return m
        elif f( a ) * fm < 0:
            b = m
        else:
            a = m
    return 0.5 * ( a + b )

En le testant sur « methode_secante( cos, 0, 3, 1.0E-10 ) » on converge en 5 itérations et le résultat retourné est π /2 avec ces 16 décimales exactes.

Expertise Design & Code

$

Python, Java, C++, C# et Front-End

Découvrez nos formations

$

Parcourir le catalogue

Boostez votre carrière !

$

Nos offres pour Développeurs

Tous les mois recevez nos derniers articles !

Try X4B now !

Découvrez gratuitement XComponent for Business. Notre solution logicielle BizDevOps !

Écrit par Philippe Boulanger

0 Comments

Submit a Comment

Votre adresse e-mail ne sera pas publiée.