Método de Muller
# Método de Muller

O método de Muller é um método numérico para o cálculo de uma ou mais raízes de equações de uma variável baseado em uma aproximação quadrática. Foi proposto inicialmente por David E. Muller em 1956. Conhecendo-se o intervalo [x0, x2] ao qual a raiz pertence, é feita uma aproximação da função f(x) na proximidade da raiz ξ com um polinômio interpolador de grau 2. O polinômio deve passar pelos três pontos [x0, f(x0)], [x1, f(x1)] e [x2, f(x2)] interpolados e então a raiz do polinômio será a primeira estimativa da raiz de f(x)=0. Novas iterações são feitas repetindo esse procedimento com os três pontos mais próximos da raiz.
Essa técnica é uma modificação do Método das secantes, pois ao invés da aproximação ser feita pela reta que passa por dois pontos da curva, é feita pela parábola que passa por três pontos dados. Portanto, a estimativa para a raiz é melhor pelo método de Muller do que pelo das Secantes.
Além disso, esse método é válido para a calcular de raiz de qualquer problema, especialmente no caso de polinômios, pois pode aproximar raízes complexas também.

## Relação de Recorrência

O método de Muller é um método recursivo que gera uma aproximação da raiz ξ da função f a cada iteração. Começando com três valores iniciais X$_0$, X$_1$ e X$_2$, a primeira iteração calcula a primeira aproximação X$_1$, a segunda iteração calcula a segunda aproximação X$_2$, a terceira iteração calcula a terceira aproximação X$_3$ e assim por diante até a K-ésima iteração que gera a aproximação X$_K$. Cada iteração leva em conta as três útimas aproximações geradas e o valor de f nessas aproximações. Portanto, a K-ésima iteração recebe como entrada os valores de X$_{K-1}$, X$_{K-2}$ e X$_{K-3}$ e os valores de f(X$_{K-1}$), f(X$_{K-2}$) e f(X$_{K-3}$). A aproximação X$_K$ pode, então, ser calculada construíndo uma parábola y$_k$(x) que passa pelos três pontos (x$_{k-1}$, f(x$_{k-1}$)), (x$_{k-2}$, f(x$_{k-2}$)) e (x$_{k-3}$, f(x$_{k-3}$)) e pode ser escrita pela fórmula de Newton como:
$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}],\,$
onde $f[x_{k-1},x_{k-2}]$ e $f[x_{k-1},x_{k-2},x_{k-3}]$ são operadores de diferenças divididas.
Essa equação pode ser reescrita como:
$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},\,$
onde $w=f[x_{k-1},x_{k-2}]+f[x_{k-1},x_{k-3}]-f[x_{k-2},x_{k-3}].\,$
A próxima iteração x$_k$ é então dada como a solução mais próxima de x$_{k-1}$ da equação quadrática y$_k$(x) = 0. Isso produz a relação de recorrência dada por:
$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}]}}}}$
Nessa fórmula, deve ser escolhido o sinal de forma que o denominador seja o maior possível em módulo. (Não é usada a fórmula padrão para resolver equações quadráticas porque isso pode levar à perda de significância).
Pode-se observar que x$_k$ pode ser um número complexo, mesmo se as iterações anteriores forem todas raizes reais. Isso está em contraste com os outros métodos de obtenção de raízes, como o método da secante, o método da secante generalizada de Sindi ou o método de Newton, cujas iterações permanecerão reais se começarmos com números reais. Mas dependendo do problema, ter iterações complexas poderá ser uma vantagem, se estiver procurando raízes complexas, ou uma desvantagem, se for determinado que todas as raízes são reais.

## Dedução da Relação de Recorrência

O método consiste em um esquema iterativo em que a aproximação x$_{i+1}$ é calculada como uma função de das três últimas aproximações:
    $x_{i+1}=\phi \left(x_{i},x_{i-1},x_{i-2}\right)$
Neste esquema, x$_{i+1}$ é definida como a raiz mais próxima de x$_i$ do polinômio quadrático que interpola os pontos (x$_i$,y$_i$), (x$_{i-1}$,y$_{i-1}$) e (x$_{i-2}$,y$_{i-2}$).
Primeiramente, consideramos um polinômio quadrático conveniente:
    $P(x)=a(x-x_{i-1})^{2}+b(x-x_{i-1})+c$
Como o polinômio passa pelos pontos (x$_{i-2}$, f (x$_{i-2}$)), (x$_{i-1}$, f (x$_{i-1}$)) e (x$_i$, f (x$_i$)) ,temos o conjunto de equações (1):
    $P(x_{i-2})=a(x_{i-2}-x_{i-1})^{2}+b(x_{i-2}-x_{i-1})+c=f(x_{i-2})$
    $P(x_{i-1})=a(x_{i-1}-x_{i-1})^{2}+b(x_{i-1}-x_{i-1})+c=c=f(x_{i-2})$
    $P(x_{i})=a(x_{i}-x_{i-1})^{2}+b(x_{i}-x_{i-1})+c=f(x_{i})$
Definindo
    $h_{1}=x_{i}-x_{i-1}$
    $h_{2}=x_{i-1}-x_{i-2}$
e substituindo em (1), temos um sistema linear em função de a e b:
    $h_{2}^{2}a-h_{2}b=f(x_{i-2})-f(x_{i-1})$
    $h_{1}^{2}a+h_{1}b=f(x_{i})-f(x_{i-1})$
A solução é, então:
    $a={\frac {1}{h_{1}(h_{1}+h_{2})}}\left[f(x_{i})-\left({\frac {h_{1}}{h_{2}}}+1\right)f(x_{i-1})+\left({\frac {h_{1}}{h_{2}}}\right)f(x_{i-2})\right]$
    $b={\frac {1}{h_{1}}}(f(x_{i})-f(x_{i-1}))-ah_{1}$
A aproximação para a raiz da equação, que corresponde ao zero do polinômio é dada por báskara. No entanto, devido a problemas de estabilidade, essa solução é reescrita na forma de:
    $z=-{\frac {2c}{b\pm {\sqrt {b^{2}-4ac}}}}$
Assim, a relação de recorrência seria:
    $x_{i+1}=x_{i-1}-{\frac {2c}{b+sinal(b){\sqrt {b^{2}-4ac}}}}$
Como havíamos obtido dois resultados possíveis, mas estamos interessados na raiz mais próxima de x$_{i-1}$, devemos escolher o mesmo sinal de b para tornar o denominador o maior possível.

## Convergência do Método

O método de Muller tem taxa de convergência de aproximadamente 1,8393. Assim, o método converge relativamente rápido em geral, visto que o método das secantes apresenta taxa de convergência de 1,62 e o de Newton; 2,0. A convergência ocorre geralmente para qualquer aproximação inicial. No entanto, se a=0 o método será o próprio método das Secantes. Se a=b=0, então f (x$_{i-2}$)= f (x$_{i-1}$)=f (x$_i$) e não há convergência, pois o polinômio será reduzido a uma função constante.

## Velocidade de Convergência

A ordem de convergência do método de Muller é de aproximadamente 1,84. Isso pode ser comparado com 1,62 para o método da Secante e 2 para o método de Newton. Assim, o método da Secante faz menos progresso por iteração do que o método de Muller e o método de Newton faz mais progresso.
Mais precisamente, se $\xi$ denota uma única raiz de f (assim f($\xi$) = 0 e f'($\xi$) ≠ 0), f é três vezes continuamente diferente, e os palpites iniciais $x_{0}$, $x_{1}$, e $x_{2}$ são tomados suficientemente perto de $\xi$, então os iterados satisfazem:
$\lim _{k\to \infty }{\frac {|x_{k}-\xi |}{|x_{k-1}-\xi |^{\mu }}}=\left|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(\mu -1)/2}$,
onde μ ≈ 1,84 é a solução positiva de $x^{3}-x^{2}-x-1=0$.

## Generalizações e métodos relacionados

O método de Muller assume a forma de uma parábola, ou seja, um polinômio de segunda ordem, devido aos seus últimos três pontos obtidos: f (x $_{k-1}$), f (x $_{k-2}$) e f (x $_{k-3}$) em cada iteração. É possível generalizar isso e definir um polinômio p$_{k,m}$ (x) de grau m aos últimos m + 1 pontos na k-ésima iteração. Nossa parábola y$_k$ é escrita como p$_{k,2}$ nesta notação. Por isso, o grau m deve ser 1 ou maior.
A próxima aproximação x$_k$ é agora uma das raízes de p$_{k,m}$, ou seja, uma das soluções de p$_{k,m}$ (x) = 0. Então, se m = 1 obteremos o método da secante, entretanto se m = 2 teremos o método de Muller.
Muller calculou que a sequência {x$_k$}, gerada desta forma, converge para a raiz ξ, com uma ordem μ$_m$, onde μ$_m$ é uma solução positiva de x ^ (m + 1) - x ^ (m) -x ^ (m-1) - ...-x-1 = 0.
Entretanto, o método é muito mais difícil para m> 2 do que para m = 1 ou m = 2. Isso acontece porque é muito mais difícil determinar as raízes de um polinômio de grau 3 ou superior. Além disso, outro problema é que parece não haver recomendação de qual das raízes de p$_{k,m}$se deve escolher como a próxima aproximação x$_k$ para m> 2.
Por fim, essas dificuldades são superadas pelo método da secante generalizado de Sidi, que também utiliza o polinômio p$_{k,m}$. Por isso, em vez de tentar resolver p$_{k,m}$ (x) = 0, a próxima aproximação x$_k$ é calculada com o auxílio da derivada de p$_{k,m}$ em x$_{k-1}$ neste método.