Método da Bissecção para Solução de Equações

Prévia do material em texto

Cálculo Numérico / Métodos Numéricos
Solução de equações:
Método da bissecção
14:29
Exemplos: f: R → R; f(x) = (x+1)2ex2-2 -1=0
14:29
Idéia da bisseção
x -3 -2 -1 0 1 2 3
f(x) 4385.5 6.4 -1 -0.9 0.5 65.5 17545.1
f(-1.5) = + ou - ?
14:29
Bissecção (algoritmo)
� Dado um intervalo ]a,b[ com f(a) . f(b) < 0
� Escolha c = (a+b)/2
� Se f(c) = 0 → FIM
� Se f(c) . f(a) < 0
� Existe uma raiz no intervalo ]a,c[
� Se f(c) . f(b) < 0
� Existe uma raiz no intervalo ]c,b[
Podemos recomeçar com o novo intervalo e melhorar a 
aproximação da raiz!
14:29
Bissecção (algoritmo)
� Dado um intervalo ]a,b[ com f(a) . f(b) < 0
� A sequência de intervalos será calculada até que a 
amplitude do intervalo seja menor que uma tolerância ε
preestabelecida.
Ao conseguir um intervalo [a,b] tal que: [ ]b,az∈ , z raiz, e ε<− ab então 
[ ] ε<−∈∀ zx,b,ax . Portanto, [ ],b,ax∈∀ pode ser escolhido como x . 
14:29
Bissecção (Exemplo)
� Achar a raiz cúbica de 5
� f(x) = x3 -5 =0
existe raiz entre x=1 e x=2
f(x=1) = -4
f(x=2) = 3
14:29
Bissecção encontra uma raiz!
14:29
Critérios de parada 
� |a-b| < ε1
� |f(c)| < ε2
14:29
Critérios de parada f(x)=ln(x).x-3
� Se critério |f(c)| < ε
1 2 3 4 5 6
−3
−2
−1
1
2
3
x
yy = ln(x)x^(-3)
Mais longe da solução, menor f(x)
14:29
Erro relativo
� Pode ser mais interessante considerar-se o erro relativo. 
|xk+1 - xk|
|xk+1|
< ε
Escrevemos esse erro na forma:
|xk+1-xk| < ε . max{1,|xk+1|} 
(Por que ?) 
(se | xk+1 | estiver próximo de zero, o método não estaciona)
14:29
Critério de parada
� Em relação à precisão pré-fixada. Se ε=10-m , m é o 
número de casa decimais corretas no resultado.
|xk+1 - xk|
|xk+1|
< ε
14:29
Estudo da convergência (1/3)
� Ruggiero e Lopes Cap. 2 O método gera três sequências 
durante o processo {ak}, {bk} {xk}.
[a0,b0]
[a1,b1]
[a2,b2]
[ak,bk]
...
{ak}: não decrescente e limitada 
superiormente por b0
{bk}: não crescente e limitada 
inferiormente por a0
{ } kbxabaxconstruçãoporx kkkkkkk ∀<<




 += ,,
2
14:29
Estudo da convergência (2/3)
� A cada iteração, a amplitude do intervalo é dividida pela 
metade:
= x*
temos que provar que f(x*) = 0
ambos convergentes {ak} e {bk}
14:29
Estudo da convergência (3/3)
� em cada iteração temos f(ak).f(bk) ≤ 0
f(x*) = 0
� Convergência lenta pois se b0-a0>> e se ε for muito 
pequeno, o numero de iterações tende a ser muito 
grande.
Por exemplo, se desejamos encontrar z, o zero da função f(x)=xlog(x)-1 que 
está no intervalo [2,3], com precisão 210−=ε , quantas iterações, no mínimo, 
devemos efetuar? 
K=7. 
Dada uma precisão ε 
Dado um intervalo inicial [a,b] (f(a).f(b)<0) 
Quantas iterações efetuar até que se tenha b-a < ε . 
Qual o valor de k tal que bk-ak< ε ? 
)log()ablog()2log(k
ab
2
2
ab
00
00k
k
00 ε−−>⇒
ε
−>⇒ε<− 
)2log(
)log()ablog(
k 00
ε−−>⇒ . 
Exercício
� Determinar o valor aproximado da raiz quadrada de 5, 
com erro menor ou igual a 0.01. Determine um intervalo 
de amplitude 1 que contém a raiz.
14:29
05x2 =− , intervalo [2,3] 
i(iteração) ai bi xi b-ai 
0 2 (-) 3(+) 2.5 (+) 0.5 
1 2(-) 2.5(+) 2.25(+) 0.25 
2 2(-) 2.25(+) 2.125(-) 0.125 
3 2.125(-) 2.25 (+) 2.1875(-) 0.0625 
4 2.1875 2.25 2.21875 0.03125 
5 2.21875 2.25 2.234375 0.015625 
6 2.234375 2.25 2.2421875 .0078125 
 
234375.25 ≈