Universidade Federal de Campina Grande
Departamento de Sistemas e Computação
Disciplina: Métodos e Software Numéricos
Prof.: José Eustáquio Rangel de Queiroz
MÓDULO V – Resolução de Equações Não Lineares
Notas de Aula 04
OUTROS MÉTODOS PARA
A DETERMINAÇÃO DE ZEROS
Embora os métodos enumerados a seguir não sejam originalmente
contemplados pelo programa da disciplina, alguns constituem métodos
alternativos dos métodos estudados, enquanto outros constituem o estado da
arte para a determinação de zeros de equações não lineares. T ais métodos são
referidos neste documento para fins de comparação.
1. Método de Muller (Muller , 1956; Press et al., 1992)
O método de Muller é uma generalização do método da Secante, no qual se
emprega interpolação quadrática entre 3 pontos ao invés de interpolação linear
entre 2, o que permite ao método determinar pares de raízes complexas. Dadas
3 aproximações para a raiz, xi−2, xi−1, xi e os valores do polinômio p(x) nos
referidos pontos, a próxima aproximação xi+1 será dada por:
q=
x i − xi−1
x i− 1 − x i − 2
A = qp (x i ) - q(1 + q)p(x i-1 ) + q 2 p(x i- 2 )
B = ( 2q + 1)p (x i ) - (1 + q) 2 p(x i- 1 ) + q 2 p(x i- 2 )
C = ( 1 + q)p (x i )
e
x i+ 1 = x i - (x i - x i- 1 )
2C
B ± B 2 − 4 AC
sendo o sinal (±) escolhido de modo a tornar seu valor absoluto tão grande
quanto possível.
Inicia-se o processo iterativo com quaisquer 3 valores de x, e.g., 3 valores
igualmente espaçados sobre o eixo real. Para a implementação do método, é
necessário atentar para a possibilidade de um denominador complexo e a
subseqüente aritmética complexa associada.
O método de Muller é, por vezes, empregado para a determinação de
aproximações para zeros complexos de funções analíticas (não apenas funções
polinomiais) no plano complexo.
2. Método de Laguerre (Press et al., 1992)
T rata-se de um método simples concebido pelo matemático francês Edmond
Nicolas Laguerre (1834-1886) para a computação numérica de uma raiz de um
polinômio arbitrário.
Segundo Press et al. (1992), o método de Laguerre é, de longe, o mais o
mais direto dos métodos genéricos e complexos, pois embora requeira um
processamento em aritmética complexa, mesmo quando converge para raízes
reais, sua convergência é garantida para uma das raízes de funções polinomiais
com todas as raízes reais. Para funções polinomiais com algumas raízes
complexas, pouco é teoricamente provado sobre a convergência do método.
Entretanto, muita experiência empírica sugere que a não convergência é
bastante rara e, além disto, pode quase sempre ser contornada a partir de uma
estratégia simples de quebrar o ciclo do limite de não convergência, como
ocorre, por exemplo, com polinômios de alta ordem (e.g. em torno de 20).
Em algumas instâncias, a aritmética complexa inerente ao método Laguerre
não constitui uma desvantagem, visto que o próprio polinômio pode ter
coeficientes complexos.
3. Método de Van Wijngaarden-Dekker-Brent (Riders, 1979; Press et al.,
1992)
O método de Van Wijngaarden-Dekker-Brent constitui um refinamento feito por
Richard Brent (1973) em um algoritmo originalmente concebido por Dekker
(1969). T rata-se de um método de 3 pontos que se fundamenta na combinação
dos métodos da Bissecção, Secante e Interpolação quadrática inversa calculada
sobre as ordenadas dos 3 últimos pontos disponíveis.
Usa-se o método quadrático e, se o resultado for um ponto fora do intervalo,
usa-se o método da secante. Se este também tiver como resultado um ponto
fora do intervalo, usa-se o método da bissecção, o qual também exerce um
controle sobre a velocidade real de convergência, se os métodos utilizados
convergirem muito lentamente.
Assim, o método de Van Wijngaarden-Dekker-Brent caracteriza-se por ser
bastante eficiente e de convergência garantida, a despeito de sua
complexidade, sendo recomendado para black-boxes.
4. Método de Ridders (Brent, 1973; Dekker , 1969)
Fundamenta-se nos métodos da Falsa Posição e da Secante, assim como no uso
de uma exponencial que é ajustada de um modo particular sobre os pontos
extremo e o intermédio do intervalo que contém a raiz.
A convergência é garantida, a velocidade de convergência pode ser muito
boa e o algoritmo é muito mais simples do que o algoritmo de Brent, sendo
quase tão confiável quanto este. (Vide Press et al. (1992) e JTEM (2008) para
maiores detalhes de implementação em C e Java, respectivamente)
5. Métodos de Bus e Dekker (Bus & Dekker (1975))
Bus & Dekker (1975) partiram do algoritmo originalmente concebido por Dekker
(1969), produzindo uma combinação dos métodos de Interpolação linear,
Interpolação racional e Bissecção. É também um método muito eficiente e de
convergência garantida, recomendado para black-boxes. (Vide Bus & Dekker
(1975) na página de Bibliografia da disciplina)
6. Método de Le (Le (1985))
O método de Le para a determinação de uma raiz de funções reais combina o
método da Bissecção com métodos de segunda e terceira ordens, usando
derivadas estimadas de valores de funções objetivas.
A convergência global é garantida e o número de testes da função é
limitado a 4 vezes o número necessário pelo método da Bissecção. Le (1985)
demonstrou com comparações numéricas entre os métodos de Newton-Raphson
e da Secante que o seu algoritmo é superior em todas as classes de problemas.
(Vide Le (1985) na página de Bibliografia da disciplina)
7. Método da Média Áurea (Le (1985))
O cálculo da derivada pode ser indesejável, de modo que outros métodos para a
determinação explícita de extremos, semelhantes aos anteriores, têm sido
concebidos. Um dos processos consiste em determinar o mínimo da única
parábola que passa nos pontos dados (a, b e c) e utilizar tal ponto como a
aproximação (x) da raiz.
O método mais simples é o da Média Áurea, equivalente ao método da
Bissecção que, tal como este, tem convergência garantida a ritmo constante.
Define-se um intervalo que contém um mínimo a partir de 3 pontos ( a, b e c),
de modo que a<b<c => f(a)>f(b)<f(c). Seccionando-se o intervalo num ponto
x qualquer e escolhendo-se o conjunto de 3 pontos consecutivos (dentre a, b, x
e c) que ainda contém um mínimo, repete-se o processo até se obter a precisão
desejada.
Com fins à otimização da velocidade de convergência, o ponto de corte
deve ficar no subintervalo maior – max([a,b], [b,c]) - e ser a média áurea desse
sub-intervalo no sentido do centro, i.e., se [a,b] for o maior sub-intervalo, x é
tal que o quociente do comprimento xb pelo comprimento ax vale 0,38197... .
Referências Bibliográficas
Brent, R.P ., Algorithms for Minimization without Derivatives, Chapter 4. Prentice-Hall,
Englewood Cliffs, NJ. ISBN 0-13-022335-2. 1973.
Bus, J. C. P ., & Dekker , T . J., Two Efficient Algorithms with Guaranteed Convergence for
Finding a Zero of a Function, ACM Transactions of Mathematical Software, 1(4):330345, 1975.
Dekker , T . J., Finding a zero by means of successive linear interpolation. In: B. Dejon
and P . Henrici (Eds.), Constructive Aspects of the Fundamental Theorem of Algebra,
London: Wiley-Interscience, 1969.
JTEM - Java T ools for Experimental Mathematics, numericalMethods. Documento
eletrônico.
Disponível
em
http://www-sfb288.math.tuberlin.de/~jtem/numericalMethods/. Última data de acesso: 23 de Junho de 2008.
Le, D., An efficient derivative-free method for solving nonlinear equations, ACM
Transactions on Mathematical Software (TOMS), 11(3):250-262, September 1985.
Muller , D. E., A Method for Solving Algebraic Equations Using an Automatic Computer ,
MTAC, 10 (1956), pp. 208-215.
Press, W . H., T eukolsky, S. A., Vetterling, W . T ., & Flannery, B.P Numerical
.,
Recipes in
C: The Art of Scientific Computing. Cambridge UK: Cambridge University Press, pp.
358–359. 2nd ed., 1992.
Ridders, C. J. F ., Three-point iterations derived from exponential curve fitting, IEEE
Transactions on Circuits and Systems, 26(8): 669−670, 1979.
Weisstein, E. W ., Muller's Method. Documento eletrônico. Disponível em
http://mathworld.wolfram.com/MullersMethod.htm l. Última data de acesso: 23 de Junho
de 2008.