2.6 Polynômes
71
%
d ’ une donnée initiale X0 . L ’ a l g o rith me s ’ arrête
%
après 100 i t e r ation s ou quand la valeur absolue de
%
la d i f f ére nce entre deux itérées c o n s éc utiv es est
%
plus petite que 1.e -04.
%
[ ROOTS , ITER ]= N E W T ONHO RNER(A , X0 , TOL , NMAX ) permet de
%
définir la t o l éran ce pour le critère d ’ arrêt et le
%
nombre maximal d ’ i t é ra tions.
if nargin == 2
tol = 1.e -04; nmax = 100;
elseif nargin == 3
nmax = 100;
end
n = length ( a ) -1; roots = zeros (n ,1); iter = zeros (n ,1);
for k = 1:n
% I t é r ation de Newton
niter = 0; x = x0 ; diff = tol + 1;
while niter < nmax & diff >= tol
[ pz ,b ] = horner (a , x ); [ dpz ,b ] = horner (b , x );
xnew = x - pz/ dpz;
diff = abs( xnew - x );
niter = niter + 1;
x = xnew ;
end
if ( niter == nmax & diff > tol)
fprintf ([ ’Ne converge pas après avoir atteint ’ ,...
’ le nombre maximum d ’ ’ i t é r ation s\n ’]);
end
% D é f l ation
[pz , a] = horner (a ,x ); roots (k ) = x ; iter (k ) = niter ;
end
return
Remarque 2.2 Pour minimiser la propagation des erreurs d’arrondi au cours
du processus de déflation, il vaut mieux commencer par approcher la racine r1
de module minimal, puis passer au calcul des autres racines r2, r3, . . ., jusqu’à
atteindre celle de plus grand module (pour plus de détails, voir par exemple
[QSS07]).
Exemple 2.11 On utilise le Programme 2.6 pour calculer les racines {1, 2, 3}
du polynôme p3(x) = x
3 − 6x
2 + 11x − 6. On entre les instructions suivantes :
a =[1 -6 11 -6]; [x , niter ]= n e w t o nhor ner(a ,0 ,1.e -15 ,100)
x =
1
2
3
niter =
8
8
2
La méthode fournit les trois racines avec précision et en quelques itérations.
Cependant, comme signalé à la Remarque 2.2, la méthode n’est pas toujours
aussi efficace. Par exemple, pour calculer les racines du polynôme p4(x) =
x
4 − 7x
3 + 15x
2 − 13x + 4 (qui admet la racine 1 de multiplicité 3 et la racine
simple 4), on trouve les valeurs suivantes :
71
%
d ’ une donnée initiale X0 . L ’ a l g o rith me s ’ arrête
%
après 100 i t e r ation s ou quand la valeur absolue de
%
la d i f f ére nce entre deux itérées c o n s éc utiv es est
%
plus petite que 1.e -04.
%
[ ROOTS , ITER ]= N E W T ONHO RNER(A , X0 , TOL , NMAX ) permet de
%
définir la t o l éran ce pour le critère d ’ arrêt et le
%
nombre maximal d ’ i t é ra tions.
if nargin == 2
tol = 1.e -04; nmax = 100;
elseif nargin == 3
nmax = 100;
end
n = length ( a ) -1; roots = zeros (n ,1); iter = zeros (n ,1);
for k = 1:n
% I t é r ation de Newton
niter = 0; x = x0 ; diff = tol + 1;
while niter < nmax & diff >= tol
[ pz ,b ] = horner (a , x ); [ dpz ,b ] = horner (b , x );
xnew = x - pz/ dpz;
diff = abs( xnew - x );
niter = niter + 1;
x = xnew ;
end
if ( niter == nmax & diff > tol)
fprintf ([ ’Ne converge pas après avoir atteint ’ ,...
’ le nombre maximum d ’ ’ i t é r ation s\n ’]);
end
% D é f l ation
[pz , a] = horner (a ,x ); roots (k ) = x ; iter (k ) = niter ;
end
return
Remarque 2.2 Pour minimiser la propagation des erreurs d’arrondi au cours
du processus de déflation, il vaut mieux commencer par approcher la racine r1
de module minimal, puis passer au calcul des autres racines r2, r3, . . ., jusqu’à
atteindre celle de plus grand module (pour plus de détails, voir par exemple
[QSS07]).
Exemple 2.11 On utilise le Programme 2.6 pour calculer les racines {1, 2, 3}
du polynôme p3(x) = x
3 − 6x
2 + 11x − 6. On entre les instructions suivantes :
a =[1 -6 11 -6]; [x , niter ]= n e w t o nhor ner(a ,0 ,1.e -15 ,100)
x =
1
2
3
niter =
8
8
2
La méthode fournit les trois racines avec précision et en quelques itérations.
Cependant, comme signalé à la Remarque 2.2, la méthode n’est pas toujours
aussi efficace. Par exemple, pour calculer les racines du polynôme p4(x) =
x
4 − 7x
3 + 15x
2 − 13x + 4 (qui admet la racine 1 de multiplicité 3 et la racine
simple 4), on trouve les valeurs suivantes :