04_ Método da bissecao

Prévia do material em texto

ufca
Me´todo da bissecc¸a˜o
O problema dos zeros de func¸a˜o
Estamos interessados em calcular uma soluc¸a˜o p (um zero ou
uma raiz) para a equac¸a˜o:
f(x) = 0
para uma func¸a˜o escalar real f dada,
ou ao menos uma aproximac¸a˜o adequada p˜ de p
Me´todo da bissecc¸a˜o
Teorema do Valor Intermedia´rio [TVI].
Sejam f cont´ınua em [a, b] e K ∈ (f(a), f(b)).
Enta˜o existe c ∈ (a, b) tal que f(c) = K
Me´todo da bissecc¸a˜o
Teorema do Valor Intermedia´rio [TVI].
Sejam f cont´ınua em [a, b] e K ∈ (f(a), f(b)).
Enta˜o existe c ∈ (a, b) tal que f(c) = K
Me´todo da bissecc¸a˜o
Teorema do Valor Intermedia´rio [TVI].
Sejam f cont´ınua em [a, b] e K ∈ (f(a), f(b)).
Enta˜o existe c ∈ (a, b) tal que f(c) = K
Se f e´ cont´ınua em [a, b] e f(a) · f(b) < 0
Enta˜o, pelo TVI, existe p ∈ (a, b) tal que f(p) = 0
Me´todo da bissecc¸a˜o
Dados f , a, b, fac¸a:
• Divida o intervalo [a, b] ao meio: p = (a+ b)/2
• Se f(p) possui o mesmo sinal que f(a), considere o
intervalo [p, b]
• Se f(p) possui o mesmo sinal que f(b), considere o
intervalo [a, p]
• Repita ate´ que o intervalo em considerac¸a˜o seja pequeno o
suficiente para aproximar a raiz de f com a precisa˜o
desejada
Me´todo da bissecc¸a˜o
Exemplo mestre
Determine as soluc¸o˜es da equac¸a˜o 6(ex − x) = 6 + 3x2 + 2x3
Crite´rio de parada
Suponha que o algoritmo gera uma sequeˆncia {pk} que
converge para a raiz p
Um crite´rio de parada independente da magnitude dos
elementos da sequeˆncia seria:
|pk+1 − pk|
|pk+1| < � ou k + 1 > nmax
Crite´rio de parada
Suponha que o algoritmo gera uma sequeˆncia {pk} que
converge para a raiz p
Um crite´rio de parada independente da magnitude dos
elementos da sequeˆncia seria:
|pk+1 − pk|
|pk+1| < � ou k + 1 > nmax
nu´mero
ma´ximo de
iterac¸o˜es
permitidas
erro
m´ınimo
exigido
Crite´rio de parada
Suponha que o algoritmo gera uma sequeˆncia {pk} que
converge para a raiz p
Um crite´rio de parada independente da magnitude dos
elementos da sequeˆncia seria:
|pk+1 − pk|
|pk+1| < � ou k + 1 > nmax
Se pk+1 estiver pro´ximo de zero ou for zero, teremos problema
Crite´rio de parada
Suponha que o algoritmo gera uma sequeˆncia {pk} que
converge para a raiz p
Um crite´rio de parada independente da magnitude dos
elementos da sequeˆncia seria:
|pk+1 − pk|
|pk+1| < � ou k + 1 > nmax
Se pk+1 estiver pro´ximo de zero ou for zero, teremos problema
Para contornar esta situac¸a˜o, usamos
|pk+1 − pk| < � ·max{1, |pk+1|} ou k + 1 > nmax
Retornando ao exemplo mestre
Determine as soluc¸o˜es da equac¸a˜o 6(ex − x) = 6 + 3x2 + 2x3
Ana´lise de convergeˆncia
Teorema. Suponha que f ∈ C[a, b] e f(a) · f(b) < 0.
O me´todo da bissecc¸a˜o gera uma sequeˆncia {pn} que se
aproxima de um zero p de f com
|pn − p| ≤ b− a
2n
, n ≥ 1
Ana´lise de convergeˆncia
Teorema. Suponha que f ∈ C[a, b] e f(a) · f(b) < 0.
O me´todo da bissecc¸a˜o gera uma sequeˆncia {pn} que se
aproxima de um zero p de f com
|pn − p| ≤ b− a
2n
, n ≥ 1
Demonstrac¸a˜o.
Para cada n ≥ 1, temos
bn − an = b− a
2n−1
e p ∈ (an, bn)
Ana´lise de convergeˆncia
Teorema. Suponha que f ∈ C[a, b] e f(a) · f(b) < 0.
O me´todo da bissecc¸a˜o gera uma sequeˆncia {pn} que se
aproxima de um zero p de f com
|pn − p| ≤ b− a
2n
, n ≥ 1
Demonstrac¸a˜o.
Para cada n ≥ 1, temos
bn − an = b− a
2n−1
e p ∈ (an, bn)
Como an < p e pn =
1
2 (an + bn), para n ≥ 1, segue que
|pn − p| ≤ |pn − an| ≤ 1
2
(bn − an) = b− a
2n
Nu´mero de iterac¸o˜es
Dada uma toleraˆncia �, podemos estimar tambe´m o nu´mero de
iterac¸o˜es, pois
|pn − p| ≤ b− a
2n
< �
Portanto,
2n >
(b− a)
�
log(2n) > log ((b− a)/�)
n log 2 > log ((b− a)/�)
n >
log ((b− a)/�)
log 2
n > log2
(
b− a
�
)
Nu´mero de iterac¸o˜es
Exemplo. Determine o nu´mero de iterac¸o˜es para resolver a
equac¸a˜o:
f(x) = x3 + 4x2 − 10 = 0,
com toleraˆncia de 10−3, usando o me´todo da bissecc¸a˜o com
intervalo inicial [1, 2]
Nu´mero de iterac¸o˜es
Exemplo. Determine o nu´mero de iterac¸o˜es para resolver a
equac¸a˜o:
f(x) = x3 + 4x2 − 10 = 0,
com toleraˆncia de 10−3, usando o me´todo da bissecc¸a˜o com
intervalo inicial [1, 2]
Soluc¸a˜o.
n >
log(b− a)− log �
log 2
n >
log(2− 1)− log(10−3)
log 2
n >
3
log 2
≈ 9.96
Logo, 10 iterac¸o˜es sa˜o suficientes
Taxa de convergeˆncia
Definic¸a˜o. Uma sequeˆncia {pk} gerada por um me´todo
nume´rico converge para p com ordem n ≥ 1 se ∃c ∈ [0, 1) tal
que
|pk+1 − p|
|pk − p|n ≤ c ∀k ≥ k0
para algum k0 ≥ 0
Taxa de convergeˆncia
Definic¸a˜o. Uma sequeˆncia {pk} gerada por um me´todo
nume´rico converge para p com ordem n ≥ 1 se ∃c ∈ [0, 1) tal
que
|pk+1 − p|
|pk − p|n ≤ c ∀k ≥ k0
para algum k0 ≥ 0
Neste caso, o me´todo e´ dito ser de ordem n
Taxa de convergeˆncia
Definic¸a˜o. Uma sequeˆncia {pk} gerada por um me´todo
nume´rico converge para p com ordem n ≥ 1 se ∃c ∈ [0, 1) tal
que
|pk+1 − p|
|pk − p|n ≤ c ∀k ≥ k0
para algum k0 ≥ 0
Neste caso, o me´todo e´ dito ser de ordem n
Quando n = 1, a constante c e´ denominada de taxa ou fator
de convergeˆncia do me´todo
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Por exemplo, considere
f(x) =
x
8
(63x4−70x2+15)
no intervalo [0,6; 1]
com nmax = 100 e
� = 10−10
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Por exemplo, considere
f(x) =
x
8
(63x4−70x2+15)
no intervalo [0,6; 1]
com nmax = 100 e
� = 10−10
decaimento do erro absoluto
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Por exemplo, considere
f(x) =
x
8
(63x4−70x2+15)
no intervalo [0,6; 1]
com nmax = 100 e
� = 10−10
Portanto, na˜o podemos
dizer que ele e´ um me´todo
de ordem 1 decaimento do erro absoluto
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Isto nos fornece apenas um limite superior para o erro
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Isto nos fornece apenas um limite superior para o erro
Para a func¸a˜o f(x) = x3 + 4x2 − 10, temos a seguinte
estimativa
|p9 − p| ≤ 2− 1
29
≈ 2× 10−3
Taxa de convergeˆncia
Infelizmente, para o me´todo da bissecc¸a˜o, na˜o podemos
garantir que
|pk+1 − p| ≤ c|pk − p|, ∀k ≥ 0
Isto nos fornece apenas um limite superior para o erro
Para a func¸a˜o f(x) = x3 + 4x2 − 10, temos a seguinte
estimativa
|p9 − p| ≤ 2− 1
29
≈ 2× 10−3
mas o erro real e´ bem menor:
|p9 − p| = |1,365230013− 1, 365234375| ≈ 4, 4× 10−6
Implementac¸a˜o
funct ion [ p , r e s , n i t e r ]= b i s s e c c a o ( f , a , b , t o l , nmax )
i f a > b then
e r r o r ( ” I n t e r v a l o i n v a l i d o ” ) ;
end
f a = f ( a ) ; f b = f ( b ) ;
i f s ign ( f a )∗ s ign ( f b ) > 0 then
e r r o r ( ” I n t e r v a l o nao contem r a i z ” ) ;
end
. . .
Implementac¸a˜oi t e r = 0 ;
whi le %t
i t e r = i t e r + 1 ;
p = 0 . 5∗ ( a + b ) ;
f p = f ( p ) ;
e r r = t o l ∗max( 1 , abs ( p ) ) ;
i f ( p−a ) < e r r | i t e r > nmax then
break ;
end
i f s ign ( f a )∗ s ign ( f p ) > 0 then
a = p ; f a = f p ;
e l s e
b = p ;
end
end
i f i t e r > nmax then
warning ( ’ Numero maximo de i t e r a c o e s a t i n g i d o . ’ ) ;
end
r e s = f p ;
endfunctionImplementac¸a˜o
Exemplo de execuc¸a˜o.
−−>d e f f ( ’ y=f ( x ) ’ , ’ y=xˆ3−9∗x+3 ’ )
−−>[p , r e s , n i t e r ] = b i s s e c c a o ( f ,0 ,1 ,10ˆ( −3) ,100)
n i t e r =
10 .
r e s =
0.0060169
p =
0.3369141
Implementac¸a˜o
−−>[p , r e s , n i t e r ] = b i s s e c c a o ( f ,1 ,2 ,10ˆ(−3) ,100)
i t e r a b p f ( p ) p−a
1 1.00000 e+00 2.00000 e+00 1.50000 e+00 2.37500 e+00 5.00000 e−01
2 1.00000 e+00 1.50000 e+00 1.25000 e+00 −1.79688 e+00 2.50000 e−01
3 1.25000 e+00 1.50000 e+00 1.37500 e+00 1.62109 e−01 1.25000 e−01
4 1.25000 e+00 1.37500 e+00 1.31250 e+00 −8.48389e−01 6.25000 e−02
5 1.31250 e+00 1.37500 e+00 1.34375 e+00 −3.50983e−01 3.12500 e−02
6 1.34375 e+00 1.37500 e+00 1.35938 e+00 −9.64088e−02 1.56250 e−02
7 1.35938 e+00 1.37500 e+00 1.36719 e+00 3.23558 e−02 7.81250 e−03
8 1.35938 e+00 1.36719 e+00 1.36328 e+00 −3.21500e−02 3.90625 e−03
9 1.36328 e+00 1.36719 e+00 1.36523 e+00 7.20248 e−05 1.95312 e−03
10 1.36328 e+00 1.36523 e+00 1.36426 e+00 −1.60467e−02 9.76562 e−04
n i t e r =
10 .
r e s =
− 0.0160467
p =
1.3642578
	ECI0010 - Métodos Num. Aplicados à Eng. Civil - Zeros de funções não-lineares
	Método da bissecção
	Exemplo mestre
	Critério de parada
	Retornando ao exemplo mestre
	Análise de convergência
	Número de iterações
	Taxa de convergência
	Implementação