214
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
Par exemple si ε = 10
−4 , le changement relatif est de 10
−1 . Remarquer que le second
membre de (6.7) vaut exactement
4
√
ε, donc, dans ce cas (6.7) est une ´ egalit´ e.
•
Exemple 6.2 Consid´ erons le polynˆ ome suivant (dit polynˆ ome de Wilkinson)
p10(x) = Π
10
k=1 (x + k) = x
10 + 55x
9 + . . . + 10!.
Soit ˆ
p10 = p10 + εx
9 , avec ε = 2
−23 1.2 · 10
−7 . Etudions le conditionnement de
la d´ etermination des racines de p10. En utilisant (6.7) avec m = 1, nous indiquons
dans la Table 6.1 les erreurs relatives E
i
rel et les estimations correspondantes S
i pour
i = 1, . . . , 10.
Ces r´ esultats montrent que le probl` eme est mal conditionn´ e, puisque la plus
grande erreur relative (correspondant `
a α8 = −8) est de trois ordres de grandeurs
sup´ erieure ` a la perturbation. On notera de plus la tr` es bonne ad´ equation entre les
estimations a priori et les erreurs relatives effectivement observ´ ees.
•
Table 6.1. Erreurs relatives observ´ ees et erreurs relatives estim´ ees en utilisant (6.7)
pour le polynˆ ome de Wilkinson de degr´ e 10
i
E
i
rel
S
i
i
E
i
rel
S
i
1 3.039 · 10
−13
3.285 · 10
−13
6 6.956 · 10
−5
6.956 · 10
−5
2 7.562 · 10
−10
7.568 · 10
−10
7 1.589 · 10
−4
1.588 · 10
−4
3 7.758 · 10
−8
7.759 · 10
−8
8 1.984 · 10
−4
1.987 · 10
−4
4 1.808 · 10
−6
1.808 · 10
−6
9 1.273 · 10
−4
1.271 · 10
−4
5 1.616 · 10
−5
1.616 · 10
−5
10 3.283 · 10
−5
3.286 · 10
−5
6.2 Une approche g´ eom´ etrique de la d´ etermination
des racines
Nous introduisons dans cette section les m´ ethodes de dichotomie (ou de bissection), de la corde, de la s´ ecante, de la fausse position (ou Regula Falsi)
et de Newton. Nous les pr´ esentons dans l’ordre de complexit´ e croissante des
algorithmes. Dans le cas de la m´ ethode de dichotomie, la seule information
utilis´ ee est le signe de la fonction f aux extr´ emit´ es de sous-intervalles, tandis
que pour les autres algorithmes on prend aussi en compte les valeurs de la
fonction et/ou de ses d´ eriv´ ees.
6.2.1 M´ ethode de dichotomie
La m´ ethode de dichotomie est fond´ ee sur la propri´ et´ e suivante :
Propri´ et´ e 6.1 (th´ eor` eme des z´ eros d’une fonction continue) Soit une
fonction continue f : [a, b] → R, si f(a)f(b) < 0, alors ∃ α ∈]a, b[ tel que
f(α) = 0.
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
Par exemple si ε = 10
−4 , le changement relatif est de 10
−1 . Remarquer que le second
membre de (6.7) vaut exactement
4
√
ε, donc, dans ce cas (6.7) est une ´ egalit´ e.
•
Exemple 6.2 Consid´ erons le polynˆ ome suivant (dit polynˆ ome de Wilkinson)
p10(x) = Π
10
k=1 (x + k) = x
10 + 55x
9 + . . . + 10!.
Soit ˆ
p10 = p10 + εx
9 , avec ε = 2
−23 1.2 · 10
−7 . Etudions le conditionnement de
la d´ etermination des racines de p10. En utilisant (6.7) avec m = 1, nous indiquons
dans la Table 6.1 les erreurs relatives E
i
rel et les estimations correspondantes S
i pour
i = 1, . . . , 10.
Ces r´ esultats montrent que le probl` eme est mal conditionn´ e, puisque la plus
grande erreur relative (correspondant `
a α8 = −8) est de trois ordres de grandeurs
sup´ erieure ` a la perturbation. On notera de plus la tr` es bonne ad´ equation entre les
estimations a priori et les erreurs relatives effectivement observ´ ees.
•
Table 6.1. Erreurs relatives observ´ ees et erreurs relatives estim´ ees en utilisant (6.7)
pour le polynˆ ome de Wilkinson de degr´ e 10
i
E
i
rel
S
i
i
E
i
rel
S
i
1 3.039 · 10
−13
3.285 · 10
−13
6 6.956 · 10
−5
6.956 · 10
−5
2 7.562 · 10
−10
7.568 · 10
−10
7 1.589 · 10
−4
1.588 · 10
−4
3 7.758 · 10
−8
7.759 · 10
−8
8 1.984 · 10
−4
1.987 · 10
−4
4 1.808 · 10
−6
1.808 · 10
−6
9 1.273 · 10
−4
1.271 · 10
−4
5 1.616 · 10
−5
1.616 · 10
−5
10 3.283 · 10
−5
3.286 · 10
−5
6.2 Une approche g´ eom´ etrique de la d´ etermination
des racines
Nous introduisons dans cette section les m´ ethodes de dichotomie (ou de bissection), de la corde, de la s´ ecante, de la fausse position (ou Regula Falsi)
et de Newton. Nous les pr´ esentons dans l’ordre de complexit´ e croissante des
algorithmes. Dans le cas de la m´ ethode de dichotomie, la seule information
utilis´ ee est le signe de la fonction f aux extr´ emit´ es de sous-intervalles, tandis
que pour les autres algorithmes on prend aussi en compte les valeurs de la
fonction et/ou de ses d´ eriv´ ees.
6.2.1 M´ ethode de dichotomie
La m´ ethode de dichotomie est fond´ ee sur la propri´ et´ e suivante :
Propri´ et´ e 6.1 (th´ eor` eme des z´ eros d’une fonction continue) Soit une
fonction continue f : [a, b] → R, si f(a)f(b) < 0, alors ∃ α ∈]a, b[ tel que
f(α) = 0.