70
2 Equations non linéaires
2.6.2 Méthode de Newton-Hörner
Comme son nom le suggère, la méthode de Newton-Hörner consiste en
une procédure de déflation utilisant la méthode de Newton pour calculer
les racines r m . L’intérêt réside dans le fait que la méthode de Newton
est implémentée de manière à exploiter au mieux l’algorithme de Hörner
(2.31). Soit q n−1 le polynôme associé à p n défini en (2.32), puisque
p
n (x) = q n−1 (x; z) + (x − z)q
n−1 (x; z),
on a
p
n (z) = q n−1 (z; z).
Grâce à cette identité, la méthode de Newton-Hörner pour l’approximation d’une racine (réelle ou complexe) r j de p n (j = 1, . . ., n) s’écrit :
étant donné une estimation initiale r
(0)
j
de la racine, calculer pour k ≥ 0
jusqu’à convergence
r
(k+1)
j
= r
(k)
j −
p n (r
(k)
j )
p
n (r
(k)
j )
= r
(k)
j −
p n (r
(k)
j )
q n−1 (r
(k)
j ; r
(k)
j )
(2.34)
On utilise alors une technique de déflation, exploitant le fait que p n (x) =
(x − r j )p n−1 (x). Puis on passe à la recherche d’un zéro de p n−1 , et ainsi
de suite jusqu’à ce que tous les zéros de p n aient été traités.
Puisque r j ∈ C, il est nécessaire d’effectuer le calcul en arithmétique
complexe, en prenant un r
(0)
j de partie imaginaire non nulle. Autrement,
la méthode de Newton-Hörner génère une suite {r
(k)
j } de nombres réels.
On a implémenté la méthode de Newton-Hörner dans le Programme 2.6. Les coefficients a j du polynôme dont on cherche les racines sont
stockés dans un vecteur a, de a n jusqu’à a 0 . Les autres paramètres d’entrée, tol et nmax, sont respectivement la tolérance du critère d’arrêt (valeur absolue de la différence entre deux itérées successives) et le nombre
maximal d’itérations. Si ces quantités ne sont pas définies, elles prennent
les valeurs par défaut nmax=100 et tol=1.e-04. En sortie, le programme
retourne respectivement dans les vecteurs roots et iter les racines calculées et le nombre d’itérations effectuées pour chacune d’elles.
Programme 2.6. newtonhorner : méthode de Newton-Hörner
function [ roots , iter ]= n e w t o nhorn er(a , x0 , tol , nmax )
% N E W T ON HORN ER méthode de Newton - Horner
%
[ ROOTS , ITER ]= N E W T ONHO RNER(A , X0) calcule les racines
%
du polynôme
%
P (X ) = A (1)* X^ N + A (2)* X ^(N -1)+...+ A( N )*X + A( N +1)
%
en u t i l isant la méthode de Newton - Horner d é m arran t
2 Equations non linéaires
2.6.2 Méthode de Newton-Hörner
Comme son nom le suggère, la méthode de Newton-Hörner consiste en
une procédure de déflation utilisant la méthode de Newton pour calculer
les racines r m . L’intérêt réside dans le fait que la méthode de Newton
est implémentée de manière à exploiter au mieux l’algorithme de Hörner
(2.31). Soit q n−1 le polynôme associé à p n défini en (2.32), puisque
p
n (x) = q n−1 (x; z) + (x − z)q
n−1 (x; z),
on a
p
n (z) = q n−1 (z; z).
Grâce à cette identité, la méthode de Newton-Hörner pour l’approximation d’une racine (réelle ou complexe) r j de p n (j = 1, . . ., n) s’écrit :
étant donné une estimation initiale r
(0)
j
de la racine, calculer pour k ≥ 0
jusqu’à convergence
r
(k+1)
j
= r
(k)
j −
p n (r
(k)
j )
p
n (r
(k)
j )
= r
(k)
j −
p n (r
(k)
j )
q n−1 (r
(k)
j ; r
(k)
j )
(2.34)
On utilise alors une technique de déflation, exploitant le fait que p n (x) =
(x − r j )p n−1 (x). Puis on passe à la recherche d’un zéro de p n−1 , et ainsi
de suite jusqu’à ce que tous les zéros de p n aient été traités.
Puisque r j ∈ C, il est nécessaire d’effectuer le calcul en arithmétique
complexe, en prenant un r
(0)
j de partie imaginaire non nulle. Autrement,
la méthode de Newton-Hörner génère une suite {r
(k)
j } de nombres réels.
On a implémenté la méthode de Newton-Hörner dans le Programme 2.6. Les coefficients a j du polynôme dont on cherche les racines sont
stockés dans un vecteur a, de a n jusqu’à a 0 . Les autres paramètres d’entrée, tol et nmax, sont respectivement la tolérance du critère d’arrêt (valeur absolue de la différence entre deux itérées successives) et le nombre
maximal d’itérations. Si ces quantités ne sont pas définies, elles prennent
les valeurs par défaut nmax=100 et tol=1.e-04. En sortie, le programme
retourne respectivement dans les vecteurs roots et iter les racines calculées et le nombre d’itérations effectuées pour chacune d’elles.
Programme 2.6. newtonhorner : méthode de Newton-Hörner
function [ roots , iter ]= n e w t o nhorn er(a , x0 , tol , nmax )
% N E W T ON HORN ER méthode de Newton - Horner
%
[ ROOTS , ITER ]= N E W T ONHO RNER(A , X0) calcule les racines
%
du polynôme
%
P (X ) = A (1)* X^ N + A (2)* X ^(N -1)+...+ A( N )*X + A( N +1)
%
en u t i l isant la méthode de Newton - Horner d é m arran t