ANÁLISE NUMÉRICA DO MÉTODO DE NEWTON PARA OBTENÇÃO
DE ZEROS DE FUNÇÕES.
Edevilson Gomes Pereira –PUCPR- [email protected]
Viviana Cocco Mariani – PUCPR- [email protected]
Resumo: Neste artigo é feita uma análise da modificação do método de
Newton-Raphson, utilizado na obtenção de raízes de equações ou zeros de
funções, surgindo o método de Newton Quadrático, Newton Quadrático 2 e
Newton Melhorado. A extensão do método de Newton para os outros três
métodos é descrita e a comparação do número de iterações, tempo de
processamento e número de ponto flutuante entre os métodos utilizados é
apresentada para algumas funções algébricas e transcendentes mostrando que
os métodos de Newton Melhorado e Newton Quadrático tiveram
comportamento superior, a respeito do número de iterações, em quase todos
os casos analisados, quando comparados com o método de Newton-Raphson.
Palavras-chave: Newton-Raphson, zeros de funções, métodos numéricos.
1. INTRODUÇÃO
Visto a importância de se obter à raiz de equações (ou zero de
funções), nas mais diversas situações da atividade humana, observa-se à
necessidade de se encontrar métodos computacionais que facilitem e agilizem
este processo com exatidão, confiabilidade e esforço computacional menor.
Todos estes fatores dependem do comportamento da função próximo as suas
raízes. A pesquisa desenvolvida tem por objetivo evidenciar novos processos
para este fim, bem como apontar a eficácia dos métodos, suas falhas e suas
condições (restrições) para convergência e a descrição de tabelas de
desempenho dos mesmos.
A partir do método de Newton Raphson, obtém-se outros métodos
iterativos, esta pesquisa, em especial, investigará o método de Newton
melhorado, o método de Newton quadrático e o método de Newton quadrático
2. O método de Newton Raphson, conhecido também como método das
tangentes, provém da expansão em série de Taylor, pois utiliza os dois
primeiros termos desta série. Visto que, a série de Taylor utiliza em as
derivadas da função, a convergência dependerá da função na região em torno
da raiz (Ruggiero e Lopes, 1996).
O método de Newton quadrático, como o próprio nome diz, é obtido
por uma equação do segundo grau, proveniente dos três primeiros termos da
2
série de Taylor. Sabe-se que para resolver uma equação do segundo grau, a
fórmula de Bhaskara ou Baskara pode ser utilizada, no qual aparece o cálculo
da raiz quadrada de um número. Nos resultados coletados no presente
trabalho utilizando o método de Newton quadrático notou-se que em alguns
casos testados durante o processo iterativo o radicando era negativo, mesmo
assim o método continuava iterando resultando em um valor x k +1 = a + bi , onde
b a parte imaginária do número era um número infinitesimal. Neste caso
observamos que desprezando a parte imaginária infinitesimal a parte real era a
raiz da equação. O método de Newton quadrático convergia nestes casos
apenas se a parte imaginária era extremamente pequena, caso contrário o
método divergia. Percebe-se, nas funções analisadas no presente trabalho,
que uma das condições necessárias para a convergência deste método, é que
a derivada segunda da função em cada ponto analisado x k , seja diferente de
zero.
O método de Newton melhorado é obtido pela combinação do método
de
Newton-Raphson
e
Newton
quadrático,
executa-se
três
cálculos
consecutivos a cada iteração, no primeiro cálculo a aproximação para a raiz é
obtida utilizando o método de Newton-Raphson, e em seguida duas avaliações
usando o método de Newton Quadrático são executadas, surgindo assim o
método de Newton melhorado. Em geral, este método, leva o mesmo número
de iterações que o método de Newton quadrático para convergir. Na maioria
dos casos analisados, este número é menor ou igual ao número de iterações
do método de Newton Raphson, e menor que o método de Newton quadrático
2. O número de operações em ponto flutuante, é em sua maioria, maior que a
do método de Newton Raphson. Observa-se ainda, que o referido método não
falha em todas as funções analisadas, convergindo para a mesma raiz que o
método de Newton-Raphson e o método de Newton quadrático 2, quando estes
convergem.
O método de Newton quadrático 2, é obtido utilizando-se os mesmos
termos utilizados pelo método de Newton quadrático, mas resolvido isolando-se
o fator comum aos dois últimos termos (xk+1 - xk).
3
Na simulação numérica adotou-se o critério de convergência ε ≤ 10-6.
Alguns problemas aplicados a processos químicos foram testados e os
resultados são apresentados a seguir.
2. FUNDAMENTOS MATEMÁTICOS
O método de Newton-Raphson é baseado na expansão em série de
Taylor, isto é, expandindo a série de Taylor em torno de xk tem-se,
f(x) = f(xk) + f’(xk)(x –xk) + f’’(xk)
( x − x k )2
( x − x k )3
+ f´´´(xk)
+ ....,
2!
3!
(1)
onde xk é um valor aproximado para a raiz λ da equação na iteração k do
processo iterativo, f(x) é a função, f´(x) a derivada primeira da função e f´´(x) a
derivada segunda da função.
Seja xk+1 a raiz da equação f(x) = 0, logo a equação (1) resulta,
( x k +1 − x k )2
( x k +1 − x k )3
0 = f(xk) + f’(xk)(xk+1 –xk) + f’’(xk)
+ f´´´(xk)
+ ....
2!
3!
(2)
Usando os dois primeiros termos da expansão da série de Taylor, do
lado direito da equação (2), obtém-se o popular método de Newton-Raphson,
ou seja (Roque, 2000),
xk+1 = xk -
f(xk )
f´( x k )
(3)
As desvantagens do método de Newton-Raphson surgem quando a
inclinação da função tem um valor próximo da raiz e/ou o seu valor é muito
pequeno. Este valor para a inclinação da função faz com que na próxima
iteração o valor para xk+1 fique fora da vizinhança da raiz, λ, podendo divergir
(Barroso et al., 1987).
A derivada primeira da função pode ser obtida numericamente de uma
maneira rápida, basta para isto usar a aproximação,
4
f´(xk) =
f ( x k + h) − f ( x k − h )
,
2h
(4)
onde h é um incremento, com valor pequeno.
Assim, substituindo a equação (4) na equação (3) tem-se,
f´(xk) = x k −
2hf ( x k )
f ( x k + h) − f ( x k − h )
(5)
,
que requer a avaliação da função f(x) em três valores vizinhos e distintos, xk, xk
+ h e xk - h. Naturalmente pode-se estimar o valor da derivada segunda da
função como,
f´´(xk) =
f ( x k + h) − 2f ( x k ) + f ( x k − h)
.
h2
(6)
Nota-se na equação (6) que o cálculo da derivada de segunda ordem,
semelhante ao cálculo da derivada de primeira ordem, só precisa da avaliação
da função f(x) em três pontos distintos xk, xk + h e xk – h. Deste modo voltando
na equação (2) e utilizando os três primeiros termos da série de Taylor obtémse,
( x k +1 − x k )2
0 = f(xk) + f’(xk)(xk+1 – xk) + f’’(xk)
.
2!
(7)
A equação (7) é quadrática para o fator ( x k +1 − x k ) , resolvendo-a o
resultado será exposto na equação (8) e representa o método que será
denominado Newton quadrático,
x k +1
 − f´( x ) +
k
= xk + 


[f´( x k )]2 − 2f ( x k )f´´( x k ) 
f´´( x k )


.
(8)
5
Outra maneira de resolver a equação (7) é isolando o fator ( x k +1 − x k )
comum aos dois últimos termos da equação (7) produzindo a equação (9) que
é a fórmula do método de Newton Quadrático 2.
x k +1 = x k − [f ( x k ) /( f´( x k ) + f´´( x k )( x k +1 − x k ) / 2)]
(9)
Para utilizar a equação (9) emprega-se a equação (3) para avaliar uma
estimativa para xk+1 no lado direito da equação.
O método de Newton Melhorado executa três cálculos consecutivos a
cada iteração, no primeiro cálculo a aproximação para a raiz é feita utilizando o
método de Newton-Raphson, equação (3), e em seguida duas avaliações
usando o método de Newton quadrático são executadas, isto é, empregando a
equação (9), surgindo assim o método de Newton melhorado, conforme
apresentado na equação (10) (Shammas, 2002),
x1 = x0 -
f(x 0 )
f´( x 0 )
x 2 = x 0 − [f ( x 0 ) /( f´( x 0 ) + f´´( x 0 )( x 1 − x 0 ) / 2)]
(10)
x 3 = x 0 − [f ( x 0 ) /( f´( x 0 ) + f´´( x 0 )( x 2 − x 0 ) / 2)]
3. RESULTADOS NUMÉRICOS
Algumas funções e problemas foram testados para comparar os
métodos de Newton e os resultados são apresentados nas tabelas que
seguem.
A capacidade calorífica (Cp) do O2 na faixa de temperatura entre 298 a
1500 K apresenta a seguinte equação, em função da temperatura: Cp(T) = 7,16
+ 1.10-3 T – (0,4.105)/T², onde: T está expressa em K e Cp em cal/mol°C. A
temperatura (K) em que a capacidade calorífica do O2 é de 8,15 cal/mol °C
resulta na função f(T) = - 0,99+10-3T – 0,4 105/T2, e o zero da função obtido
através dos métodos numéricos analisados no presente trabalho é apresentado
na tabela 1. A sigla NPF, nas tabelas, indica o número de operações em ponto
flutuante, a precisão adotada em todas as simulações foi 10 −6 .
6
Tabela 1 – Solução numérica para uma raiz de f(T) = - 0,99+10-3T – 0,4 105/T2.
Métodos
T0
Raiz
Iterações Tempo NPF
Newton
500
1027,8609
4
0,078 182
Newton Melhorado
500
1027,8609
5
0,078 302
Newton Quadrático
500
1027,8609
4
0.016 250
Newton Quadrático 2
500 e 500,1
1027,8609
7
0,094 250
Newton
2000
1027,8609
4
0,094 182
Newton Melhorado
2000
1027,8609
3
0,110 214
Newton Quadrático
2000
1027,8609
3
0,125 196
Newton Quadrático 2 2000 e 2000,1 1027,8609
6
0,109 228
Newton
1000
1027,8609
3
0,109 154
Newton Melhorado
1000
1027,8609
3
0,140 214
Newton Quadrático
1000
1027,8609
3
0,108 196
Newton Quadrático 2 1000 e 1000,1 1027,8609
5
0,124 206
A raiz aproximada é 1027,860929749276.
Nota-se na tabela 1 que os métodos de Newton Melhorado e Newton
Quadrático para o valor inicial 2000 convergiram com menor número de
iterações quando comparados com o método de Newton-Raphson, contudo o
tempo de processamento e o número de operações em ponto flutuante é maior
nestes métodos. A figura 1 ilustra o comportamento da função f(T) = - 0,99+103
T – 0.4 105/T2 e das retas tangentes nos pontos (xi, f(xi)) durante o processo
iterativo do método de Newton.
Figura 1 – Ilustração da convergência da função f(T) com T0 = 1000.
7
O metano apresenta a seguinte equação do calor específico em função
da temperatura, na faixa entre 298 e 1500 K, Cp(T) = 3,381 + 18,044.10-³T4,3.10-6T², onde T está em K e Cp em cal/mol°C. A temperatura (K) para a qual
a capacidade calorífica do CH4 vale 15,0 cal/mol °C, resulta na seguinte
equação f(T) = 18,044 10-3 T – 4,3 10-6 T2 - 11,619.
Tabela 2 – Solução numérica para as raízes de f(T) = 18,044 10-3 T –
4,3 10-6 T2 – 11,619.
Métodos
Valor inicial
Raiz
Iterações Tempo
NPF
Newton
500
794,2621
4
0,156
182
Newton Melhorado
500
794,2621
3
0,187
204
Newton Quadrático
500
794,2621
3
0,203
152
Newton Quadrático 2
500 e 1000 794,2621
6
0,219
216
Newton
2098
794,2621
18
0,047
574
Newton Melhorado
2098
794,2621
9
0,047
454
Newton Quadrático
2098
794,2621
9
0,047
128
Newton Quadrático 2 1598 e 2417 794,2621
25
0,297
596
Newton
2099
3402,017
15
0,281
490
Newton Melhorado
2099
3402,017
8
0,297
404
Newton Quadrático
2099
794,2621
8
0,328
128
Newton Quadrático 2 1598 e 2418 3402,017
23
0,250
556
Uma das raízes aproximadas é 794,2620542183545.
Na tabela 2 observa-se que os métodos de Newton Melhorado e
Quadrático convergem para a raiz da equação com menor número de
iterações, contudo o tempo de processamento ainda é menor com o método de
Newton-Raphson. Nesta tabela também verificamos que o método de Newton
Quadrático convergiu sempre para a mesma raiz, 794, embora a condição
inicial tenha sido modificada, isto é, para qualquer utilizado como aproximação
inicial, onde a derivada primeira da função não se anule o método de Newton
Quadrático converge para a raiz 794. A figura 2 ilustra o gráfico da função f(T)
= 18,044 10-3 T – 4,3 10-6 T2 – 11,619 com suas duas raízes reais e o
comportamento do método de Newton-Raphson durante o processo iterativo.
Na figura 3 é ilustrada uma ampliação do gráfico da figura 2.
8
Figura 2 – Ilustração da convergência da função f(T) para T0 = 2098.
Figura 3 – Ampliação da figura 2.
A tabela 3 mostra os resultados obtidos para a função f(x) = 100- x - x2/2
- x3/3 - x4/4 e o desempenho dos métodos a respeito do número de iterações,
tempo de processamento e número de ponto flutuante.
9
Para os dados apresentados na tabela 3 nota-se que para a
aproximação inicial 1, no método de Newton Quadrático 2, a função diverge, já
para a aproximação inicial 3, no método de Newton Quadrático, converge para
um número complexo cuja parte complexa do número citado é extremamente
pequena e a parte real é a raiz -4,772, raiz esta que os outros métodos não
convergiram para esta mesma aproximação inicial.
O método de Newton Melhorado foi o método que apresentou melhor
desempenho quanto ao número de iterações se comparado aos demais
métodos, porém o tempo de processamento e o número de operações em
ponto flutuante, que está relacionado ao número de iterações, não apresenta
uma constância, variando muito.
Tabela 3 - Solução numérica para uma raiz de f(x) = 100 - x - x2/2 - x3/3 - x4/4.
Métodos
Valor
Raiz
Iterações Tempo
NPF
inicial
Newton
1
4,031
12
0,063
475
Newton Melhorado
1
4,031
5
0,047
356
Newton Quadrático
1
-4,772
4
0,063
276
Newton Quadrático 2
1 e 1,1
-inf
Newton
3
4,031
5
0,109
237
Newton Melhorado
3
4,031
4
0,094
300
Newton Quadrático
3
-4,772
9
0,032
572
Newton Quadrático 2
3 e 3,1
4,031
7
0,109
292
Newton
5
4,031
5
0,125
237
Newton Melhorado
5
4,031
3
0,125
244
Newton Quadrático
5
-4,772
7
0,031
442
Newton Quadrático 2
5 e 5,1
4,031
7
0,125
292
Uma das raízes aproximadas é 4,03104780823003.
A figura 4 ilustra o processo iterativo do método de Newton-Raphson,
com suas retas tangentes, com o valor inicial x0 = 1.
10
Figura 4 - Ilustração da convergência da função f(x) para x0 = 1.
A tabela 4 mostra os resultados numéricos dos diversos métodos
utilizados para obter as raízes da função f(x) = x2 - 7xcos(x). Nesta tabela para
a aproximação inicial 5 o método de Newton Quadrático na segunda iteração
calcula a raiz quadrada de um número negativo, isto é, um número complexo
que a priori não é nenhuma das raízes da função estudada. Graficamente, na
figura 5, observa-se que a referida função, tem no mínimo 6 raízes reais.
Tabela 4 - Solução numérica para as raízes de f(x) = x2 - 7xcos(x).
Métodos
Valor inicial
Raiz
Iterações Tempo NPF
Newton
5
5,6522
4
0,172
189
Newton Melhorado
5
5,6522
4
0,188
300
Newton Quadrático
5
Newton Quadrático 2
5 e 5,1
5,6522
7
0,203
292
Newton
5,5
5,6522
4
0,219
189
Newton Melhorado
5,5
5,6522
3
0,219
244
Newton Quadrático
5,5
6,6160
3
0,219
276
Newton Quadrático 2
5,5 e 5,51
5,6522
6
0,219
265
Newton
6
5,6522
5
0,219
219
Newton Melhorado
6
5,6522
4
0,219
300
Newton Quadrático
6
6,6160
4
0,219
226
Newton Quadrático 2
6 e 6,1
5,6522
9
0,234
348
Uma das raízes aproximadas é 5,65222352013264.
11
Na tabela 4 para a aproximação inicial 5 o método de Newton
Quadrático na segunda iteração calcula a raiz quadrada de um número
negativo, isto é, um número complexo que a priori não é nenhuma das raízes
da função estudada.
Na figura 5, apresenta-se o processo de convergência do método de
Newton-Raphson, com as suas retas tangentes, para x0 = 6.
Figura 5 – Ilustração da convergência da função f(x) para x0 = 6.
4. CONCLUSÕES
Este artigo apresentou os resultados numéricos, para obter a raiz de
algumas funções matemáticas, utilizando os métodos de Newton-Raphson,
Newton Melhorado e Newton Quadrático e Newton Quadrático 2. Os métodos
de Newton Melhorado e Newton Quadrático apresentaram convergência mais
rápida, a respeito do número de iterações, que o método de Newton-Raphson
na maior parte dos casos avaliados, o que já havia sido observado por
Shammas (2002). Contudo, nota-se que estas vantagens podem ser alteradas
dependendo da função matemática avaliada, do valor inicial da raiz, da
curvatura da função próxima à raiz, etc.
12
O método de Newton Melhorado a cada iteração utiliza três avaliações
sucessivas para o cálculo da raiz, isto é, utiliza a avaliação do método de
Newton-Raphson e duas avaliações do método de Newton Quadrático, já o
método de Newton Quadrático é bastante instável, não convergindo em alguns
casos analisados, o método de Newton Quadrático 2 é altamente dependente
das estimativas iniciais para a raiz. Recomenda-se antes de adotar um método
para obter a raiz, que se faça o gráfico da função e analise como é a curvatura
da função próxima à raiz e a estimativa inicial da raiz.
5. REFERÊNCIAS
BARROSO, C. L., BARROSO, M. M., FILHO, C. F. F., CARVALHO, M. L. B.,
Cálculo Numérico - com Aplicações, São Paulo, Harbra, 2ª. edição, 1987.
ROQUE, W. L., Introdução ao Cálculo Numérico - Um Texto Integrado com
Derive, São Paulo, Atlas, 2000.
RUGGIERO, M. A. G., LOPES, V. L. R., Cálculo Numérico - Aspectos
Teóricos e Computacionais, Rio de Janeiro, Makron, 2ª. edição, 1996.
SHAMMAS, N. C., Enhancing Newton’s Method, Dr. Dobb’s Journal, p. 94 97, 2002.