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
[editar | editar código-fonte]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 X0, X1 e X2, a primeira iteração calcula a primeira aproximação X1, a segunda iteração calcula a segunda aproximação X2, a terceira iteração calcula a terceira aproximação X3 e assim por diante até a K-ésima iteração que gera a aproximação XK. 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 XK-1, XK-2 e XK-3 e os valores de f(XK-1), f(XK-2) e f(XK-3). A aproximação XK pode, então, ser calculada construíndo uma parábola yk(x) que passa pelos três pontos (xk-1, f(xk-1)), (xk-2, f(xk-2)) e (xk-3, f(xk-3)) e pode ser escrita pela fórmula de Newton como:
onde e são operadores de diferenças divididas.
Essa equação pode ser reescrita como:
onde
A próxima iteração xk é então dada como a solução mais próxima de xk-1 da equação quadrática yk(x) = 0. Isso produz a relação de recorrência dada por:
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 xk 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
[editar | editar código-fonte]O método consiste em um esquema iterativo em que a aproximação xi+1 é calculada como uma função de das três últimas aproximações:
Neste esquema, xi+1 é definida como a raiz mais próxima de xi do polinômio quadrático que interpola os pontos (xi,yi), (xi-1,yi-1) e (xi-2,yi-2).
Primeiramente, consideramos um polinômio quadrático conveniente:
Como o polinômio passa pelos pontos (xi-2, f (xi-2)), (xi-1, f (xi-1)) e (xi, f (xi)) ,temos o conjunto de equações (1):
Definindo
e substituindo em (1), temos um sistema linear em função de a e b:
A solução é, então:
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:
Assim, a relação de recorrência seria:
Como havíamos obtido dois resultados possíveis, mas estamos interessados na raiz mais próxima de xi-1, devemos escolher o mesmo sinal de b para tornar o denominador o maior possível.
Convergência do Método
[editar | editar código-fonte]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 (xi-2)= f (xi-1)=f (xi) e não há convergência, pois o polinômio será reduzido a uma função constante.
Velocidade de Convergência
[editar | editar código-fonte]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 denota uma única raiz de f (assim f() = 0 e f'() ≠ 0), f é três vezes continuamente diferente, e os palpites iniciais , , e são tomados suficientemente perto de , então os iterados satisfazem:
,
onde μ ≈ 1,84 é a solução positiva de .
Interpretação Geométrica
[editar | editar código-fonte]Generalizações e métodos relacionados
[editar | editar código-fonte]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 pk,m (x) de grau m aos últimos m + 1 pontos na k-ésima iteração. Nossa parábola yk é escrita como pk,2 nesta notação. Por isso, o grau m deve ser 1 ou maior.[1]
A próxima aproximação xk é agora uma das raízes de pk, m, ou seja, uma das soluções de pk,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 {xk}, 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 pk,m se deve escolher como a próxima aproximação xk 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 pk,m. Por isso, em vez de tentar resolver pk,m (x) = 0, a próxima aproximação xk é calculada com o auxílio da derivada de pk,m em xk-1 neste método.[2]
- ↑ Atkinson, Kendall E. (1988). An introduction to numerical analysis Second edition ed. New York: [s.n.] OCLC 17551990
- ↑ Press, William H. (2007). Numerical recipes : the art of scientific computing. Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Cambridge University Press 3rd ed ed. Cambridge, UK: [s.n.] OCLC 123285342
Bibliografia
[editar | editar código-fonte]- 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