Méthode de Horner
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

La méthode de Horner est utilisée dans le calcul polynomial, soit pour calculer la valeur d'une fonction polynomiale en un point, soit pour calculer le quotient d'un polynôme par X - a.

Valeur d'un polynôme en un point (Graphie)

Soit P = λnXn + λn − 1Xn − 1 + ... + λ0 un polynôme (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils donnent localement une...) sur un anneau commutatif A et a un élément de A. Le calcul de P(a) = λnan + λn − 1an − 1 + ... + λ0 laisse à penser qu'il faut calculer chacune des puissances de a, multiplier celle-ci par son coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme), un espace...) λk puis faire la somme de ce que l'on a trouvé.

Si on calcule an en multipliant successivement a par lui-même, le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de produits nécessaire est alors de n + (n − 1) + ... + 2 + 1 = n(n + 1) / 2, quantité (La quantité est un terme générique de la métrologie (compte, montant) ; un scalaire, vecteur, nombre d’objets ou d’une autre manière de dénommer la valeur d’une...) qui croît comme le carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même mesure. Un carré est à la fois un...) du degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) du polynôme.

On peut améliorer la vitesse (On distingue :) du calcul de an par une méthode d'exponentiation rapide, permettant de réduire le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) du calcul de P(a) à une quantité qui croît comme nln(n).

La méthode de Horner (La méthode de Horner est utilisée dans le calcul polynomial, soit pour calculer la valeur d'une fonction polynomiale en un point, soit pour calculer le quotient d'un polynôme par X - a.) consiste à améliorer encore ce résultat en effectuant le calcul comme suit :

P(a) = ((...((λna + λn − 1)a + λn − 2)a + ...) + λ1)a + λ0

Le nombre de produits est alors réduit à n, de sorte que le temps de calcul d'une fonction polynomiale en un point a est seulement proportionnel au degré du polynôme.

Quotient d'un polynôme par X - a

Reprenons le même polynôme P = λnXn + λn − 1Xn − 1 + ... + λ0 et cherchons son quotient dans la division (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la fonction "division par ce nombre" est la réciproque de la fonction...) euclidienne par X - a. On a :

P = (Xa)Q + P(a)

Si on écrit Q = qn − 1Xn − 1 + qn − 2Xn − 2 + ... + q1X + q0 et si on identifie les coefficients de même degré dans les deux membres, on obtient :

qn − 1 = λn
qk − 1 = λk + aqk pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) k tel que 0 < k < n

La valeur de P(a) n'est autre que λ0 + aq0.

Les n valeurs de la suite q calculées ici sont précisément les n valeurs successives calculées dans le paragraphe précédent pour évaluer P(a). La mémorisation (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) de ces valeurs successives donne donc les coefficients du polynôme quotient, la dernière valeur étant celle du reste.

Illustration dans un tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :)

Une présentation de la méthode de Horner dans un tableau montre la simplicité de l'algorithme : chaque coefficient de Q s'obtient en multipliant le coefficient de la case de gauche par a et en lui ajoutant le coefficient de la case du dessus.

Coefficients de P λn λn - 1 λn - 2 ... λ1 λ0
Coefficients de Q qn - 1
λn
qn - 2
aqn - 1 + λn - 1
qn - 3
aqn - 2 + λn - 2
... q0
aq1 + λ1
r
aq0 + λ0

Exemple pratique : division de 4X3 − 7X2 + 3X − 5 par X − 2

Coefficients de P 4 − 7 3 − 5
Coefficients de Q 4 8 − 7 = 1 2 + 3 = 5 r = 10 − 5 = 5

Ce qui donne : 4X3 − 7X2 + 3X − 5 = (X − 2)(4X2 + X + 5) + 5

Page générée en 0.037 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique