Méthode de Muller

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Méthode de Müller)
Aller à : navigation, rechercher

En mathématiques, la méthode de Muller est un algorithme de recherche d'un zéro d'une fonction qui est basé sur la méthode de la sécante mais qui utilise une approximation quadratique d'une partie de la fonction au lieu d'une approximation linéaire. Ceci offre une convergence plus rapide que la méthode de la sécante. Une particularité de cette méthode est que le candidat issu de la recherche peut devenir complexe.

La méthode[modifier | modifier le code]

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 :

q = \frac{x_n - x_{n-1}}{x_{n-1} -x_{n-2}}

On définit ensuite trois termes :

A = qf(x_n) - q(1+q)f(x_{n-1})+q^2f(x_{n-2})~
B = (2q+1)f(x_n) - (1+q)^2  f(x_{n-1}) + q^2 f(x_{n-2})~
C = (1+q)f(x_n)~

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

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 x0, x1 et x2 qui sont proches, si possible, de la solution recherchée.

Vitesse de convergence[modifier | modifier le code]

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 x0, x1, et x2 sont pris suffisamment près de ξ, alors les itérés vérifient

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

p ≈ 1.84 est la racine positive de  x^3 - x^2 - x - 1 = 0 .

Références[modifier | modifier le code]

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