2.6 Polynômes
69
Programme 2.5. horner : algorithme de division synthétique
function [y ,b ] = horner (a , z)
% HORNER A l g o rithme de Horner
%
Y = HORNER (A , Z ) calcule
%
Y = A (1)* Z^ N + A (2)* Z ^(N -1) + ... + A (N )*Z + A (N +1)
%
en u t i l isant l ’ a l g or ithme de division s y n t héti que
%
de Horner
n = length ( a ) -1;
b = zeros (n +1 ,1); b (1) = a (1);
for j =2:n +1
b( j) = a (j )+b (j -1)* z;
end
y = b (n +1);
b = b (1: end -1);
return
Nous introduisons maintenant une technique efficace permettant de
“retirer” une racine connue (ou dont on connaît une approximation) afin
de chercher les autres racines de proche en proche, jusqu’à les avoir toutes
déterminées.
Nous commençons pour cela par rappeler la propriété de la division
euclidienne des polynômes :
Proposition 2.3 Soient deux polynômes h n ∈ P n et g m ∈ P m avec
m ≤ n. Il y a un unique polynôme δ ∈ P n−m et un unique polynôme
ρ ∈ P m−1 tels que
h n (x) = g m (x)δ(x) + ρ(x).
(2.33)
Ainsi, en divisant un polynôme p n ∈ P n par x − z, on déduit de (2.33)
que
p n (x) = b 0 + (x − z)q n−1 (x; z),
où q n−1 est le quotient et b 0 le reste de la division. Si z est une racine
de p n , alors on a b 0 = p n (z) = 0 et donc p n (x) = (x − z)q n−1 (x; z).
La résolution de l’équation q n−1 (x; z) = 0 fournit alors les n − 1 racines
restantes de p n (x). Cette remarque suggère la démarche suivante, appelée
déflation, pour calculer toutes les racines p n .
Pour m = n, n − 1, . . . , 1, (par valeurs décroissantes) :
1. trouver une racine r m de p m à l’aide d’une méthode d’approximation ;
2. calculer q m−1 (x; r m ) en utilisant (2.31)-(2.32) (avec z = r m ) ;
3. poser p m−1 = q m−1 .
La méthode que nous présentons dans le paragraphe suivant est la
plus utilisée des méthodes de ce type. Elle est basée sur une méthode de
Newton pour approcher les racines.