234
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
En ´ ecrivant p 2 (x
(3) ) = 0, on en d´ eduit
x
(3) = x
(2) +
−w ±
w
2
− 4f(x
(2) )f[x
(2) , x
(1) , x
(0) ]
1/2
2f[x (2) , x (1) , x (0) ]
.
On doit faire des calculs similaires pour trouver x
(4) ` a partir de x
(1) , x
(2) et
x
(3) et, plus g´ en´ eralement, pour trouver x
(k+1) ` a partir de x
(k−2) , x
(k−1) et
x
(k) , avec k ≥ 2, grˆ ace ` a la formule suivante
x
(k+1) = x
(k)
−
2f(x
(k) )
w ∓
w 2 − 4f(x (k) )f[x (k) , x (k−1) , x (k−2) ]
1/2 .
(6.30)
Le signe dans (6.30) est choisi de mani` ere ` a maximiser le module du d´ enominateur. Si on suppose que f ∈ C
3 (J ) dans un voisinage J de la racine α, avec
f
(α) = 0, l’ordre de convergence est presque quadratique. Plus pr´ ecis´ ement,
l’erreur e
(k) = α −x
(k) ob´ eit ` a la relation suivante (voir [Hil87] pour la preuve)
lim
k→∞
|e
(k+1)
|
|e (k) | p =
1
6
f
(α)
f (α)
,
p 1.84.
Exemple 6.7 Utilisons la m´ ethode de Muller pour approcher les racines du polynˆ ome p6 de l’Exemple 6.6. La tol´ erance pour le test d’arrˆ et est tol = 10
−6 , et les
donn´ ees pour (6.30) sont x
(0) = −5, x
(1) = 0 et x
(2) = 5. Nous indiquons dans la
Table 6.4 les racines approch´ ees de p6, not´ ees sj et rj (j = 1, . . . , 5), o` u, comme
dans l’Exemple 6.6, sj et rj ont ´ et´ e obtenues respectivement avec et sans raffinement. Pour calculer les racines rj , on a effectu´ e respectivement 12, 11, 9, 9, 2 et 1
it´ erations, et seulement une it´ eration suppl´ ementaire pour le raffinement de toutes
les racines.
On peut encore noter dans cette exemple l’efficacit´ e de la proc´ edure de raffinement, bas´ ee sur la m´ ethode de Newton, pour am´ eliorer la pr´ ecision des solutions
fournies par (6.30).
•
La m´ ethode de Muller est impl´ ement´ ee en MATLAB dans le Programme 50,
pour le cas particulier o` u f est un polynˆ ome de degr´ e n. Le proc´ ed´ e de d´ eflation
Table 6.4. Les racines du polynˆ ome p6 obtenues avec la m´ ethode de Muller sans
raffinement (rj) et avec raffinement (sj)
r j
s j
r 1
1 + i2.2 · 10
−15
s 1 1 + i9.9 · 10
−18
r 2
−1 − i8.4 · 10
−16
s 2
-1
r 3
0.99 + i
s 3
1 + i
r 4
0.99 − i
s 4
1 − i
r 5 −1.1 · 10
−15 + i1.99 s 5
i2
r 6
−1.0 · 10
−15
− i2
s 6
-i2
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
En ´ ecrivant p 2 (x
(3) ) = 0, on en d´ eduit
x
(3) = x
(2) +
−w ±
w
2
− 4f(x
(2) )f[x
(2) , x
(1) , x
(0) ]
1/2
2f[x (2) , x (1) , x (0) ]
.
On doit faire des calculs similaires pour trouver x
(4) ` a partir de x
(1) , x
(2) et
x
(3) et, plus g´ en´ eralement, pour trouver x
(k+1) ` a partir de x
(k−2) , x
(k−1) et
x
(k) , avec k ≥ 2, grˆ ace ` a la formule suivante
x
(k+1) = x
(k)
−
2f(x
(k) )
w ∓
w 2 − 4f(x (k) )f[x (k) , x (k−1) , x (k−2) ]
1/2 .
(6.30)
Le signe dans (6.30) est choisi de mani` ere ` a maximiser le module du d´ enominateur. Si on suppose que f ∈ C
3 (J ) dans un voisinage J de la racine α, avec
f
(α) = 0, l’ordre de convergence est presque quadratique. Plus pr´ ecis´ ement,
l’erreur e
(k) = α −x
(k) ob´ eit ` a la relation suivante (voir [Hil87] pour la preuve)
lim
k→∞
|e
(k+1)
|
|e (k) | p =
1
6
f
(α)
f (α)
,
p 1.84.
Exemple 6.7 Utilisons la m´ ethode de Muller pour approcher les racines du polynˆ ome p6 de l’Exemple 6.6. La tol´ erance pour le test d’arrˆ et est tol = 10
−6 , et les
donn´ ees pour (6.30) sont x
(0) = −5, x
(1) = 0 et x
(2) = 5. Nous indiquons dans la
Table 6.4 les racines approch´ ees de p6, not´ ees sj et rj (j = 1, . . . , 5), o` u, comme
dans l’Exemple 6.6, sj et rj ont ´ et´ e obtenues respectivement avec et sans raffinement. Pour calculer les racines rj , on a effectu´ e respectivement 12, 11, 9, 9, 2 et 1
it´ erations, et seulement une it´ eration suppl´ ementaire pour le raffinement de toutes
les racines.
On peut encore noter dans cette exemple l’efficacit´ e de la proc´ edure de raffinement, bas´ ee sur la m´ ethode de Newton, pour am´ eliorer la pr´ ecision des solutions
fournies par (6.30).
•
La m´ ethode de Muller est impl´ ement´ ee en MATLAB dans le Programme 50,
pour le cas particulier o` u f est un polynˆ ome de degr´ e n. Le proc´ ed´ e de d´ eflation
Table 6.4. Les racines du polynˆ ome p6 obtenues avec la m´ ethode de Muller sans
raffinement (rj) et avec raffinement (sj)
r j
s j
r 1
1 + i2.2 · 10
−15
s 1 1 + i9.9 · 10
−18
r 2
−1 − i8.4 · 10
−16
s 2
-1
r 3
0.99 + i
s 3
1 + i
r 4
0.99 − i
s 4
1 − i
r 5 −1.1 · 10
−15 + i1.99 s 5
i2
r 6
−1.0 · 10
−15
− i2
s 6
-i2