Método da Bisseção para Solução Numérica de Equações

Prévia do material em texto

GEX114 - Ca´lculo Nume´rico
Profa.Dra.Amanda Castro Oliveira
Departamento de Cieˆncias Exatas - DEX/UFLA
amanda@dex.ufla.br
Aula 7 - Cap.2 Soluc¸o˜es Nume´ricas de Equac¸o˜es
Na aula passada:
Dizemos que δ e´ uma raiz ou um zero de uma func¸a˜o f (x) se
f (δ) = 0.
Queremos investigar se ∃δ ∈ D(f ) tal que f (δ) = 0. δ ∈ <.
Teo. 2.1: Seja f (x) uma func¸a˜o cont´ınua num intervalo [a, b].
Se f (a)f (b) < 0 enta˜o existe pelo menos um ponto δ ∈ [a, b]
tal que f (δ) = 0.
Considerando as hipo´teses do Teorema 2.1, se f ′(x) existir e
preservar o sinal em (a, b) enta˜o este intervalo conte´m um
u´nico zero de f (x).
Fase I: Isolamento das Ra´ızes (Me´todo Gra´fico)
Trac¸amos gra´fico de f (x) ou transformamos a equac¸a˜o
f (x) = 0 na equac¸a˜o equivalente g(x) = h(x).
2.3 Fase II: Refinamento das Ra´ızes (Me´todos Iterativos)
Estudaremos agora va´rios me´todos nume´ricos para o
refinamento da raiz.
Todos eles sa˜o me´todos iterativos.
A forma como este refinamento e´ feito e´ o que diferencia os
me´todos.
Um me´todo iterativo consiste em uma sequeˆncia de instruc¸o˜es
que sa˜o executadas passo a passo, algumas das quais sa˜o
repetidas em ciclos.
A execuc¸a˜o de cada ciclo recebe o nome de iterac¸a˜o. Cada
iterac¸a˜o usa os resultados das iterac¸o˜es anteriores e efetua
determinados testes para verificar se foi atingido um resultado
pro´ximo o suficiente do resultado esperado.
2.3.1 Crite´rios de Parada
Todos os me´todos iterativos para se obter ra´ızes de func¸o˜es
efetuam um teste do tipo:
xk esta´ suficientemente pro´ximo da raiz exata?
Que tipo de teste devemos fazer para verificarmos se xk esta´
suficientemente pro´ximo da raiz exata?
Primeiramente devemos entender que existem 2 interpretac¸o˜es
para a raiz aproximada (r.a.) que nem sempre levam ao
mesmo resultado.
x¯ e´ a raiz aproximada com precisa˜o � se:
(i) |x¯ − δ| < � ou
(ii) |f (x¯)| < �.
Como fazer o primeiro teste se na˜o conhecemos δ?
2.3.1 Crite´rios de Parada
Todos os me´todos iterativos para se obter ra´ızes de func¸o˜es
efetuam um teste do tipo:
xk esta´ suficientemente pro´ximo da raiz exata?
Que tipo de teste devemos fazer para verificarmos se xk esta´
suficientemente pro´ximo da raiz exata?
Primeiramente devemos entender que existem 2 interpretac¸o˜es
para a raiz aproximada (r.a.) que nem sempre levam ao
mesmo resultado.
x¯ e´ a raiz aproximada com precisa˜o � se:
(i) |x¯ − δ| < � ou
(ii) |f (x¯)| < �.
Como fazer o primeiro teste se na˜o conhecemos δ?
2.3.1 Crite´rios de Parada
Podemos reduzir o intervalo que conte´m a raiz a cada iterac¸a˜o. Ao
se conseguir um intervalo [a, b] tal que:
δ ∈ [a, b] e
b − a < �
enta˜o ∀x ∈ [a, b], teremos sempre que |x − δ| < �. Logo qualquer
x ∈ [a, b] podera´ ser tomado como uma r.a. x¯ .
2.3.1 Crite´rios de Parada
Nem sempre e´ poss´ıvel atender simultaneamnte a`s exigeˆncias
de (i) e (ii).
Com o uso dos me´todos nume´ricos estamos interessados em
satisfazer a pelo menos um dos crite´rios.
Dependendo da ordem de grandeza dos nu´meros envolvidos
deve-se usar o teste do erro relativo. Ou seja, considerar x¯
como uma boa aproximac¸a˜o da raiz δ se
| f (x¯)
f (x)
| < �
para algum x escolhido na vizinhanc¸a de δ.
Ale´m destes testes no caso de uma implementac¸a˜o
computacional devemos tambe´m estipular um nu´mero ma´ximo
de iterac¸o˜es.
2.4.1 Me´todo da Bissecc¸a˜o
Figura: Func¸a˜o com raiz em x = δ com f (a0) < 0 e f (b0) > 0.
2.4.1 Me´todo da Bissecc¸a˜o
O me´todo da bissec¸a˜o e´ o me´todo conceitualmente mais
simples e bem intuitivo.
Esta´ baseado na ideia de”cercar”a raiz x¯ por dois valores: um
a` esquerda da raiz (ai ) e outro a` direita (bi ), formando um
intervalo que vai sendo continuamente reduzido ate´ que a
largura final do intervalo seja ta˜o pequena quanto o erro
absoluto da raiz �.
A reduc¸a˜o cont´ınua da largura do intervalo e´ feita dividindo-se
o intervalo ao meio e definindo um valor me´dio xi pela
expressa˜o:xi =
ai+bi
2
E´ usado para se determinar ra´ızes de func¸o˜es que atendam a`s
hipo´teses do teorema 2.1.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
1 Determine um intervalo inicial [ai , bi ] tal que f (ai )f (bi ) < 0.
2 Calcule a raiz aproximada considerando xi =
ai+bi
2
Se |f (xi )| < � enta˜o xi e´ a raiz procurada e o processo
terminou. Sena˜o:
Se f (ai )f (xi ) < 0 enta˜o ai+1 = ai e bi+1 = xi sena˜o:
f (ai )f (xi ) > 0 enta˜o ai+1 = xi e bi+1 = bi
3 Repita este processo ate´ que |f (xi )| < � ou |bi − ai | < �
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
Ex.1 Seja f (x) = x ln(x)− 1 encontre as ra´ızes desta func¸a˜o com
� = 0.01
FASE I: Localizac¸a˜o ou isolamento das ra´ızes:
x ln(x)− 1 = 0⇔ ln(x) = 1
x
com x 6= 0.
loga(x) = b ⇔ ab = x
loge(x) = b ⇔ eb = x
enta˜o D ln(x) =]0,∞[
Vemos que δ ∈]1, 2[, enta˜o tomamos a0 = 1 e b0 = 2.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
Ex.1 Seja f (x) = x ln(x)− 1 encontre as ra´ızes desta func¸a˜o com
� = 0.01
FASE I: Localizac¸a˜o ou isolamento das ra´ızes:
x ln(x)− 1 = 0⇔ ln(x) = 1
x
com x 6= 0.
loga(x) = b ⇔ ab = x
loge(x) = b ⇔ eb = x
enta˜o D ln(x) =]0,∞[
Vemos que δ ∈]1, 2[, enta˜o tomamos a0 = 1 e b0 = 2.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
Ex.1 Seja f (x) = x ln(x)− 1 encontre as ra´ızes desta func¸a˜o com
� = 0.01
FASE I: Localizac¸a˜o ou isolamento das ra´ızes:
x ln(x)− 1 = 0⇔ ln(x) = 1
x
com x 6= 0.
loga(x) = b ⇔ ab = x
loge(x) = b ⇔ eb = x
enta˜o D ln(x) =]0,∞[
Vemos que δ ∈]1, 2[, enta˜o tomamos a0 = 1 e b0 = 2.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
Figura: g(x) = ln(x) e h(x) = 1x com x ∈ [0.1, 3]
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para araiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo
i ai , f (ai ) bi , f (bi ) xi f (xi ) bi − ai
1 1, < 0 2, > 0 1.5 −0.391802 1
2 1.5, < 0 2, > 0 1.75 −0.020672 0.5
3 1.75, < 0 2, > 0 1.875 0.1786412 0.25
4 1.75, < 0 1.875, > 0 1.8125 0.077906 0.125
5 1.75, < 0 1.8125, > 0 1.78125 0.028342 0.0625
6 1.75, < 0 1.78125, > 0 1.765625 0.003766 0.03125
7 1.75, < 0 1.765625, > 0 1.7578125 −0.008470 0.015625
Como 1.765625− 1.7578125 = 0.0078125 < 0.01 temos que
x¯ = 1.7578125 e´ uma boa aproximac¸a˜o para a raiz procurada com
precisa˜o de � = 0.01.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estudo da
convergeˆncia
Theorem
Seja f (x) uma func¸a˜o cont´ınua em [a, b], onde f (a)f (b) < 0.
Enta˜o o me´todo da Bissecc¸a˜o gera uma sequeˆncia xk que converge
para a raiz δ quando k →∞.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estudo da
convergeˆncia
Suponhamos que [a0, b0] seja o intervalo inicial e que a raiz δ seja
u´nica no interior desse intervalo. O me´todo da bissecc¸a˜o gera treˆs
sequeˆncias:
ak : na˜o decrescente e limitada superiormente por b0;
enta˜o existe r ∈ < tal que lim
k→∞
ak = r
bk : na˜o crescente e limitada inferiormente por a0; enta˜o
existe s ∈ < tal que lim
k→∞
bk = s
xk : e´ tal que ak < xk < bk , por construc¸a˜o xk =
ak+bk
2 .
A amplitude de cada intervalo gerado e´ a metade da amplitude
anterior.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estudo da
convergeˆncia
Suponhamos que [a0, b0] seja o intervalo inicial e que a raiz δ seja
u´nica no interior desse intervalo. O me´todo da bissecc¸a˜o gera treˆs
sequeˆncias:
ak : na˜o decrescente e limitada superiormente por b0;
enta˜o existe r ∈ < tal que lim
k→∞
ak = r
bk : na˜o crescente e limitada inferiormente por a0; enta˜o
existe s ∈ < tal que lim
k→∞
bk = s
xk : e´ tal que ak < xk < bk , por construc¸a˜o xk =
ak+bk
2 .
A amplitude de cada intervalo gerado e´ a metade da amplitude
anterior.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estudo da
convergeˆncia
Suponhamos que [a0, b0] seja o intervalo inicial e que a raiz δ seja
u´nica no interior desse intervalo. O me´todo da bissecc¸a˜o gera treˆs
sequeˆncias:
ak : na˜o decrescente e limitada superiormente por b0;
enta˜o existe r ∈ < tal que lim
k→∞
ak = r
bk : na˜o crescente e limitada inferiormente por a0; enta˜o
existe s ∈ < tal que lim
k→∞
bk = s
xk : e´ tal que ak < xk < bk , por construc¸a˜o xk =
ak+bk
2 .
A amplitude de cada intervalo gerado e´ a metade da amplitude
anterior.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estudo da
convergeˆncia
Assim temos que:
(bk − ak) = (bk−1 − ak−1)
2
= · · · = (b0 − a0)
2k
.
Enta˜o lim
k→∞
(bk − ak) = lim
k→∞
(b0 − a0)
2k
= 0.
Como ak e bk sa˜o sequeˆncias convergentes,
lim
k→∞
bk − lim
k→∞
ak = 0⇒ lim
k→∞
bk = lim
k→∞
ak . Enta˜o r = s.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estudo da
convergeˆncia
Seja m = r = s o limite das duas sequeˆncias. Dado que para todo
k o ponto xk pertence ao intervalo (ak , bk), o Ca´lculo Diferencial e
Integral nos garante que
lim
k→∞
(xk) = m.
Resta-nos mostrar que ale´m disso o limite acima e´ a raiz da
equac¸a˜o f (x) = 0, ou seja, f (m) = 0.
Como f (ak)f (bk) < 0. para qualquer k , enta˜o temos que
0 ≥ lim
k→∞
f (ak)f (bk) = lim
k→∞
f (ak) lim
k→∞
f (bk) = f (r)f (s) = [f (r)]
2 ≥ 0
Portanto 0 ≥ [f (r)]2 ≥ 0⇒ f (r) = 0 e lim
k→∞
(xk) = r
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estimativa do
nu´mero de iterac¸o˜es
Pelo crite´rio de parada podemos observar que o nu´mero de
iterac¸o˜es depende do intervalo inicial [a0, b0] e da precisa˜o
requerida �. Dada uma precisa˜o � temos,
(bk − ak) < �⇒ (b0 − a0)
2k
< �⇒ 2k > (b0 − a0)
�
Como estes valores sa˜o sempre positivos, podemos aplicar a func¸a˜o
logaritmo, obtendo:
k >
log (b0 − a0)− log �
log (2)
Portanto k e´ o nu´mero m´ınimo de iterac¸o˜es necessa´rias para que o
me´todo da bissecc¸a˜o encontre a raiz procurada x¯ com a precisa˜o �.
2.4.1 Me´todo da Bissecc¸a˜o-algoritmo-estimativa do
nu´mero de iterac¸o˜es
Ex.1 Seja f (x) = x ln(x)− 1 encontre as ra´ızes desta func¸a˜o com
� = 0.01 Como a0 = 1 e b0 = 2 temos que
k >
log (2− 1)− log 10−2
log (2)
=
log 1 + 2 log 10
log (2)
=
2
0.3010
= 6.64!
Que esta´ de acordo com o resultado encontrado no exemplo em
que tivemos k = 7.
2.2 Fase I: Isolamento das Ra´ızes (Me´todo Gra´fico)
O me´todo da Bissecc¸a˜o sempre vai alcanc¸ar eˆxito se f (x) e´ uma
func¸a˜o cont´ınua em [a, b], onde f (a)f (b) < 0, entretanto sua
convergeˆncia para uma boa aproximac¸a˜o pode ser muito lenta. Em
geral ele e´ usado para conseguirmos uma primeira aproximac¸a˜o
para a raiz que depois e´ aproximada com maior precisa˜o e
velocidade por um outro me´todo.
Ex.2: Considere b0 − a0 = 3 e � = 10−7, assim
k >
log (3)− log 10−7
log (2)
=
log 3 + 7 log 10
log (2)
= 24.8!
Exerc´ıcio: Seja f (x) = ( x2 )
2 − sin(x) encontre a raiz positiva desta
equac¸a˜o considerando � = 10−3
Pro´xima aula
2. Fase II: Refinamento das Ra´ızes (Me´todos da Falsa Posic¸a˜o)
Por hoje e´ so´ pessoal!!
Este material e´ inteiramente baseado na bibliografia do curso,
principalmente no livro texto :RUGIERO, M. A.G; LOPES,V
Ca´lculo Nume´rico: Aspectos teo´ricos e computacionais, Editora
McGraw-Hill.1997. Sites consultados acessados em 24/03/2011:
CASTILHO, J. E., Apostila de Ca´lculo Nume´rico,
http://www.castilho.prof.ufu.br, UFU, 2002
http://www.alunos.eel.usp.br/numerico/notas.html
Este material na˜o substitui a bibliografia.