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 procede de acuerdo con una relación de recurrencia de tercer orden similar a la relación de recurrencia de segundo orden del método secante . Mientras que el método secante procede construyendo una línea a través de dos puntos en el gráfico de f correspondientes a las dos últimas aproximaciones iterativas y luego utiliza la raíz de la línea como la siguiente aproximación en cada iteración, por el contrario, el método de Muller utiliza tres puntos correspondientes a las últimas tres aproximaciones iterativas, construye una parábola a través de estos tres puntos y luego utiliza una raíz de la parábola como la siguiente aproximación en cada iteración.
El método de Muller es un método recursivo que genera una nueva aproximación de una raíz ξ de f en cada iteración utilizando las tres iteraciones anteriores. Partiendo de tres valores iniciales x 0 , x −1 y x −2 , la primera iteración calcula una aproximación x 1 utilizando esos tres, la segunda iteración calcula una aproximación x 2 utilizando x 1 , x 0 y x −1 , la tercera iteración calcula una aproximación x 3 utilizando x 2 , x 1 y x 0 , y así sucesivamente: la k ésima iteración genera una aproximación x k utilizando x k-1 , x k-2 y x k-3 . Cada iteración toma como entrada las últimas tres aproximaciones generadas y el valor de f en estas aproximaciones: los valores x k -1 , x k -2 y x k -3 y los valores de función f ( x k -1 ), f ( x k -2 ) y f ( x k -3 ). La aproximación x k se calcula de la siguiente manera a partir de esos seis valores.
Primero, se construye una parábola y k ( x ) interpolando a través de 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 )) usando un polinomio 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 iteración x k se da entonces como la solución de la ecuación cuadrática y k ( x ) = 0 más cercana a x k -1 . En conjunto, esto implica la relación de recurrencia no lineal de tercer orden general [1]
donde el signo de la raíz cuadrada debe elegirse de manera que el denominador total sea lo más grande posible en magnitud.
Nótese que x k puede ser complejo incluso cuando las iteraciones 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 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.
Para funciones que se comportan bien, el orden de convergencia del método de Muller es aproximadamente 1,84 y exactamente la constante de Tribonacci . Esto se puede comparar con aproximadamente 1,62, exactamente 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 y el método de Newton avanza más.
Más precisamente, si ξ denota una raíz única de f (por lo que f (ξ) = 0 y f '(ξ) ≠ 0), f es tres veces continuamente diferenciable, y las conjeturas iniciales x 0 , x 1 y x 2 se toman suficientemente cerca de ξ, entonces las iteraciones satisfacen
donde μ ≈ 1,84 es la solución positiva de , la ecuación definitoria de la constante de Tribonacci.
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 ) 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 .
Sin embargo, el método es mucho más difícil para m >2 que para m =1 o m =2 porque es mucho más difícil determinar las raíces de un polinomio de grado 3 o superior. Otro problema es que no parece haber ninguna prescripció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 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.
A continuación, se implementa el método de Muller en el lenguaje de programación Python . Luego se aplica para encontrar una raíz de la función f ( x ) = x 2 − 612 .
![{\displaystyle y_{k}(x)=f(x_{k-1})+(x-x_{k-1})f[x_{k-1},x_{k-2}]+(x-x_{k-1})(x-x_{k-2})f[x_{k-1},x_{k-2},x_{k-3}],\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4fc666633edb20752cb468a206f851cbdf80a6b)
![{\displaystyle y_{k}(x)=f(x_{k-1})+w(x-x_{k-1})+f[x_{k-1},x_{k-2},x_{k-3}]\,(x-x_{k-1})^{2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c91020ad243a430cea8adf2006a934ceba38a25b)
![{\displaystyle w=f[x_{k-1},x_{k-2}]+f[x_{k-1},x_{k-3}]-f[x_{k-2},x_{k-3}].\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed105042af661129967a1df66fc7895e981ad762)
![{\displaystyle x_{k}=x_{k-1}-{\frac {2f(x_{k-1})}{w\pm {\sqrt {w^{2}-4f(x_{k-1})f[x_{k-1},x_{k-2},x_{k-3}]}}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/195fb4477b4db27f29bed7960be03801aabda944)
desde escribir import * desde cmath import sqrt # Use la raíz cuadrada compleja ya que podemos generar números complejosNum = Unión [ float , complex ] Func = Callable [[ Num ], Num ]def div_diff ( f : Func , xs : list [ Num ]): """Calcula la diferencia dividida f[x0, x1, ...]."" if len ( xs ) == 2 : a , b = xs return ( f ( a ) -f ( b )) / ( a - b ) else : return ( div_diff ( f , xs [ 1 : ]) - div_diff ( f , xs [ 0 : -1 ] ) ) / ( xs [ -1 ] -xs [ 0 ] ) def mullers_method ( f : Func , xs : ( Num , Num , Num ), iterations : int ) -> float : """Devuelve la raíz calculada utilizando el método de Muller.""" x0 , x1 , x2 = xs para _ en rango ( iterations ): w = div_diff ( f , ( x2 , x1 )) + div_diff ( f , ( x2 , x0 )) - div_diff ( f , ( x2 , x1 )) s_delta = sqrt ( w ** 2-4 * f ( x2 ) * div_diff ( f , ( x2 , x1 , x0 ) )) denoms = [ w + s_delta , w - s_delta ] # Toma el denominador de mayor magnitud x3 = x2-2 * f ( x2 ) / max ( denominaciones , clave = abs ) # Avanzar x0 , x1 , x2 = x1 , x2 , x3 devolver x3 def f_example ( x : Num ) -> Num : """La función de ejemplo. Con una función más costosa, puede resultar útil memorizar los últimos 4 puntos llamados.""" return x ** 2 - 612 raíz = método_mullers ( ejemplo_f , ( 10 , 20 , 30 ), 5 ) print ( "Raíz: {} " . formato ( raíz )) # Raíz: (24.738633317099097+0j)