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₀, X₁ e X₂, a primeira iteração calcula a primeira aproximação X₁, a segunda iteração calcula a segunda aproximação X₂, a terceira iteração calcula a terceira aproximação X₃ 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.

Bibliografia

• Burden, Richard L. e Faires, J. Douglas Análise Numérica 8ª edição Editora Cengage Learning pag 91
• Campos, filho, Frederico Ferreira. Algoritmos Numéricos 2ª edição Rio de Janeiro: LTC, 2007

Ligações externas

• O Método de Muller por Ricardo A. D. Zanardini
• Solução de Equações Não Lineares por Rudi Gaelzer