Método de Muller

El método de Muller es un algoritmo para encontrar 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 procede según una relación de recurrencia de tercer orden similar a la relación de recurrencia de segundo orden del método de la secante . Mientras que el método de la secante procede construyendo una línea que pasa por dos puntos en la gráfica de f correspondientes a las dos últimas aproximaciones iterativas y luego usa la raíz de la línea como la siguiente aproximación en cada iteración, por el contrario, el método de Muller usa tres puntos correspondientes a las tres últimas aproximaciones iterativas, construye una parábola que pasa por estos tres puntos y luego usa una raíz de la parábola como la siguiente aproximación en cada iteración.

El método de Muller utiliza tres aproximaciones iniciales de la raíz,${\displaystyle x_{0},x_{1}}$y${\displaystyle x_{2}}$y determina la siguiente aproximación${\displaystyle x_{3}}$al considerar la intersección del eje x con la parábola a través de${\displaystyle (x_{0},f(x_{0}))}$,${\displaystyle (x_{1},f(x_{1}))}$y${\displaystyle (x_{2},f(x_{2}))}$.

Consideremos el polinomio cuadrático $${\displaystyle P(x)=a(x-x_{2})^{2}+b(x-x_{2})+c,}$$

que pasa por${\displaystyle (x_{0},f(x_{0}))}$,${\displaystyle (x_{1},f(x_{1}))}$y${\displaystyle (x_{2},f(x_{2}))}$Para simplificar la notación, definamos las diferencias.

$${\displaystyle h_{0}=x_{1}-x_{0},\quad h_{1}=x_{2}-x_{1}}$$

y $${\displaystyle \delta _{0}={\frac {f(x_{1})-f(x_{0})}{h_{0}}},\quad \delta _{1}={\frac {f(x_{2})-f(x_{1})}{h_{1}}}.}$$

Sustituyendo cada uno de los tres puntos${\displaystyle (x_{0},f(x_{0}))}$,${\displaystyle (x_{1},f(x_{1}))}$y${\displaystyle (x_{2},f(x_{2}))}$en${\displaystyle P(x)}$y resolviendo simultáneamente para${\displaystyle a,b}$y${\displaystyle c}$da

$${\displaystyle a={\frac {\delta _{1}-\delta _{0}}{h_{1}+h_{0}}},\quad b=ah_{1}+\delta _{1},\quad c=f(x_{2}).}$$

Luego se aplica la fórmula cuadrática a${\displaystyle P(x)}$determinar${\displaystyle x_{3}}$como

${\displaystyle x_{3}-x_{2}={\frac {-2c}{b\pm {\sqrt {b^{2}-4ac}}}}.}$

El signo que precede al término radical se elige para que coincida con el signo de${\displaystyle b}$para asegurar que la siguiente iteración sea la más cercana a${\displaystyle x_{2}}$, donación

${\displaystyle x_{3}=x_{2}-{\frac {2c}{b+\operatorname {sign} (b){\sqrt {b^{2}-4ac}}}}.}$

Una vez${\displaystyle x_{3}}$Una vez determinado el resultado, el proceso se repite. Cabe destacar que, debido a la expresión radical en el denominador, las iteraciones pueden ser complejas incluso cuando las anteriores son 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 generalizada de Sidi o el método de Newton , cuyas iteraciones seguirán siendo reales si se parte de 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), según el problema.

El método se puede adoptar fácilmente para escenarios, como la detección de colisiones, donde no interesa la raíz más cercana, sino la más pequeña, reemplazando${\displaystyle \operatorname {sign} (b)}$con${\displaystyle \operatorname {sign} (-a)}$:

${\displaystyle x_{3}=x_{2}-{\frac {2c}{b-\operatorname {sign} (a){\sqrt {b^{2}-4ac}}}}.}$

El siguiente pseudocódigo describe el método de Muller para aproximar una raíz de la ecuación f(x) = 0. Devuelve una estimación.${\displaystyle x_{3}}$que satisface${\displaystyle |x_{3}-x_{2}|<\varepsilon }$, dónde${\displaystyle \varepsilon }$es una tolerancia especificada por el usuario.

entrada: función f , aproximaciones iniciales x0 , x1 , x2 , tolerancia ε , iteraciones máximas Nmax para n = 0 a Nmax hacer h0 ← x1 − x0 h1 ← x2 − x1 δ0 ← ( f ( x1 ) − f ( x0 )) / h0 δ1 ← ( f ( x2 ) − f ( x1 )) / h1 a ← ( δ1 − δ0 ) / ( h1 + h0 ) b ← a · h1 + δ1 c ← f ( x2 ) si b ≥ 0 entonces denominador ← b + sqrt( b ² − 4· a · c ) sino denominador ← b − sqrt( b ² − 4· a · c ) fin si x3 ← x2 − 2· c / denominador si | x3 − x2 | < ε entonces devolver x3 fin si x0 ← x1 x1 ← x2 x2 ← x3 fin para devolver x3

Supongamos que buscamos una solución del polinomio

${\displaystyle f(x)=-x^{3}-x+7\,.}$

Aplicación del método de Muller con estimaciones iniciales${\displaystyle x_{0}=1}$,${\displaystyle x_{1}=2}$y${\displaystyle x_{2}=3}$y una tolerancia de${\displaystyle 10^{-9}}$proporciona las siguientes aproximaciones:

Con la tolerancia requerida, el método de Muller genera la solución.${\displaystyle 1.7392038612200968}$en la sexta iteración.

Al modificar las estimaciones iniciales, el método de Muller también puede generar soluciones complejas. Aplicando el método de Muller nuevamente pero con estimaciones iniciales${\displaystyle x_{0}=-1}$,${\displaystyle x_{1}=-2}$y${\displaystyle x_{2}=-3}$y una tolerancia de${\displaystyle 10^{-9}}$proporciona las siguientes aproximaciones:

Con la tolerancia requerida, el método de Muller genera la solución compleja.${\displaystyle -0.8696019306084998-1.8079332269621338i}$en la octava iteración.

Para funciones bien comportadas, el orden de convergencia del método de Muller es aproximadamente 1,839, que coincide exactamente con la constante de Tribonacci . Esto se puede comparar con aproximadamente 1,618, que coincide exactamente con la proporción áurea , para el método de la secante , y con exactamente 2 para el método de Newton . Por lo tanto, el método de la secante avanza menos por iteración que el método de Muller, mientras que el método de Newton avanza más.

Más precisamente, si ξ denota una sola raíz de f (de modo que f (ξ) = 0 y f ' (ξ) ≠ 0), f es tres veces continuamente diferenciable, y las estimaciones iniciales x ₀ , x ₁ , y x ₂ se toman suficientemente cerca de ξ, entonces las iteraciones satisfacen

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

donde μ ≈ 1,84 es la solución positiva de${\displaystyle x^{3}-x^{2}-x-1=0}$, la ecuación que define la constante de Tribonacci.

El método de Muller ajusta una parábola, es decir, un polinomio de segundo orden , a los últimos tres puntos obtenidos f ( x _{k -1} ), f ( x _{k -2} ) y f ( 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 como 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 de la 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${\displaystyle x^{m+1}-x^{m}-x^{m-1}-\dots -x-1=0}$.

A medida que m tiende a infinito, la solución positiva de la ecuación tiende a 2. Sin embargo, el método es mucho más difícil para m > 2 que para m = 1 o m = 2, ya que es mucho más complicado determinar las raíces de un polinomio de grado 3 o superior. Otro problema es que no parece haber ninguna indicación sobre 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 con el método de la secante generalizada 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.

• Método de Halley , con convergencia cúbica
• El método de Householder incluye los métodos de Newton, Halley y de convergencia de orden superior.

• Atkinson, Kendall E. (1989). Introducción al análisis numérico , 2.ª edición, Sección 2.4. John Wiley & Sons, Nueva York. ISBN 0-471-50023-2.
• Burden, RL y Faires, JD Análisis numérico , 4ª edición, páginas 77 y siguientes.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 9.5.2. Método de Muller» . Numerical Recipes: The Art of Scientific Computing (3.ª  ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.

• Una variante de acotación con convergencia global: Costabile, F.; Gualtieri, MI; Luceri, R. (marzo de 2006). "Una modificación del método de Muller". Calcolo . 43 (1): 39– 50. doi : 10.1007/s10092-006-0113-9 . S2CID 124772103 .