Apostila desenho mecanico 2 raizes2(metodo de newton raphson

Prévia do material em texto

Zeros de Func¸o˜es – Parte 2
Jorge C. Lucero
16 de Marc¸o de 2009
1 Me´todo de Newton-Raphson
Seja o ca´lculo de um zero ξ de uma func¸a˜o f(x), cont´ınua em um intervalo que conte´m a ξ.
Este me´todo esta´ baseado em aproximar a func¸a˜o f(x) por uma reta tangente, como mostra
o seguinte gra´fico
x
y
x0
(x0,f(x0))
x1
(x1,f(x1))
y = f(x)
x2ξ
Figura 1: Me´todo de Newton-Raphson
Seja x0 uma aproximac¸a˜o inicial ao zero ξ. A reta tangente a` curva y = f(x) no ponto
(x0, f(x0)) tem coeficiente angular f ′(x0), e sua equac¸a˜o e´
y − f(x0) = f ′(x0)(x− x0) (1)
O valor de x = x1 onde reta corta o eixo x pode ser determinado fazendo y = 0 a equac¸a˜o
acima, obtendo
0− f(x0) = f ′(x0)(x1 − x0)
e isolando x1
x1 = x0 − f(x0)
f ′(x0)
O valor de x1 passa a ser uma nova aproximac¸a˜o a ξ, a partir da qual calculamos novas
aproximac¸o˜es, repetindo o processo descrito. Apo´s k iterac¸o˜es, teremos
xk+1 = xk − f(xk)
f ′(xk)
1
que e´ a fo´rmula iterativa de Newton-Raphson.
Paramos as iterac¸o˜es quando a diferenc¸a entre aproximac¸o˜es consecutivas e´ suficientemente
pequena, e tomamos como aproximac¸a˜o final o valor da u´ltima aproximac¸a˜o calculada. Se ε e´
um valor de toleraˆncia dado (normalmente um nu´mero pequeno), enta˜o o crite´rio de parada
esta´ dado pela condic¸a˜o |xk − xk−1| < ε.
Algoritmo 1 (Me´todo de Newton-Raphson). Dada uma func¸a˜o f(x) e uma aproximac¸a˜o
inicial x0 a um zero ξ de f(x), este algoritmo calcula uma aproximac¸a˜o x∗ ao zero com erro
menor que ε. Caso as aproximac¸o˜es na˜o convirjam, o algoritmo para ao atingir Imax iterac¸o˜es.
k = 0
Error = ε+ 1
while Error > ε
k = k + 1
if k > Imax
Mostre a mensagem “O algoritmo na˜o converge apo´s Imax iterac¸o˜es”
end
xk+1 = xk − f(xk)/f ′(xk)
Error = |xk+1 − xk|
end
x∗ = xk+1
�
Exemplo 1. Consideremos o ca´lculo de
√
A, onde A e´ qualquer nu´mero positivo. Este
problema pode ser expressado como o ca´lculo do zero positivo da func¸a˜o f(x) = x2 − A.
Sendo f ′(x) = 2x, a fo´rmula de Newton Raphson e´
xk+1 = xk − x
2
k −A
2xk
=
xk
2
+
A
2xk
=
1
2
(
xk +
A
xk
)
Curiosamente, esta e´ a mesma fo´rmula iterativa do conhecido me´todo babiloˆnico. Por
exemplo, com A = 19 e x0 = 4, obtemos
k xk
0 5
1 4,4
2 4,359090909
3 4,358898948
4 4,358898944
5 4,358898944
Note a velocidade de convergeˆncia do algoritmo: em apenas 4 iterac¸o˜es obtemos
√
19 =
4,35889844 com erro menor que 10−9. Como comparac¸a˜o, podemos calcular a quantidade de
2
iterac¸o˜es que seriam necessa´rias para fazer o ca´lculo pelo me´todo da Bissecc¸a˜o, com a mesma
precisa˜o. Usando a fo´rmula ja´ vista, e considerando [4, 5] como intervalo inicial, obtemos
k >
log(5− 4)− log(10−9)
log 2
= 28,89
Seriam necessa´rias, enta˜o, pelo menos 29 iterac¸o˜es. �
Uma desvantagem do me´todo, que na˜o existe no me´todo da Bissecc¸a˜o, e´ a possibilidade de
na˜o convergeˆncia das iterac¸o˜es. Por exemplo, se em algum momento obtivermos f ′(xk) = 0,
deveremos parar o ca´lculo, e tentar uma nova aproximac¸a˜o inicial. Tambe´m, um valor de
f ′(xk) muito pequeno pode produzir um valor de xk+1 muito grande e longe do intervalo no
qual estamos trabalhando.
E´ poss´ıvel demonstrar que as aproximac¸o˜es ira˜o convergir ao zero ξ de f(x) se a aproxi-
mac¸a˜o inicial x0 estiver “suficientemente pro´xima”de ξ. No entanto, geralmente na˜o sabemos,
a priori, se a aproximac¸a˜o inicial escolhida satisfaz essa condic¸a˜o. Caso as aproximac¸o˜es na˜o
convirjam, podemos tentar uma nova aproximac¸a˜o inicial, ou mudar para o algoritmo da
bissecc¸a˜o, por exemplo, que tem convergeˆncia garantida.
O seguinte e´ um exemplo “perverso” [Mol04].
Exemplo 2. A seguinte func¸a˜o possui um zero em x = 2
f(x) =
{ √
x− 2, se x ≥ 2,
−√2− x, se x < 2.
Sua derivada e´
f ′(x) =
⎧⎪⎨
⎪⎩
1
2
√
x− 2 , se x ≥ 2,
1
2
√
2− x, se x < 2.
Tomando, por exemplo, x0 = 2,7, obtemos f(x0) = 0,83666, f ′(x0) = 0,59761, e logo
x1 = 1,3. Repetindo, a partir de x1, obtemos f(x1) = −0,83666, f ′(x1) = 0,59761, e x2 = 2,7,
voltando ao ponto inicial. De fato, e´ simples mostrar que para qualquer aproximac¸a˜o inicial
teremos sempre x2 = x0.
�
Analisemos agora a velocidade de convergeˆncia do me´todo. Para isso, precisamos lembrar
da fo´rmula de Taylor: a expansa˜o em se´rie de poteˆncias de uma func¸a˜o f(x) em torno a um
ponto x0 e´
f(x) = f(x0) + f ′(x0)(x− x0) + f
′′(x0)
2!
(x− x0)2 + · · ·+ f
(n)(x0)
n!
(x− x0)n + · · ·
(supomos que todas as derivadas de f(x) existem, e que a se´rie e´ convergente em alguma
vizinhanc¸a de x0). A fo´rmula acima diz que f(x) e´ igual a` soma da se´rie. Se truncamos a
se´rie no n-e´ssimo termo, obteremos um polinoˆmio de Taylor de grau n
pn(x) = f(x0) + f ′(x0)(x− x0) + f
′′(x0)
2!
(x− x0)2 + · · ·+ f
(n)(x0)
n!
(x− x0)n
Neste caso, f(x) �= pn(x), pois estamos desprezando todos os termos apo´s o n-e´ssimo. Pode-
mos considerar que pn(x) e´ uma aproximac¸a˜o a f(x), com erro Rn(x) = f(x)−pn(x) (chamado
3
1
−1
−2
1 2 3
x
y
y = f(x)
(x0,f(x0))
(x1,f(x1))
x0 = x2x1
Figura 2: Exemplo 2
de erro de truncamento ou resto). Segundo o Teorema de Taylor, existe um nu´mero ζ entre
x e x0 tal que
Rn(x) =
f (n+1)(ζ)
(n + 1)!
(x− x0)n+1
Se agora fazemos n = 1, obtemos
p1(x) = f(x0) + f ′(x0)(x− x0) (2)
e o resto e´
R1(x) =
f ′′(ζ)
2
(x− x0)2
Comparando as Eqs. (1) e (2), percebemos que y = p1(x) e´ a equac¸a˜o da reta tangente
utilizada pelo me´todo de Newton-Raphson, e enta˜o R1(x) e´ o erro cometido ao substituir a
curva y = f(x) pela reta y = p1(x).
Fac¸amos x = ξ (zero de f(x)), e f(x) = f(ξ) = 0. Substituindo em R1(x) = f(x)− pn(x),
obtemos
f ′′(ζ)
2
(ξ − x0)2 = −f(x0)− f ′(x0)(ξ − x0)
Dividindo por f ′(x0) (supondo f ′(x0) �= 0),
f ′′(ζ)
2f ′(x0)
(ξ − x0)2 = − f(x0)
f ′(x0)
− ξ + x0
4
No lado direito, podemos substituir x0 − f(x0)f ′(x0) = x1, e enta˜o
f ′′(ζ)
2f ′(x0)
(ξ − x0)2 = x1 − ξ
Tomando valor absoluto, e generalizando para k iterac¸o˜es,
|ξ − xk+1| = |f
′′(ζ)|
2|f ′(xk)| |ξ − xk|
2
onde ζ esta´ entre ξ e xk.
Se as aproximac¸o˜es xk convergem ao zero ξ, enta˜o, para k suficientemente grande, f ′(xk) ≈
f ′(ξ) e f ′′(ζ) ≈ f ′′(ξ). Podemos escrever (supondo f ′(ξ) �= 0)
|ξ − xk+1| ≈ |f
′′(ξ)|
2|f ′(ξ)| |ξ − xk|
2 = C|ξ − xk|2
onde C ≥ 0 e´ uma constante. Em geral, C > 0, e a equac¸a˜o acima diz que o erro |ξ −
xk+1| em cada iterac¸a˜o e´ aproximadamente proporcional ao quadrado do erro |ξ − xk| na
iterac¸a˜o anterior. Tal caracter´ıstica e´ denominada convergeˆncia quadra´tica. Por exemplo,
suponhamos C = 1 e um erro inicial |ξ − x0| = 0,1. Nas iterac¸o˜es seguintes, o erro sera´
10−2, 10−4, 10−8, 10−16, 10−32, . . ., o que indica que a quantidade de d´ıgitos corretos duplica
em cada iterac¸a˜o.
Exemplo 3. O polinoˆmio p3(x) = x3 − 2x− 5 foi utilizado por John Wallis ao apresentar o
me´todo de Newton a` Academia de Cieˆncias Francesa. Possui um par de ra´ızes complexas, e
uma raiz real entre 2 e 3. A seguinte tabela mostra resultados da aplicac¸a˜o do me´todo com
x0 = 2,5. Vemos que os d´ıgitos corretos das aproximac¸o˜es (sublinhados) aproximadamente
duplicam a cada iterac¸a˜o.
k xk d´ıgitos corretos
0 2,500000000000000 1
1 2,164179104477612 1
2 2,097135355810555 3
3 2,094555232390448 6
4 2,094551481550247 11
5 2,094551481542327 > 16
6 2,094551481542327
�
As concluso˜es acima exigem f ′′(ξ) �= 0, f ′(ξ) �= 0, a continuidade de f(x) e suas derivadas
no intervalo de trabalho, e uma boa aproximac¸a˜o inicial que produza convergeˆncia. Se alguma
dessas condic¸o˜es falha, as aproximac¸o˜es podera˜o na˜o convergir, ou convergir de maneira na˜o
quadra´tica. Em particular, e´ poss´ıvel mostrar que, quando f ′(ξ) = 0 (i.e., quando ξ e´ um zero
de f(x) e tambe´m um ponto cr´ıtico),as aproximac¸o˜es podera˜o convergir, mas a convergeˆncia
sera´ linear
Exemplo 4. A func¸a˜o f(x) = (x− 1) ln x tem um zero e um um mı´nimo local em x = 1. A
aplicac¸a˜o do algoritmo de Newton-Raphson com x0 = 2 produz
5
1
1 2 x
y
y = (x− 1) ln x
Figura 3: exemplo 1.13
k xk d´ıgitos corretos
0 2.000000000000000 0
1 1.419059784196405 1
2 1.191773181862321 1
3 1.091745000606795 2
4 1.044873379776890 2
5 1.022191381700575 2
6 1.011034918720469 2
7 1.005502335432813 3
8 1.002747395356304 3
9 1.001372755664817 3
10 1.000686142463597 4
11 1.000343012406407 4
12 1.000171491498957 4
13 1.000085742073679 5
14 1.000042870117923 5
15 1.000021434829236 5
Neste caso, a quantidade de d´ıgitos corretos aumenta linearmente, e verificamos que existe
uma relac¸a˜o linear |1− xk+1|/|1 − xk| ≈ 0,5. �
Me´todo da Secante
Este me´todo e´ uma variac¸a˜o do me´todo de Newton-Raphson, para casos em que a derivada
f ′(x) na˜o esta´ dispon´ıvel (e.g., quando o ca´lculo de f ′(x) na˜o e´ poss´ıvel ou e´ muito complicado).
No lugar da derivada, o me´todo da secante utiliza uma aproximac¸a˜o da mesma calculada a
partir das duas u´ltima aproximac¸o˜es. A fo´rmula do me´todo pode ser escrita na forma
xk+1 = xk − xk
sk
6
onde
sk =
f(xk)− f(xk−1)
xk − xk−1
Note que, se xk1 → xk a fo´rmula acima produz sk = f ′(xk).
x
y
x0
(x0,f(x0))
x1
(x1,f(x1))
y = f(x)
x2
(x2,f(x2))
x3ξ
Figura 4: Me´todo da Secante
Como ilustra a Fig. 3, partimos de duas aproximac¸o˜es iniciais x0 e x1. Trazemos uma reta
tangente a` curva y = f(x) pelos pontos (x0, f(x0)) e (x1, f(x1)), e chamemos de x2 ao valor
de x onde a reta intersecta o eixo x. O coeficiente angular m dessa reta e´
m =
f(x0)− f(x1)
x0 − x1
=
f(x1)− f(x0)
x1 − x0
e a equac¸a˜o da reta e´
y − f(x1) = m(x− x1) (3)
Procedendo em forma similar ao me´todo de Newton-Raphson, determinamos o valor de x = x2
onde reta corta o eixo x fazendo y = 0 a equac¸a˜o acima, de onde obtemos
x2 = x1 − f(x1)
m
que concorda com a fo´rmula geral do me´todo vista acima. Numa nova iterac¸a˜o, trac¸amos
uma nova secante por (x1, f(x1)) e (x2, f(x2)), obtendo uma nova aproximac¸a˜o x3 no ponto
de intersec¸a˜o com o eixo x, e o me´todo continua repetindo este processo.
Algoritmo 2 (Me´todo da Secante). Dada uma func¸a˜o f(x) e duas aproximac¸o˜es iniciais, x0
e x1, a um zero ξ de f(x), este algoritmo calcula uma aproximac¸a˜o x∗ ao zero com erro menor
que ε. Caso as aproximac¸o˜es na˜o convirjam, o algoritmo para ao atingir Imax iterac¸o˜es.
7
k = 0
Error = |x1 − x0|
while Error > ε
k = k + 1
if k > Imax
Mostre a mensagem “O algoritmo na˜o converge apo´s Imax iterac¸o˜es”
end
sk =
f(xk)− f(xk−1)
xk − xk−1
xk+1 = xk − f(xk)/sk
Error = |xk+1 − xk|
end
x∗ = xk+1
�
Exemplo 5. Consideremos novamente o ca´lculo de
√
A, com onde A = 19. Como vimos, o
problema e´ resolvido calculando o zero positivo da func¸a˜o f(x) = x2 −A. Tomando x0 = 4 e
x1 = 5, obtemos
k xk
0 4
1 5
2 4,333333333
3 4,357142857
4 4,358904110
5 4,358898942
6 4,358898944
7 4,358898944
�
Como ilustra o exemplo, este me´todo e´ um pouco mais lento que o Newton-Raphson (i.e.,
exige uma maior quantidade de iterac¸o˜es para atingir a mesma precisa˜o). De fato, e´ poss´ıvel
demonstrar que a convergeˆncia ja´ na˜o e´ mais quadra´tica, e o erro em cada iterac¸a˜o segue uma
lei da forma
|ξ − xk+1| ≈ C|ξ − xk|φ
onde, curiosamente, φ e´ o nu´mero a´ureo (1 +
√
5)/2 = 1,618 . . ..
Igualmente ao me´todo Newton-Raphson, o me´todo da secante pode apresentar problemas
de convergeˆncia. Por exemplo, se f(xk) = f(xk−1 teremos uma divisa˜o por zero no ca´lculo de
sk. Ainda, se f(xk) ≈ f(xk−1, poderemos obter um valor de xk+1 muito grande e longe do
intervalo no qual estamos trabalhando.
Refereˆncias
[Mol04] Cleve Moler. Numerical Computing with MATLAB. The Mathworks, online em
http://www.mathworks.com/academia/ (u´ltimo accesso em 27/05/2007), 2004.
8
	Método de Newton-Raphson