Algorithme Polynôme – Python

Les calculatrices programmables en Python sont bien représentées en France. Le Python est devenu le langage principal pour l’enseignement de l’algorithmie au lycée. Vous pouvez d’ailleurs découvrir d’autres articles de programmation Python sur calculatrice sur notre blog. Les polynômes sont des fonctions riches en fonctionnalités et elles sont utiles dans de nombreux domaines. Elles font partie, ainsi, des fonctions les plus étudiées dans le cursus du lycée et au-delà. La recherche des zéros d’un polynôme de degré 2 est un grand classique de la classe de seconde. L’évaluation des polynômes en utilisant la méthode de Hoerner est un classique de l’optimisation des performances en diminuant le nombre d’opérations. Quant au calcul de la dérivée d’un polynôme c’est un bon moyen de mettre en évidence la concision du langage 😊

A X² + B X + C = 0

Explications

Sans se lancer dans de longues démonstrations, la recherche des racines de cette équation dépend du signe du discriminant :

Δ = b² – 4 a c

• Si Δ est nul, alors il y a une racine unique : x = -b / (2a)
• Si Δ > 0 alors l’équation admet 2 solutions réelles :
  • x₁ = ( -b + √Δ ) / ( 2a )
  • x₂ = ( -b – √Δ ) / ( 2a )
• Si Δ est strictement négatif alors l’équation admet 2 racines complexes
  • x₁ = ( -b + √Δ ) / ( 2a ) avec qui √Δ est un nombre complexe
  • x₂ = ( -b – √Δ ) / ( 2a ) avec qui √Δ est un nombre complexe

En Polynôme Python

Voici la version qui ne retourne que les racines réelles : on retourne None s’il n’y a pas de solutions réelles sinon on retourne un tuple contenant 2 racines.

from math  import sqrt

def racine_polynome2( a, b, c ):
    d = b * b - 4 * a * c
    if d < 0:
        return None
    else:
        return ( ( -b + sqrt( d ) ) / 2 / a,
                 ( -b - sqrt( d ) ) / 2 / a )

Pour le cas où l’on souhaite des racines dans l’espace des nombres complexes, le code Python s’en trouve simplifié :

from cmath import sqrt as csqrt

def racine_polynome2_complexe( a, b, c ):
    d = b * b - 4 * a * c
    return ( ( -b + csqrt( d ) ) / 2 / a,
             ( -b - csqrt( d ) ) / 2 / a)

Représentation d’un Algorithme Polynôme Python

Le type Polynôme n’existe pas dans Python, pour travailler avec les polynômes il nous faudra donc trouver une structure de stockage adaptée. Un polynôme est défini par la liste de ses coefficients où chacun d’entre eux est associé à une puissance de x.

Une liste Python, qui est aussi un tableau, contient des éléments qui sont indexés de 0 à n-1 (où est n est le nombre d’éléments). On pourrait stocker le coefficient a_i correspondant à xⁱ dans l’élément de la liste Python indicé i. « x⁵-x⁴+2x³-2x²+3x-3 » sera ainsi codé : [-3, 3, -2, 2, -1, 1].

Cette forme de représentation sera adoptée pour tous les algorithmes que nous décrirons dans la suite de cet article.

Évaluation de Polynôme : la méthode de Hoerner

Explications

Toutes les opérations sur un ordinateur ont un coût que l’on compte en nombre de cycles d’horloge. Les multiplications sont plus coûteuses que les additions et le calcul de la puissance d’un nombre est beaucoup plus coûteux qu’une multiplication. Calculer x¹⁰ est donc consommateur en puissance de calcul ; heureusement un mathématicien du nom de Hoerner a trouvé une méthode permettant de diminuer le coût de l’évaluation en minimisant le nombre d’opérations.

Voici un exemple sur un polynôme de degré 4 que nous noterons P₄(x) = a x⁴ + b x³ + c x² + d x + e. Par un jeux de factorisation des opérations on peut le réécrire en P₄(x) = ( ( ( a x + b ) x + c ) x + d ) x + e. Par ce biais, on remplace les calculs de puissances par des additions et multiplication successives.

Algorithme

L’algorithme du schéma de Hoerner est assez simple à mettre en œuvre. On utilisera la variable P pour le polynôme. La fonction « longueur » retourne le nombre d’éléments du tableau :

Fonction EvaluerPolynome( P, x )
	longueur( P ) - 1 -> n
	0. -> v
	Pour i de n à 0 avec pas de -1
		v * x + P[ i ] -> v
	Fin Pour
	Retourne v
Fin Fonction

Code Python

Python fournit un grand nombre de moyens de parcourir un tableau notamment de la fin vers le début grâce à la fonction reversed qui fournit un itérateur (un moyen de parcourir les éléments du tableau du dernier élément vers le premier).

def EvaluerPolynome( P, x ):
    e = 0.
    for c in reversed( P ):
        e = e * x + c
    return e

Calculer la dérivée d’un Polynôme Python

Explications

La dérivée du monôme axⁿ est nax^n-1. Et la dérivée de f(x)+g(x) est f’(x)+g’(x). Dès lors, automatiser le calcul de la dérivée d’un polynôme complexe est une tâche simple.

Algorithme

Fonction Derivation( P )
	[] -> D
	longueur( P ) - 1 -> n
	Pour i de 1 à n
		ajouter (i * P[i]) à la fin de D
	Fin Pour
	Retourne D
End Fonction

Programme Python

Nous allons profiter de la concision des listes par compréhension alliée à la fonction enumerate sur un sous-tableau de P pour en faciliter l’écriture.

def DerivationPolynome( P ):
    return [ i * c for i, c in enumerate( P[ 1: ], 1 ) ]