El método de Muller es un algoritmo de búsqueda de raíces , un método numérico para resolver ecuaciones de la forma f ( x ) = 0. Fue presentado por primera vez por David E. Muller en 1956.
El método de Muller se basa en el método de la secante , que construye en cada iteración una línea que pasa por dos puntos en la gráfica de f . En cambio, el método de Muller usa tres puntos, construye la parábola a través de estos tres puntos y toma la intersección del eje x con la parábola como la siguiente aproximación.
Relación de recurrencia
El método de Muller es un método recursivo que genera una aproximación de la raíz ξ de f en cada iteración. Comenzando con los tres valores iniciales x 0 , x −1 y x −2 , la primera iteración calcula la primera aproximación x 1 , la segunda iteración calcula la segunda aproximación x 2 , la tercera iteración calcula la tercera aproximación x 3 , etc. el k ésimo iteración genera aproximación x k . Cada iteración toma como entrada las tres últimas aproximaciones generadas y el valor de f en estas aproximaciones. Por tanto, la k- ésima iteración toma como entrada los valores x k -1 , x k -2 y x k -3 y los valores de la función f ( x k -1 ), f ( x k -2 ) yf ( x k -3 ). La aproximación x k se calcula de la siguiente manera.
Se construye una parábola y k ( x ) que pasa por los tres puntos ( x k -1 , f ( x k -1 )), ( x k -2 , f ( x k -2 )) y ( x k -3 , f ( x k -3 )). Cuando se escribe en la forma de Newton , y k ( x ) es
donde f [ x k -1 , x k -2 ] y f [ x k -1 , x k -2 , x k -3 ] denotan diferencias divididas . Esto se puede reescribir como
dónde
La siguiente iteración x k ahora se da como la solución más cercana a x k -1 de la ecuación cuadrática y k ( x ) = 0. Esto produce la relación de recurrencia
En esta fórmula, el signo debe elegirse de manera que el denominador sea lo más grande posible en magnitud. No usamos la fórmula estándar para resolver ecuaciones cuadráticas porque eso puede llevar a una pérdida de significancia .
Tenga en cuenta que x k puede ser complejo, incluso si las iteraciones anteriores fueran todas reales. Esto contrasta con otros algoritmos de búsqueda de raíces como el método de la secante , el método de la secante generalizado de Sidi o el método de Newton , cuyas iteraciones seguirán siendo reales si se comienza con números reales. Tener iteraciones complejas puede ser una ventaja (si se buscan raíces complejas) o una desventaja (si se sabe que todas las raíces son reales), dependiendo del problema.
Velocidad de convergencia
El orden de convergencia del método de Muller es aproximadamente 1,84. Esto se puede comparar con 1,62 para el método de la secante y 2 para el método de Newton . Entonces, el método de la secante progresa menos por iteración que el método de Muller y el método de Newton avanza más.
Más precisamente, si ξ denota una única raíz de f (entonces f (ξ) = 0 y f '(ξ) ≠ 0), f es tres veces continuamente diferenciable, y las suposiciones iniciales x 0 , x 1 y x 2 son tomado lo suficientemente cerca de ξ, entonces las iteraciones satisfacen
donde μ ≈ 1,84 es la solución positiva de .
El método de Muller ajusta una parábola, es decir, un polinomio de segundo orden , a los tres últimos puntos obtenidos f ( x k -1 ), f ( x k -2 ) yf ( x k -3 ) en cada iteración. Se puede generalizar esto y ajustar un polinomio p k, m ( x ) de grado m a los últimos m +1 puntos en la k- ésima iteración. Nuestra parábola y k se escribe p k , 2 en esta notación. El grado m debe ser 1 o mayor. La siguiente aproximación x k es ahora una de las raíces de p k, m , es decir, una de las soluciones de p k, m ( x ) = 0. Tomando m = 1 obtenemos el método secante mientras que m = 2 da el método de Muller.
Muller calculó que la secuencia { x k } generada de esta manera converge a la raíz ξ con un orden μ m donde μ m es la solución positiva de.
Sin embargo, el método es mucho más difícil para m > 2 que para m = 1 om = 2 porque es mucho más difícil determinar las raíces de un polinomio de grado 3 o superior. Otro problema es que parece no haber prescripción de cuál de las raíces de p k, m elegir como la siguiente aproximación x k para m > 2.
Estas dificultades se superan mediante el método secante generalizado de Sidi, que también emplea el polinomio p k, m . En lugar de intentar resolver p k, m ( x ) = 0, la siguiente aproximación x k se calcula con la ayuda de la derivada de p k, m en x k -1 en este método.
Referencias
- Muller, David E., "Un método para resolver ecuaciones algebraicas usando una computadora automática", Tablas matemáticas y otras ayudas a la computación , 10 (1956), 208-215. JSTOR 2001916
- Atkinson, Kendall E. (1989). Introducción al análisis numérico , segunda edición, sección 2.4. John Wiley & Sons, Nueva York. ISBN 0-471-50023-2 .
- Burden, RL and Faires, JD Numerical Analysis , 4ª edición, páginas 77 y siguientes.
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 9.5.2. Método de Muller" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.