230
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
Une fois que les it´ erations (6.29) ont converg´ e, on effectue l’´ etape de d´ eflation.
Celle-ci est facilit´ ee par le fait que p n (x) = (x−r j )p n−1 (x). On recherche alors
l’approximation d’une racine de p n−1 (x) et ainsi de suite jusqu’` a ce que toutes
les racines de p n aient ´ et´ e calcul´ ees.
En notant n k = n − k le degr´ e du polynˆ ome obtenu `
a chaque it´ eration
du processus de d´ eflation, pour k = 0, . . . , n − 1, le coˆ ut de chaque it´ eration
de l’algorithme de Newton-Horner (6.29) est ´ egal ` a 4n k . Si r j ∈ C, il est
n´ ecessaire de travailler en arithm´ etique complexe et de prendre r
(0)
j
∈ C ;
autrement la m´ ethode de Newton-Horner (6.29) conduit `
a une suite {r
(k)
j } de
nombres r´ eels.
Le processus de d´ eflation peut ˆ etre affect´ e par des erreurs d’arrondi et
peut donc conduire `
a des r´ esultats impr´ ecis. Pour am´ eliorer sa stabilit´ e, on
peut commencer par approcher la racine r 1 de module minimum, qui est la
plus sensible au mauvais conditionnement du probl` eme (voir Exemple 2.7,
Chapitre 2) puis continuer avec les racines suivantes r 2 , . . ., jusqu’` a ce que la
racine de module maximum ait ´ et´ e calcul´ ee. Pour localiser r 1 , on peut utiliser
les techniques d´ ecrites ` a la Section 5.1 ou la m´ ethode des suites de Sturm (voir
[IK66], p. 126).
On peut encore am´ eliorer la pr´ ecision en proc´ edant comme suit. Une fois
calcul´ ee une approximation
r j de la racine r j , on retourne au polynˆ ome original p n et on construit par la m´ ethode de Newton-Horner (6.29) une nouvelle
approximation de r j en prenant r
(0)
j = r j comme donn´ ee initiale. Cette combinaison de d´ eflation et de correction de la racine est appel´ ee m´ ethode de
Newton-Horner avec raffinement.
Exemple 6.6 Examinons les performances de la m´ ethode de Newton-Horner dans
deux cas : dans le premier cas, le polynˆ ome n’admet que des racines r´ eelles, et dans
le second il admet deux paires de racines complexes conjugu´ ees. Nous avons impl´ ement´ e (6.29) en activant ou en d´ esactivant le raffinement afin d’en ´ etudier l’influence
(m´ ethodes NwtRef et Nwt respectivement). Les racines approch´ ees obtenues avec la
m´ ethode Nwt sont not´ ees rj , tandis que les sj d´ esignent celles calcul´ ees par NwtRef.
Pour les tests num´ eriques, les calculs ont ´ et´ e effectu´ es en arithm´ etique complexe,
avec x
(0) = 0 + i 0 (o` u i =
√
−1), nmax = 100 et tol = 10
−5 . La tol´ erance pour le
crit` ere d’arrˆ et dans la boucle de raffinement a ´ et´ e fix´ ee ` a 10
−3 · tol.
1) p5(x) = x
5 + x
4 − 9x
3 − x
2 + 20x − 12 = (x − 1)
2 (x − 2)(x + 2)(x + 3).
Nous indiquons dans les Tables 6.2(a) et 6.2(b) les racines approch´ ees rj (j =
1, . . . , 5) et le nombre d’it´ erations de Newton (Nit) effectu´ ees pour obtenir chacune
d’elles ; dans le cas de la m´ ethode NwtRef, nous donnons aussi le nombre d’it´ erations
suppl´ ementaires n´ ecessaires au raffinement (Extra).
Remarquer la nette am´ elioration de la pr´ ecision apport´ ee par le raffinement, mˆ eme
avec peu d’it´ erations suppl´ ementaires.
2) p6(x) = x
6 − 2x
5 + 5x
4 − 6x
3 + 2x
2 + 8x − 8.
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
Une fois que les it´ erations (6.29) ont converg´ e, on effectue l’´ etape de d´ eflation.
Celle-ci est facilit´ ee par le fait que p n (x) = (x−r j )p n−1 (x). On recherche alors
l’approximation d’une racine de p n−1 (x) et ainsi de suite jusqu’` a ce que toutes
les racines de p n aient ´ et´ e calcul´ ees.
En notant n k = n − k le degr´ e du polynˆ ome obtenu `
a chaque it´ eration
du processus de d´ eflation, pour k = 0, . . . , n − 1, le coˆ ut de chaque it´ eration
de l’algorithme de Newton-Horner (6.29) est ´ egal ` a 4n k . Si r j ∈ C, il est
n´ ecessaire de travailler en arithm´ etique complexe et de prendre r
(0)
j
∈ C ;
autrement la m´ ethode de Newton-Horner (6.29) conduit `
a une suite {r
(k)
j } de
nombres r´ eels.
Le processus de d´ eflation peut ˆ etre affect´ e par des erreurs d’arrondi et
peut donc conduire `
a des r´ esultats impr´ ecis. Pour am´ eliorer sa stabilit´ e, on
peut commencer par approcher la racine r 1 de module minimum, qui est la
plus sensible au mauvais conditionnement du probl` eme (voir Exemple 2.7,
Chapitre 2) puis continuer avec les racines suivantes r 2 , . . ., jusqu’` a ce que la
racine de module maximum ait ´ et´ e calcul´ ee. Pour localiser r 1 , on peut utiliser
les techniques d´ ecrites ` a la Section 5.1 ou la m´ ethode des suites de Sturm (voir
[IK66], p. 126).
On peut encore am´ eliorer la pr´ ecision en proc´ edant comme suit. Une fois
calcul´ ee une approximation
r j de la racine r j , on retourne au polynˆ ome original p n et on construit par la m´ ethode de Newton-Horner (6.29) une nouvelle
approximation de r j en prenant r
(0)
j = r j comme donn´ ee initiale. Cette combinaison de d´ eflation et de correction de la racine est appel´ ee m´ ethode de
Newton-Horner avec raffinement.
Exemple 6.6 Examinons les performances de la m´ ethode de Newton-Horner dans
deux cas : dans le premier cas, le polynˆ ome n’admet que des racines r´ eelles, et dans
le second il admet deux paires de racines complexes conjugu´ ees. Nous avons impl´ ement´ e (6.29) en activant ou en d´ esactivant le raffinement afin d’en ´ etudier l’influence
(m´ ethodes NwtRef et Nwt respectivement). Les racines approch´ ees obtenues avec la
m´ ethode Nwt sont not´ ees rj , tandis que les sj d´ esignent celles calcul´ ees par NwtRef.
Pour les tests num´ eriques, les calculs ont ´ et´ e effectu´ es en arithm´ etique complexe,
avec x
(0) = 0 + i 0 (o` u i =
√
−1), nmax = 100 et tol = 10
−5 . La tol´ erance pour le
crit` ere d’arrˆ et dans la boucle de raffinement a ´ et´ e fix´ ee ` a 10
−3 · tol.
1) p5(x) = x
5 + x
4 − 9x
3 − x
2 + 20x − 12 = (x − 1)
2 (x − 2)(x + 2)(x + 3).
Nous indiquons dans les Tables 6.2(a) et 6.2(b) les racines approch´ ees rj (j =
1, . . . , 5) et le nombre d’it´ erations de Newton (Nit) effectu´ ees pour obtenir chacune
d’elles ; dans le cas de la m´ ethode NwtRef, nous donnons aussi le nombre d’it´ erations
suppl´ ementaires n´ ecessaires au raffinement (Extra).
Remarquer la nette am´ elioration de la pr´ ecision apport´ ee par le raffinement, mˆ eme
avec peu d’it´ erations suppl´ ementaires.
2) p6(x) = x
6 − 2x
5 + 5x
4 − 6x
3 + 2x
2 + 8x − 8.