Méthode de Muller

La méthode de la sécante définit une relation de récurrence basée sur l'interpolation linéaire entre deux points. La méthode de Muller de par sa nature quadratique, nécessite trois points. On pose ainsi :

${\displaystyle q={\frac {x_{n}-x_{n-1}}{x_{n-1}-x_{n-2}}}}$

On définit ensuite trois termes :

${\displaystyle A=qf(x_{n})-q(1+q)f(x_{n-1})+q^{2}f(x_{n-2})~}$

${\displaystyle B=(2q+1)f(x_{n})-(1+q)^{2}f(x_{n-1})+q^{2}f(x_{n-2})~}$

${\displaystyle C=(1+q)f(x_{n})~}$

La relation de récurrence pour cette méthode est donnée finalement par :

${\displaystyle x_{n+1}=x_{n}-(x_{n}-x_{n-1}){\frac {2C}{\max {(B\pm {\sqrt {B^{2}-4AC}})}}}~}$

L'initialisation nécessite 3 points x₀, x₁ et x₂ qui sont proches, si possible, de la solution recherchée.

La vitesse de convergence de la méthode de Muller est approximativement 1,84 contre 1,62 pour la méthode de la sécante et 2 pour la méthode de Newton-Raphson.

Plus précisément, si ξ est une racine simple de f (ainsi f(ξ) = 0 et f'(ξ) ≠ 0), que f est trois fois continuement différentiable et que les points de départ x₀, x₁, et x₂ sont pris suffisamment près de ξ, alors les itérés vérifient

${\displaystyle \lim _{k\to \infty }{\frac {|x-x_{k}|}{|x-x_{k-1}|^{p}}}=\left|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(p-1)/2},}$

où p ≈ 1.84 est la racine positive de ${\displaystyle x^{3}-x^{2}-x-1=0}$.

• David E. Muller, A Method for Solving Algebraic Equations Using an Automatic Computer, Math. Comp. 10 (1956), 208-215 [PDF]
• Kendall E. Atkinson, An Introduction to Numerical Analysis, 2^d edition, 1988, Section 2.4. John Wiley & Sons, New York. (ISBN 0-471-50023-2).
• R. L. Burden, J. D. Faires, Numerical Analysis, 4th edition, pages 77ff.
• William H. Press et al. Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2^d edition, 1992, page 364. (ISBN 0-521-43064-X).