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] où 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.
