Méthode de Horner (ou schéma de Horner)

Objectif

Cette méthode permet de calculer l'image d'un polynôme PP en un point xox_o. En outre, elle permet d'obtenir la division euclidienne de P(x)P(x) par (xxo)(x-x_o), utile pour la factorisation des polynômes.
Et puis elle est très simple et efficace (je parle en terme d'erreurs potentielles).

Méthode de Horner pour calculer l'image d'un point par un polynôme

Introduction

Je suis très surpris de constater que la méthode (ou schéma) de Horner n'est pas trés utilisée par les lycéens. Le principe est pourtant très simple et sa mise en pratique très aisée. Je vais
essayer d'expliquer en quoi elle consiste. Comme je l'ai indiqué dans le titre, le schéma de Horner permet de calculer l'image d'un polynôme PP en un point β\beta donné. Mais la force de la
méthode réside sur le fait que tout en calculant l'image de β\beta, on peut obtenir une factorisation de PP dans le cas où β\beta est une racine de PP.

Plan de cours

La première section est beaucoup plus théorique et est réservée à ceux qui souhaitent approfondir et comprendre pourquoi cette méthode est correcte... Cette partie n'est pas nécessaire pour
appliquer la méthode.

On peut passer directement à la deuxième section. Celle-ci est la mise en oeuvre de la méthode dans sa pratique.

Dans la section 3, je donnerai deux exemples pour illustrer la méthode, puis je conclurai par le lien avec la factorisation dans la section 4.

1 - Etude théorique

Dans cette section, on considère un polynôme PP de degré nn, avec n2n \geqslant 2 (sinon c'est trivial...) et β\beta un réel quelconque. On suppose que PP s'écrit :

P(x)=anxn+an1xn1+...+a2x2+a1x+a0P(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_2x^2 + a_1x + a_0;

où les aia_i sont des réels quelconques (mais an0a_n \neq 0 car PP est de degré nn).

Notre but est de calculer P(β)P(\beta); on remplace donc xx par β\beta dans P(x)P(x) :

P(β)=anβn+an1βn1+...+a2β2+a1β+a0P(\beta) = a_n \beta^n + a_{n-1} \beta^{n-1} + ... + a_2 \beta^2 + a_1 \beta+ a_0

Maintenant, on factorise β\beta sauf pour a0a_0 (qui n'a pas de β\beta) et on obtient :

P(β)=β(anβn1+an1βn2+...+a3β2+a2β+a1)+a0P(\beta) = \beta (a_n \beta^{n-1} + a_{n-1} \beta^{n-2} + ... + a_3 \beta^2 + a_2 \beta + a_1) + a_0

Notons :

P1(β)=anβn1+an1βn2+...+a3β2+a2β+a1P_1(\beta) = a_n \beta^{n-1} +a_{n-1} \beta^{n-2} + ... +a_3 \beta^2 + a_2 \beta +a_ 1.

On a donc : P(β)=βP1(β)+a0P(\beta) = \beta P1(\beta) +a_0.

Pour calculer P(β)P(\beta), il nous faut donc calculer P1(β)P_1(\beta) et pour cela on refait la même chose que pour PP : on factorise par β\beta sauf pour a1a_1

On obtient :

P1(β)=β(anβn2+an1βn3+...+a3β+a2)+a1P_1(\beta) = \beta(a_n\beta^{n-2} + a_{n-1} \beta^{n-3} + ... + a_3 \beta + a_2) + a_1

Puis on note : P2(β)=anβn2+an1βn3+...+a3β+a2P_2(\beta) = a_n \beta^{n-2} + a_{n-1} \beta^{n-3} + ... + a_3\beta + a_2. On a alors P1(β)=βP2(β)+a1P_1(\beta) = \beta P_2(\beta) + a_1.

En continuant ainsi, on obtient :

P(β)=anβn+an1βn1+...+a2β2+a1β+a0P(\beta) = a_n \beta^n + a_{n-1} \beta^{n-1} + ... + a_2 \beta^2 + a_1 \beta + a_0

=β(anβn1+an1βn2+...+a2β+a1)+a0= \beta (a_n \beta^{n-1} + a_{n-1} \beta^{n-2} + ... + a_2 \beta + a_1) + a_0

=β(β(anβn2+an1βn3+...+a3β+a2)+a1)+a0= \beta (\beta (a_n \beta^{n-2} + a_{n-1} \beta^{n-3} + ... + a_3 \beta + a_2) + a_1) + a_0

== ...........

=β(β(β(...β(βan+an1)...)+a2)+a1)+a0= \beta(\beta(\beta(... \beta(\beta a_n + a_{n-1})...) + a_2) + a_1) + a_0

Pour calculer tout ça, on procède en deux étapes, en commençant par le centre du calcul :
1. on multiplie β\beta par ana_n.
2. on rajoute an1a_{n-1} au résultat.

Et après ?

Ben on recommence. On multiplie β\beta par le résultat qu'on a obtenu à l'étape 2 précédente puis on rajoute an2a_{n-2} au résultat ainsi obtenu, et on continue ainsi, jusqu'à rajouter a0a_0. Le résultat qu'on obtient là est exactement P(β)P(\beta).

2 - Dans la pratique

OK, fini le bla-bla de la section 1. Passons à la pratique. On considère donc un polynôme PP de degré nn, avec n2n \geqslant 2 et un réel β\beta. Il s'agit alors de calculer P(β)P(\beta). Voici les étapes nécessaires :

1. Dessiner un tableau ayant 3 lignes et (n+2)(n + 2) colonnes.

col. 11 col. 22 col. 33 ............ col. nn col. n+1n+1 col. n+2n+2
ligne 11
ligne 22
ligne 33

2. Initialiser le tableau de cette façon :

  • Ligne 2, colonne 1 : on met ici la valeur β\beta, en laquelle on veut calculer l'image par PP.

  • Ligne 3, colonne 2 : on met ana_n.

  • Ligne 1 : mettre le coefficient de degré nn à la colonne 2, celui de degré n1n - 1 sur la colonne 3, etc..., le coefficient de degré 11 sur l'avant-dernière colonne et enfin le coefficient constant sur la dernière colonne.

Remarque : si un des coefficients est nul (c'est-à-dire qu'il n'y a pas de terme de degré ce coefficient, il faut mettre 00 à la place).

En supposant que P(x)=anxn+an1xn1+...+a2x2+a1x+a0P(x) = a_nx^n +a_{n-1} x^{n-1} +... +a_2x^2 +a_1x+a_0, ceci donne le tableau suivant :

col. 11 col. 22 col. 33 ............ col. nn col. n+1n+1 col. n+2n+2
ligne 11 ana_{n} an1a_{n-1} ....... a2a_2 a1a_1 a0a_0
ligne 22 β\beta
ligne 33 ana_{n}

3. Remplir le tableau de la manière suivante :

  • (a) Prendre la dernière valeur mise sur la ligne 3

  • (b) Multiplier cette valeur par β\beta

  • (c) Mettre le résultat à la ligne 2 et à la colonne suivant celle de cette valeur.

col. 11 col. 22 col. 33 col. 44 ....
ligne 11 ana_{n} an1a_{n-1} an2a_{n-2} ...
ligne 22 β\beta βan\beta a_n ...
ligne 33 ana_{n} ....
  • (d) Additionner ce résultat avec le coefficient correspondant à cette colonne.

  • (e) Mettre le résultat à la même colonne mais à la ligne 3.

col. 11 col. 22 col. 33 col. 44 ....
ligne 11 ana_{n} an1a_{n-1} an2a_{n-2} ...
ligne 22 β\beta βan\beta a_n ...
ligne 33 ana_{n} βan+an1\beta a_n + a_{n-1} ....
  • (f) Recommencer à l'étape (a) jusqu'à remplir la ligne 3 à la dernière colonne. La dernière valeur obtenue est l'image de β\beta par le polynôme PP.
col. 11 col. 22 col. 33 col. 44 ....
ligne 11 ana_{n} an1a_{n-1} an2a_{n-2} ...
ligne 22 β\beta βan\beta a_n β2an+βan1\beta^2 a_n + \beta a_{n-1} ...
ligne 33 ana_{n} βan+an1\beta a_n + a_{n-1} β2an+βan1+an2\beta^2 a_n + \beta a_{n-1} + a_{n-2} ....

3 - Deux exemples

Prenons deux exemples pour illustrer la méthode.

Exemple 1 :

Soit P1(x)=2x3+3x2+11x6P_1(x) = -2x^3 + 3x^2 + 11x - 6. On veut calculer P1(2)P_1(-2).

On obtient successivement les tableaux suivants en suivant les étapes de la méthode :

2-2 33 1111 6-6
2-2
2-2

2-2 33 1111 6-6
2-2 44
2-2

2-2 33 1111 6-6
2-2 44
2-2 77

2-2 33 1111 6-6
2-2 44 14-14
2-2 77

2-2 33 1111 6-6
2-2 44 14-14
2-2 77 3-3

2-2 33 1111 6-6
2-2 44 14-14 66
2-2 77 3-3

2-2 33 1111 6-6
2-2 44 14-14 66
2-2 77 3-3 00

Ainsi on a terminé et on lit que P1(2)=0P_1(-2) = 0.

Exemple 2 :

On prend maintenant P2(x)=3x4x216x14P_2(x) = 3x^4 - x^2 - 16x - 14, et β=2\beta = 2. Ceci nous donne les tableaux suivants (remarquez le 00 mis pour le coefficient de degré 3...) :

33 00 1-1 16-16 14-14
22
33

33 00 1-1 16-16 14-14
22 66
33 66

33 00 1-1 16-16 14-14
22 66 1212
33 66 1111

33 00 1-1 16-16 14-14
22 66 1212 2222
33 66 1111 66

33 00 1-1 16-16 14-14
22 66 1212 2222 1212
33 66 1111 66

33 00 1-1 16-16 14-14
22 66 1212 2222 1212
33 66 1111 66 2-2

Et par suite, P2(2)=2P_2(2) = -2.

4 - Intérêt de la méthode : factorisation

En fait, une fois le tableau du schéma de Hormer rempli, il donne une écriture du polynôme PP en question. Plus exactement, on peut lire la division euclidienne de P(x)P(x) par (xβ)(x - \beta ).

Voici comment procéder : on sait que P(x)P(x) peut toujours s'écrire sous la forme (xβ)Q(x)+P(β)(x - \beta)Q(x) + P(\beta),

QQ étant un polynôme de degré (n1)(n - 1) si PP est de degré nn. Il ne reste plus qu'à trouver P(β)P(\beta), ainsi que les coefficients de QQ.

Bonne nouvelle : comme on l'a dit, P(β)P(\beta) est la valeur obtenue à la dernière ligne et à la dernière colonne du tableau; quant aux coefficients de QQ, ils se lisent sur la 3ème et dernière ligne du tableau, une fois terminé.

Ainsi, pour les exemples de la section 3, on obtient :

P1(x)=(x+2)(2x2+7x3)P_1(x) = (x + 2)(-2x^2 + 7x - 3) et
P2(x)=(x2)(3x3+6x2+11x+6)2P_2(x) = (x - 2)(3x^3 + 6x^2 + 11x + 6) - 2.

Note : Si des erreurs se sont glissées quelque part dans ce document ou si vous avez des remarques, merci de m'en informer.

Par jaoira

Toutes nos vidéos sur méthode de horner (ou schéma de horner)


Posez vos questions

D'autres interrogations sur ce cours ? Démarrez une discussion et obtenez des réponses à des exercices pratiques.

Accéder au forum