La méthode de Hörner

La méthode de Hörner

Considérons un polynôme P, dont une racine est égale à a.

La méthode de Hörner va nous permettre de trouver les coefficients du polynôme Q tel que : \[P(x)=(x-a)Q(x).\]

Bien entendu, il existe d’autres méthodes, comme la division euclidienne de polynômes ou encore la méthode des coefficients indéterminés, mais nous allons voir que la méthode de Hörner a deux avantages sur les autres : sa rapidité et le fait que l’on puisse la programmer aisément.

Un exemple simple

Considérons le polynôme : \[ P(x)=x^4-3x^3+7x^2-4x-12,\] dont une racine évidente est = 2.

Nous allons réfléchir à une méthode qui nous permet de trouver les coefficients de Q(x), tel que P(x) = (– 2)Q(x), à l’aide d’une division euclidienne.

On peut alors remarquer que :

  • \(-1 = -3 + 2\times2 \)
  • \( 5=7+2\times(-1)\)
  • \(6=-4+2\times 5\)

Généralisation

Posons \(P(x)=\displaystyle\sum_{k\leq n} p_kx^k\), \(Q(x)=\displaystyle\sum_{k<n} q_kx^k\) et a une racine de P.

D’après le raisonnement précédent, on peut écrire : \[ \begin{cases} q_{n-1}=p_n\\ q_k=p_{k+1}+aq_{k+1}\quad\forall\ 0\leq k < n\end{cases} \]

Schématisation

Application

Soit : \[ P(x)=3x^5-4x^4+8x^3-3x^2-2x-2.\] Une racine de P est = 1, d’où :
D’où : \[ P(x)=(x-1)(3x^4-x^3+7x^2+4x+2). \]

Programme Python

On peut peut-être améliorer le code suivant, mais il fonctionne correctement :

n = int(input("Degré du polynôme : "))
a = float(input("Racine du polynôme : "))
p = (n+1)*[0]
for i in range(0,n+1):
    print("Coefficient de x^",i," : ")
    p[i]=float(input());

q = n*[0]
q[n-1] = p[n]
j = n-2
while j > -1:
    q[j] = p[j+1]+a*q[j+1]
    j=j-1

for i in range(0,n):
    print("Coefficient de x^",i," : ",q[i],end='\n')

 

Télécharger cet article au format PDF : Méthode de Horner

Voir les fichiers sources \(\LaTeX\) et Python : cliquez ici

Stéphane Pasquet
Stéphane Pasquet

Auteur de livres parascolaires en mathématiques

Laissez votre message