Apostila desenho mecanico 2 raizes3(metodo de dekker)

Prévia do material em texto

Zeros de Func¸o˜es – Parte 3
Jorge C. Lucero
16 de Marc¸o de 2009
1 Me´todo de Dekker
Uma forma eficiente de calcular zeros de func¸o˜es e´ combinar algoritmos. O algoritmo de
Dekker [Dek69], que utiliza o me´todo de Secante a menos que a Bissecc¸a˜o parec¸a mais con-
veniente.
Seja uma func¸a˜o cont´ınua f(x), e duas aproximac¸o˜es iniciais a0 e b0 tais que f(a0) e f(b0)
tenham sinais contra´rios. Essas condic¸o˜es garantem a existeˆncia de um zero ξ entre a0 e b0. O
algoritmo gera duas sequeˆncias de aproximac¸o˜es ak e bk, tais que f(ak) e f(bk) tenham sinais
contra´rios; dessa forma, o zero ξ estara´ sempre entre ak e bk. Ale´m disso, em cada iterac¸a˜o
verifica se |f(bk)| ≤ |f(ak)|, e intercambia ak e bk caso a desigualdade na˜o seja verdadeira.
Dessa forma, bk sera´ sempre (provavelmente) uma aproximac¸a˜o a ξ melhor que ak.
Em cada iterac¸a˜o, duas aproximac¸o˜es sa˜o calculadas: q, utilizando o me´todo da secante a
partir das aproximac¸o˜es bk e bk−1
q = bk − bk bk − bk−1
f(bk)− f(bk−1)
e m, usando a bissecc¸a˜o
m =
ak + bk
2
.
Na iterac¸a˜o inicial (k = 0), o ca´lculo de q e´ realizado tomando bk−1 = a0.
Sempre que poss´ıvel, gostar´ıamos de utilizar a Secante em vez da Bissecc¸a˜o, pois sabemos
que aquele e´ mais ra´pida. Entretanto, as aproximac¸o˜es calculadas pela fo´rmula da secante
podem na˜o ser convergentes. Para garantir a convergeˆncia, poder´ıamos enta˜o exigir que
q esteja entre ak e bk (ja´ que sabemos que o zero ξ esta´ nesse intervalo). No entanto, o
algoritmo supo˜e que ξ esta´ mais pro´ximo de bk que de ak, pois |f(bk)| ≤ |f(ak)|. Assim,
exigimos que q esteja entre bk e m (ponto me´dio do intervalo). Se isso acontece, tomamos
bk+1 = q como nova aproximac¸a˜o, e caso contrario, fazemos bk+1 = m.
Logo, ak+1 e´ escolhido de forma de que f(ak+1) tenha sinal contra´rio ao de f(bk+1). Se
o sinal de f(ak) e´ contra´rio ao de f(bk+1), enta˜o fazemos ak+1 = ak; caso contra´rio, f(bk) e
f(bk+1) devem ter sinais contra´rios, e enta˜o fazemos ak+1 = bk.
As iterac¸o˜es param quando |bk − ak|/2 < ε, e tomamos x∗ = bk como aproximac¸a˜o final a
ξ. A condic¸a˜o de parada garante que o erro sera´ |ξ − x∗| < ε.
Algoritmo 1 (Me´todo de Dekker). Dada uma func¸a˜o f(x) cont´ınua em um intervalo [a0,b0],
com f(a0)) e f(b0) de sinais opostos, este algoritmo calcula uma aproximac¸a˜o x∗ a um zero
de f(x) em [a0,b0], com erro menor que ε.
k = 0
if |f(a0)| ≤ |f(b0)|
swap a0, b0
1
x
y
a0b0 ξ
mq
y = f(x)
b1 a1q m
b2a2
Figura 1: Me´todo de Dekker
end
b−1 = a0
while |bk − ak|/2 > ε
s =
f(bk)− f(bk−1)
bk − bk−1
q = bk − f(bk)/s
m = (ak + bk)/2
if q esta´ entre bk e m
bk+1 = q
else
bk+1 = m
end
if f(ak) · f(bk+1 < 0
ak+1 = ak
else
ak+1 = bk
end
if |f(ak+1)| ≤ |f(bk+1)|
swap ak+1, bk+1
end
end
x∗ = bk+1
�
2
Exemplo 1. Calculemos uma aproximac¸a˜o ao zero de f(x) = 4xe−x − 1 no intervalo [0, 1],
com erro menor que ε = 0,0005. Tomando a0 = 0 e b0 = 1, o algoritmo acima produz
k ak bk f(ak) f(bk) q m |bk − ak|
0 0 1 -1 0,4715 0,6796 0,5 1
1 0 0,6796 -1 0,3777 -0,6108 0,3398 0,6796
2 0,6796 0,3398 0,3777 -0,0324 0,3666 0,5097 0,3398
3 0,3398 0,3666 -0,0324 0,0164 0,3576 0,3532 0,0268
4 0,3398 0,3576 -0,0324 3,7094 × 10−4 0,3574 0,3487 0,0178
5 0,3576 0,3574 3,7094 × 10−4 −4,4044 × 10−6 0,0002
e retorna x∗ = 0,3574 como aproximac¸a˜o final. �
O algoritmo de Dekker combina a velocidade do me´todo da secante com a garantia de
convergeˆncia do me´todo da bissecc¸a˜o. Para func¸o˜es razoavelmente bem comportadas, e´ um
algoritmo eficiente. Entretanto, existem casos particulares em que a convergeˆncia pode ser
muito lenta, ainda mais que no me´todo da Bissecc¸a˜o [Bre02]. Uma versa˜o aprimorada do
algoritmo, devida a Richard P. Brent, inclui testes de convergeˆncia adicionais para resolver
tais casos. Tambe´m, incorpora o uso de interpolac¸a˜o quadra´tica inversa (esta te´cnica sera´
vista mais adiante), o que incrementa sua eficieˆncia. Este me´todo de Dekker-Brent constitui
a base de programas computacionais modernos para o ca´lculo de zeros de func¸o˜es, em software
como Matlab e Octave.
Refereˆncias
[Bre02] Richard P. Brent. Algorithms for Minimization without Derivatives. Courier Dover Publica-
tions, 2002.
[Dek69] T. J. Dekker. Constructive Aspects of the Fundamental Theorem of Algebra, cap´ıtulo Finding
a zero by means of successive linear interpolation. Wiley-Interscience, 1969.
3
	Método de Dekker