68
2 Equations non linéaires
Théorème 2.4 (Cauchy) Tous les zéros de p n sont inclus dans le
cercle Γ du plan complexe
Γ = {z ∈ C : |z| ≤ 1 + η}, où η = max
0≤k≤n−1
|a k /a n |. (2.29)
Cette propriété est rarement utile quand η 1 (pour le polynôme p 6 de
l’Exemple 2.10, on a η = 8, tandis que toutes les racines sont dans des
disques visiblement plus petits).
2.6.1 Algorithme de Hörner
Dans ce paragraphe, nous décrivons une méthode pour évaluer efficacement la valeur d’un polynôme (et de sa dérivée) en un point donné z. Cet
algorithme est à la base d’une procédure automatique, appelée méthode
de déflation, pour l’approximation progressive de toutes les racines d’un
polynôme.
D’un point de vue algébrique, (1.9) peut s’écrire de manière équivalente
p n (x) = a 0 + x(a 1 + x(a 2 + . . . + x(a n−1 + a n x) . . .)).
(2.30)
Tandis que (1.9) nécessite n sommes et 2n − 1 produits pour évaluer
p n (x) (pour un x donné), (2.30) ne requiert que n sommes et n produits.
L’expression (2.30), parfois appelée méthode des produits imbriqués, est
la base de l’algorithme de Hörner. Celui-ci permet d’évaluer de manière
efficace un polynôme p n en un point z en utilisant l’algorithme de division
synthétique
b n = a n ,
b k = a k + b k+1 z, k = n − 1, n − 2, ..., 0
(2.31)
Dans (2.31) tous les coefficients b k , avec k ≤ n − 1, dépendent de z et
on peut vérifier que b 0 = p n (z). Le polynôme
q n−1 (x; z) = b 1 + b 2 x + ... + b n x
n−1 =
n
k=1
b k x
k−1 ,
(2.32)
de degré n − 1 en x, dépend du paramètre z (via les coefficients b k ) et
est appelé polynôme associé à p n . On a implémenté l’Algorithme (2.31)
dans le Programme 2.5. Les coefficients a j du polynôme à évaluer sont
stockés dans un vecteur a, de a n à a 0 .
2 Equations non linéaires
Théorème 2.4 (Cauchy) Tous les zéros de p n sont inclus dans le
cercle Γ du plan complexe
Γ = {z ∈ C : |z| ≤ 1 + η}, où η = max
0≤k≤n−1
|a k /a n |. (2.29)
Cette propriété est rarement utile quand η 1 (pour le polynôme p 6 de
l’Exemple 2.10, on a η = 8, tandis que toutes les racines sont dans des
disques visiblement plus petits).
2.6.1 Algorithme de Hörner
Dans ce paragraphe, nous décrivons une méthode pour évaluer efficacement la valeur d’un polynôme (et de sa dérivée) en un point donné z. Cet
algorithme est à la base d’une procédure automatique, appelée méthode
de déflation, pour l’approximation progressive de toutes les racines d’un
polynôme.
D’un point de vue algébrique, (1.9) peut s’écrire de manière équivalente
p n (x) = a 0 + x(a 1 + x(a 2 + . . . + x(a n−1 + a n x) . . .)).
(2.30)
Tandis que (1.9) nécessite n sommes et 2n − 1 produits pour évaluer
p n (x) (pour un x donné), (2.30) ne requiert que n sommes et n produits.
L’expression (2.30), parfois appelée méthode des produits imbriqués, est
la base de l’algorithme de Hörner. Celui-ci permet d’évaluer de manière
efficace un polynôme p n en un point z en utilisant l’algorithme de division
synthétique
b n = a n ,
b k = a k + b k+1 z, k = n − 1, n − 2, ..., 0
(2.31)
Dans (2.31) tous les coefficients b k , avec k ≤ n − 1, dépendent de z et
on peut vérifier que b 0 = p n (z). Le polynôme
q n−1 (x; z) = b 1 + b 2 x + ... + b n x
n−1 =
n
k=1
b k x
k−1 ,
(2.32)
de degré n − 1 en x, dépend du paramètre z (via les coefficients b k ) et
est appelé polynôme associé à p n . On a implémenté l’Algorithme (2.31)
dans le Programme 2.5. Les coefficients a j du polynôme à évaluer sont
stockés dans un vecteur a, de a n à a 0 .