228
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
Propri´ et´ e 6.6 (th´ eor` eme de Cauchy) Tous les z´ eros de p n sont contenus
dans le disque Γ du plan complexe
Γ = {z ∈ C : |z| ≤ 1 + η k } ,
o` u η k = max
0≤k≤n−1
|a k /a n |.
La seconde propri´ et´ e n’est pas tr` es utile quand η k 1. Dans ce cas, il vaut
mieux effectuer un changement de coordonn´ ees par translation, comme sugg´ er´ e dans l’Exercice 10.
6.4.1 M´ ethode de Horner et d´ eflation
Dans cette section, nous d´ ecrivons la m´ ethode de Horner pour l’´ evaluation
efficace d’un polynˆ ome (et de sa d´ eriv´ ee) en un point z donn´ e. L’algorithme
permet de g´ en´ erer automatiquement un proc´ ed´ e, appel´ e d´ eflation, pour l’approximation successive de toutes les racines d’un polynˆ ome.
La m´ ethode de Horner est fond´ ee sur le fait que tout polynˆ ome p n ∈ P n
peut ˆ etre ´ ecrit sous la forme
p n (x) = a 0 + x(a 1 + x(a 2 + . . . + x(a n−1 + a n x) . . .)).
(6.25)
Les formules (6.24) et (6.25) sont ´ equivalentes d’un point de vue alg´ ebrique ;
n´ eanmoins, (6.24) n´ ecessite n sommes et 2n − 1 multiplications pour ´ evaluer
p n (x), tandis que (6.25) ne requiert que n sommes et n multiplications. La
seconde expression, parfois appel´ ee algorithme des multiplications emboˆ ıt´ ees,
est l’ingr´ edient de base de la m´ ethode de Horner. Cette m´ ethode ´ evalue efficacement le polynˆ ome p n au point z par l’algorithme de division synth´ etique
suivant
b n = a n ,
b k = a k + b k+1 z, k = n − 1, n − 2, ..., 0.
(6.26)
L’algorithme de division synth´ etique (6.26) est impl´ ement´ e dans le Programme 48. Les coefficients a j du polynˆ ome sont stock´ es dans le vecteur a, en
commen¸ cant par a n .
Programme 48 - horner : Algorithme de division synth´ etique
function [pnz,b] = horner(a,n,z)
%HORNER Algorithme de division synth´ etique.
% [PNZ,B]=HORNER(A,N,Z) ´ evalue avec la m´ ethode de Horner un polynˆ ome
% de degr´ e N et de coefficients A(1),...,A(N) au point Z.
b(1)=a(1);
for j=2:n+1
b(j)=a(j)+b(j-1)*z;
end
pnz=b(n+1);
return
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
Propri´ et´ e 6.6 (th´ eor` eme de Cauchy) Tous les z´ eros de p n sont contenus
dans le disque Γ du plan complexe
Γ = {z ∈ C : |z| ≤ 1 + η k } ,
o` u η k = max
0≤k≤n−1
|a k /a n |.
La seconde propri´ et´ e n’est pas tr` es utile quand η k 1. Dans ce cas, il vaut
mieux effectuer un changement de coordonn´ ees par translation, comme sugg´ er´ e dans l’Exercice 10.
6.4.1 M´ ethode de Horner et d´ eflation
Dans cette section, nous d´ ecrivons la m´ ethode de Horner pour l’´ evaluation
efficace d’un polynˆ ome (et de sa d´ eriv´ ee) en un point z donn´ e. L’algorithme
permet de g´ en´ erer automatiquement un proc´ ed´ e, appel´ e d´ eflation, pour l’approximation successive de toutes les racines d’un polynˆ ome.
La m´ ethode de Horner est fond´ ee sur le fait que tout polynˆ ome p n ∈ P n
peut ˆ etre ´ ecrit sous la forme
p n (x) = a 0 + x(a 1 + x(a 2 + . . . + x(a n−1 + a n x) . . .)).
(6.25)
Les formules (6.24) et (6.25) sont ´ equivalentes d’un point de vue alg´ ebrique ;
n´ eanmoins, (6.24) n´ ecessite n sommes et 2n − 1 multiplications pour ´ evaluer
p n (x), tandis que (6.25) ne requiert que n sommes et n multiplications. La
seconde expression, parfois appel´ ee algorithme des multiplications emboˆ ıt´ ees,
est l’ingr´ edient de base de la m´ ethode de Horner. Cette m´ ethode ´ evalue efficacement le polynˆ ome p n au point z par l’algorithme de division synth´ etique
suivant
b n = a n ,
b k = a k + b k+1 z, k = n − 1, n − 2, ..., 0.
(6.26)
L’algorithme de division synth´ etique (6.26) est impl´ ement´ e dans le Programme 48. Les coefficients a j du polynˆ ome sont stock´ es dans le vecteur a, en
commen¸ cant par a n .
Programme 48 - horner : Algorithme de division synth´ etique
function [pnz,b] = horner(a,n,z)
%HORNER Algorithme de division synth´ etique.
% [PNZ,B]=HORNER(A,N,Z) ´ evalue avec la m´ ethode de Horner un polynˆ ome
% de degr´ e N et de coefficients A(1),...,A(N) au point Z.
b(1)=a(1);
for j=2:n+1
b(j)=a(j)+b(j-1)*z;
end
pnz=b(n+1);
return