6.4 Racines des ´ equations alg´ ebriques
229
Tous les coefficients b k d´ ependent de z et b 0 = p n (z). Le polynˆ ome
q n−1 (x; z) = b 1 + b 2 x + ... + b n x
n−1 =
n
k=1
b k x
k−1
(6.27)
est de degr´ e n−1 en la variable x et d´ epend du param` etre z par l’interm´ ediaire
des coefficients b k ; on l’appelle polynˆ ome associ´ e ` a p n .
Rappelons la propri´ et´ e de la division euclidienne :
´ etant donn´ e deux polynˆ omes h n ∈ P n et g m ∈ P m avec m ≤ n, il existe un
unique polynˆ ome δ ∈ P n−m et un unique polynˆ ome ρ ∈ P m−1 tels que
h n (x) = g m (x)δ(x) + ρ(x).
(6.28)
Ainsi, en divisant p n par x − z, on a
p n (x) = b 0 + (x − z)q n−1 (x; z),
o` u q n−1 (x; z) d´ esigne le quotient et b 0 le reste de la division. Si z est un z´ ero
de p n , alors b 0 = p n (z) = 0 et donc p n (x) = (x − z)q n−1 (x; z). Dans ce cas,
l’´ equation alg´ ebrique q n−1 (x; z) = 0 fournit les n − 1 autres z´ eros de p n (x).
Cette observation sugg` ere d’adopter l’algorithme suivant, dit de d´ eflation,
pour trouver les racines de p n :
pour m = n, n − 1, . . . , 1 :
1. trouver une racine r de p m en utilisant une m´ ethode d’approximation
ad´ equate ;
2. ´ evaluer q m−1 (x; r) par (6.26) ;
3. poser p m−1 = q m−1 .
Dans les deux prochaines sections, nous envisagerons des m´ ethodes de
d´ eflation particuli` eres en pr´ ecisant le choix de l’algorithme du point 1.
6.4.2 La m´ ethode de Newton-Horner
Dans ce premier exemple, on utilise la m´ ethode de Newton pour calculer la
racine r ` a l’´ etape 1 de l’algorithme de d´ eflation de la section pr´ ec´ edente. L’impl´ ementation de la m´ ethode de Newton exploite pleinement de l’algorithme de
Horner (6.26). En effet, si q n−1 est le polynˆ ome associ´ e ` a p n d´ efini en (6.27),
comme 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) (o` u p
n
est la d´ eriv´ ee de p n par rapport `
a x). Grˆ ace ` a cette identit´ e, la m´ ethode de
Newton-Horner pour l’approximation d’une racine (r´ eelle ou complexe) r j de
p n (j = 1, . . . , n) prend la forme suivante :
´ etant donn´ e une estimation initiale r
(0)
j
de la racine, r´ esoudre pour tout k ≥ 0
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 )
.
(6.29)
229
Tous les coefficients b k d´ ependent de z et b 0 = p n (z). Le polynˆ ome
q n−1 (x; z) = b 1 + b 2 x + ... + b n x
n−1 =
n
k=1
b k x
k−1
(6.27)
est de degr´ e n−1 en la variable x et d´ epend du param` etre z par l’interm´ ediaire
des coefficients b k ; on l’appelle polynˆ ome associ´ e ` a p n .
Rappelons la propri´ et´ e de la division euclidienne :
´ etant donn´ e deux polynˆ omes h n ∈ P n et g m ∈ P m avec m ≤ n, il existe un
unique polynˆ ome δ ∈ P n−m et un unique polynˆ ome ρ ∈ P m−1 tels que
h n (x) = g m (x)δ(x) + ρ(x).
(6.28)
Ainsi, en divisant p n par x − z, on a
p n (x) = b 0 + (x − z)q n−1 (x; z),
o` u q n−1 (x; z) d´ esigne le quotient et b 0 le reste de la division. Si z est un z´ ero
de p n , alors b 0 = p n (z) = 0 et donc p n (x) = (x − z)q n−1 (x; z). Dans ce cas,
l’´ equation alg´ ebrique q n−1 (x; z) = 0 fournit les n − 1 autres z´ eros de p n (x).
Cette observation sugg` ere d’adopter l’algorithme suivant, dit de d´ eflation,
pour trouver les racines de p n :
pour m = n, n − 1, . . . , 1 :
1. trouver une racine r de p m en utilisant une m´ ethode d’approximation
ad´ equate ;
2. ´ evaluer q m−1 (x; r) par (6.26) ;
3. poser p m−1 = q m−1 .
Dans les deux prochaines sections, nous envisagerons des m´ ethodes de
d´ eflation particuli` eres en pr´ ecisant le choix de l’algorithme du point 1.
6.4.2 La m´ ethode de Newton-Horner
Dans ce premier exemple, on utilise la m´ ethode de Newton pour calculer la
racine r ` a l’´ etape 1 de l’algorithme de d´ eflation de la section pr´ ec´ edente. L’impl´ ementation de la m´ ethode de Newton exploite pleinement de l’algorithme de
Horner (6.26). En effet, si q n−1 est le polynˆ ome associ´ e ` a p n d´ efini en (6.27),
comme 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) (o` u p
n
est la d´ eriv´ ee de p n par rapport `
a x). Grˆ ace ` a cette identit´ e, la m´ ethode de
Newton-Horner pour l’approximation d’une racine (r´ eelle ou complexe) r j de
p n (j = 1, . . . , n) prend la forme suivante :
´ etant donn´ e une estimation initiale r
(0)
j
de la racine, r´ esoudre pour tout k ≥ 0
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 )
.
(6.29)