6.4 Racines des ´ equations alg´ ebriques
233
x
(3)
f
p 2
x
(0) x
(1) x
(2)
Fig. 6.5. Une ´ etape de la m´ ethode de Muller
6.4.3 La m´ ethode de Muller
Un second exemple de d´ eflation utilise la m´ ethode de Muller pour d´ eterminer,
` a l’´ etape 1 de l’algorithme d´ ecrit ` a la Section 6.4.1, une approximation de la
racine r (voir [Mul56]). Contrairement `
a la m´ ethode de Newton ou `
a celle de
la s´ ecante, la m´ ethode de Muller est capable de calculer des z´ eros complexes
d’une fonction f, mˆ eme en partant d’une donn´ ee initiale r´ eelle ; de plus, sa
convergence est presque quadratique.
Une ´ etape de la m´ ethode de Muller est repr´ esent´ ee sur la Figure 6.5. Ce
sch´ ema est une extension de la m´ ethode de la s´ ecante dans laquelle on remplace
le polynˆ ome de degr´ e un introduit en (6.13) par un polynˆ ome du second degr´ e :
pour trois valeurs distinctes x
(0) , x
(1) et x
(2) , le nouveau point x
(3) est tel que
p 2 (x
(3) ) = 0, o` u p 2 ∈ P 2 est l’unique polynˆ ome qui interpole f aux points x
(i) ,
i = 0, 1, 2, i.e. p 2 (x
(i) ) = f(x
(i) ) pour i = 0, 1, 2. On a donc
p2(x) = f (x
(2) ) + (x − x
(2) )f [x
(2) , x
(1) ] + (x − x
(2) )(x − x
(1) )f [x
(2) , x
(1) , x
(0) ] ,
o` u
f[ξ, η] =
f(η) − f(ξ)
η − ξ
, f[ξ, η, τ ] =
f[η, τ ] − f[ξ, η]
τ − ξ
sont les diff´ erences divis´ ees d’ordre 1 et 2 associ´ ees aux points ξ, η et τ (voir
Section 7.2.1). En remarquant que x − x
(1) = (x − x
(2) ) + (x
(2)
− x
(1) ), on
obtient
p 2 (x) = f(x
(2) ) + w(x − x
(2) ) + f[x
(2) , x
(1) , x
(0) ](x − x
(2) )
2 ,
o` u
w = f[x
(2) , x
(1) ] + (x
(2)
− x
(1) )f[x
(2) , x
(1) , x
(0) ]
= f[x
(2) , x
(1) ] + f[x
(2) , x
(0) ] − f[x
(0) , x
(1) ] .