aula06 raiz

Prévia do material em texto

Ca´lculo Nume´rico
Ra´ızes Reais de uma Equac¸a˜o
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Introduc¸a˜o
3 Me´todo da Bissec¸a˜o
4 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Operac¸o˜es aritme´ticas em sistemas de ponto flutuante
◮ Soma/Subtrac¸a˜o e Multiplicac¸a˜o/Divisa˜o
◮ Propriedades aritme´ticas
◮ Noc¸o˜es ba´sicas sobre erros
◮ Erro absoluto
◮ Erro relativo
◮ Efeitos nume´ricos
◮ Somar (ou subtrair) nu´meros com ordens de grandeza muito diferentes
◮ Cancelamento
◮ Propagac¸a˜o do erro
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Propriedade Aritme´tica
1 from pylab import *
2
3 x1 = 1.23456789
4 x2 = 98765432.1
5 x3 = 24682.1357
6
7 resultado1 = x3 * ( x2 - x1 )
8 resultado2 = x3 * x2 - x3 * x1
9
10 print("Resultado x3 * ( x2 - x1 ): " + str( resultado1 ) )
11 print("Resultado x3 * x2 - x3 * x1: " + str( resultado2 ) )
12 print("Comparando os resultados: " + str( resultado1==resultado2 ) )
13 print("Diferenca: " + str( abs( resultado1-resultado2 ) ) )
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Propriedade Aritme´tica
◮ Resultado ao executar
1 Resultado x3 * ( x2 - x1 ): 2.43774176709e+12
2 Resultado x3 * x2 - x3 * x1: 2.43774176709e+12
3 Comparando os resultados: False
4 Diferenca: 0.00048828125
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Somato´rio
1 fracao = 0.1
2 soma = 0.0
3 i = 0
4 passos = 10000000
5
6 while i < passos:
7 soma += fracao
8 i += 1
9
10 resultadoEsperado = fracao * passos
11
12 print "Resultado obtido: \t" + str( soma )
13 print "Resultado esperado: \t" + str( resultadoEsperado )
14 print "Diferenca: " + str( resultadoEsperado - soma )
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Somato´rio
◮ Resultado ao executar
1 Resultado obtido: 999999.999839
2 Resultado esperado: 1000000.0
3 Diferenca: 0.000161024625413
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Cancelamento
1 from pylab import *
2
3 #aproximacao utilizando diferenca progressiva
4 def aproximacao_derivada_sen( x, h ):
5 derivada = ( sin( x + h ) - sin( x ) ) / h
6 return derivada
7
8 #valor exato da derivada
9 def derivada_sen( x ):
10 derivada = cos( x )
11 return derivada
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Cancelamento – continuac¸a˜o
1 x = 2.0
2 h = 0.1
3 derivada = derivada_sen( x )
4 iis = [ ]
5 erros = [ ]
6 maxI = 50
7 i = 0
8 while i < maxI:
9 aproximacao = aproximacao_derivada_sen( x, h )
10 erroAbsoluto = abs( aproximacao - derivada )
11 print( str( i ) + "\t" + str( h ) + "\t" + str( erroAbsoluto ) )
12 iis.append( i ) #inclui ’i’ no array
13 erros.append( erroAbsoluto ) #inclui ’erroAbsoluto’ no array
14 i += 1
15 h /= 2.0 #decrementa ’h’ pela metada
16
17 xlabel("i")
18 ylabel("erro")
19 plot( iis, erros )
20 show()
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Exemplos em Python – Cancelamento
0 10 20 30 40 50
i
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
e
r
r
o
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Sera˜o estudados aqui me´todos nume´ricos para a resoluc¸a˜o do
problema de determinar as ra´ızes de uma equac¸a˜o f(x) = 0
◮ ou, o que e´ o mesmo, determinar os zeros da func¸a˜o f(x)
◮ Tais ra´ızes podem ser reais ou complexas
◮ Considera-se aqui o caso em que f e´ uma func¸a˜o real de uma varia´vel
real x
◮ Sera´ estudada somente a determinac¸a˜o de ra´ızes reais
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ As ra´ızes correspondem aos pontos onde o gra´fico da func¸a˜o f(x)
intercepta o eixo x
✲
x
✻y
f(x)
r1 r2 r3
s s s
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Expresso˜es fechadas existem para alguns polinoˆmios
◮ Polinoˆmio Quadra´tico
ax2 + bx+ c = 0⇒ r1,2 = −b±
√
b2 − 4ac
2a
◮ Como na˜o existe uma forma direta para encontrar os zeros de uma
func¸a˜o f(x) qualquer, enta˜o recorre-se a me´todos aproximados
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Definic¸a˜o (raiz):
Seja f : [a, b]→ R uma func¸a˜o dada, enta˜o um ponto r ∈ [a, b] e´ um
zero (ou raiz) de f se f(r) = 0.
◮ Exemplo:
0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
x
−6
−4
−2
0
2
4
6
y
f(x) = ( x - 1)*( x - 2 )*( x - 3 )
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Pode ocorrer da func¸a˜o f(x) tangenciar o eixo x no ponto r, ou seja
f(r) = 0 e f ′(r) = 0, o que caracteriza r como uma raiz dupla.
◮ Definic¸a˜o (multiplicidade):
Uma raiz r da equac¸a˜o f(x) = 0 tem multiplicidade m (inteira) se
f(x) e´ m-vezes diferencia´vel em x = r,
f(r) = f ′(r) = · · · = f (m−1)(r) = 0 e f (m)(r) 6= 0.
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Exemplo
◮ Exemplo 1
Seja f(x) = x2 − 2x+ 1 = (x− 1)2. Mostre que a raiz r = 1 de
f(x) = 0 tem multiplicidade 2.
◮ Soluc¸a˜o:
f(1) = 0
f ′(x) = 2(x− 1)⇒ f ′(1) = 0
f ′′(x) = 2⇒ f ′′(1) = 2 6= 0
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Os me´todos nume´ricos estudados aqui seguem as seguintes etapas
◮ Isolamento das ra´ızes
◮ Encontrar um intervalo [a, b] que contenha apenas uma raiz, ou
◮ Determinar uma aproximac¸a˜o inicial x0
(ou mais de uma, dependendo do me´todo)
◮ Refinamento
◮ Gerar uma sequeˆncia {x0, x1, . . . } que convirja para a raiz exata r de
f(x) = 0
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Teorema:
Seja f : [a, b]→ R uma func¸a˜o cont´ınua. Se f(a)f(b) < 0, enta˜o
existe pelo menos um ponto x ∈ [a, b] tal que f(x) = 0.
◮ Geometricamente, o teorema afirma que a curva de uma func¸a˜o
cont´ınua que comec¸a abaixo do eixo horizontal e termina acima dele,
deve cruzar o eixo em algum ponto
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Exemplo
◮ Existem 3 ra´ızes no intervalo [0, 4]
◮ Existem 2 ra´ızes no intervalo [0,5; 2,5]
◮ Nota-se que f(0,5) = −1.875 e f(2,5) = −0.375
0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
x
−6
−4
−2
0
2
4
6
y
f(x) = ( x - 1)*( x - 2 )*( x - 3 )
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Como encontrar o intervalo da raiz r > 0 de f(x) =
(
x
2
)2 − sen(x)?
−1.0 −0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0
x
−1.0
−0.5
0.0
0.5
1.0
1.5
2.0
2.5
y
f(x)
◮ Inspec¸a˜o visual
◮ No exemplo, r ∈ [1,5; 2]
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Outra possibilidade e´ fazer uma tabela de valores
x f(x) sinal
0,5 -0,416925538604 < 0
1,0 -0,591470984808 < 0
1,5 -0,434994986604 < 0
2,0 0,0907025731743 > 0
2,5 0,964027855896 > 0
3,0 2,10887999194 > 0
◮ Logo, ha´ ao menos uma raiz em [1,5; 2]
◮ Outra possibilidade e´ fixar o in´ıcio do intervalo x = a e procurar b de
modo que f(a)f(b) < 0
◮ b = a+ h, a+ 2h, a+ 4h, . . .
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ Teorema
Sob as hipo´teses do teorema anterior, se f ′(x) existir e preservar o
sinal em [a, b], enta˜o o intervalo conte´m um u´nico zero de f(x).
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Exemplo
◮ Exemplo 2
Encontre umintervalo de tamanho unita´rio em que haja ao menos
uma raiz para f(x) =
√
x− 5e−x = 0 de modo que x ≥ 0.
◮ Soluc¸a˜o:
x f(x) sinal
0 -5,0 < 0
1,0 -0,839397205857 < 0
2,0 0,73753714619 > 0
◮ Logo, pelos dados apresentados na tabela e sendo f(x) cont´ınua no
intervalo [1, 2], enta˜o ha´ ao menos uma raiz em [1, 2]
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Exemplo
◮ Exemplo 3
Ha´ garantia de haver apenas uma raiz para f(x) =
√
x− 5e−x = 0 no
intervalo [1, 2]?
◮ Soluc¸a˜o:
Sim, pois f(x) e´ cont´ınua nesse intervalo, f(1)f(2) < 0 e
f ′(x) = 1
2
√
x
+ 5e−x > 0, ∀x > 0
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Crite´rio de Parada
◮ Definido o intervalo (ou formas de inicializac¸a˜o), pode-se enta˜o gerar
iterativamente uma sequeˆncia de aproximac¸o˜es para a raiz de f(x)
◮ Antes de estudar os me´todos nume´ricos para gerac¸a˜o dessas
aproximac¸o˜es, e´ importante definir um crite´rio de parada para o
processo iterativo
◮ Alguns dos crite´rios normalmente adotados sa˜o:
|xk − xk−1| ≤ ǫ |xk − xk−1||xk| ≤ ǫ |f(xk)| ≤ ǫ
onde
◮ k e´ o passo do processo iterativo
◮ ǫ e´ a precisa˜o/toleraˆncia da soluc¸a˜o
◮ Pode-se adicionar um nu´mero ma´ximo de iterac¸o˜es para evitar que o
programa itere indefinidamente
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
◮ O me´todo baseia-se na ideia de que seja f(x) cont´ınua e
f(a)f(b) < 0, enta˜o existe ao menos uma raiz no intervalo [a, b]
◮ A cada passo, o intervalo e´ dividido ao meio
◮ xk =
a+b
2
◮ O novo (sub-)intervalo sera´ aquele que conte´m a raiz
◮ [a, xk], se f(a)f(xk) < 0
◮ [xk, b], caso contra´rio
◮ A busca continua ate´ o crite´rio de parada ser atendido
b− a ≤ ǫ |f(xk)| ≤ ǫ |xk − xk−1||xk| ≤ ǫ
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a
b
f(a)
f(b)
r r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a x1
b
f(a)
f(b)
r r r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a
b
r r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a
x2 b
r r r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a
b
r r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a
x3 b
r rr
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a
b
r r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a x4
b
r r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
✲
x
✻
y
a x1 x4
x3 x2 b
f(a)
f(b)
r r r r
r
r
r
r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o
Entrada: f(x) cont´ınua em [a, b], intervalo [a, b] tal que f(a)f(b) < 0,
precisa˜o ǫ e ma´ximo nu´mero de iterac¸o˜es
1 inicio
2 k ←− 0;
3 enquanto crite´rio de parada na˜o e´ satisfeito fac¸a
4 xk ←− a+b2 ;
5 se f(a)f(xk) < 0 enta˜o
6 b←− xk;
7 sena˜o
8 a←− xk;
9 k ←− k + 1;
10 retorna xk
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Exemplo
◮ Exemplo 4
Encontre uma aproximac¸a˜o para o zero da func¸a˜o
f(x) =
(
x
2
)2 − sen(x) no intervalo [1,5; 2] executando 5 passos do
me´todo da bissec¸a˜o
◮ Soluc¸a˜o:
k a b xk f(a) f(b) f(xk)
0 1,5 2 1,75 −0,4349 0,0907 −0,2184
1 1,75 2 1,875 −0,2184 0,0907 −0,0752
2 1,875 2 1,9375 −0,0752 0,0907 0,0050
3 1,875 1,9375 1,90625 −0,0752 0,0050 −0,035814
4 1,90625 1,9375 1,921875 −0,035814 0,0050 −0,015601
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Ana´lise
◮ A cada interac¸a˜o k, a raiz de f(x) = 0 esta´ num intervalo [ak, bk]
◮ Assim, sendo r a soluc¸a˜o do problema, pode-se dizer que
|r − xk| ≤ 12(bk − ak)
◮ Ale´m disso, o intervalo (bk − ak) no passo k pode ser escrito como
bk − ak = bk−1 − ak−1
2
=
bk−2 − ak−2
22
= · · · = b0 − a0
2k
◮ Logo, o erro absoluto no passo k satisfaz
|r − xk| ≤ b0 − a0
2k+1
onde a0 e b0 sa˜o os limites do intervalo original
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Ana´lise
◮ O limitante para o erro absoluto pode ser utilizado para determinar o
nu´mero de iterac¸o˜es necessa´rias para se obter uma raiz com uma
dada precisa˜o ǫ
◮ Considerando como crite´rio de parada
b− a ≤ ǫ
◮ Nesse sentido, deseja-se determinar k tal quer
|r − xk| ≤ b0 − a0
2k+1
≤ ǫ
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Ana´lise
◮ Logo,
b0 − a0
2k+1
≤ ǫ
b0 − a0
ǫ
≤ 2k+1
2k+1 ≥ b0 − a0
ǫ
log2(2
k+1) ≥ log2
(
b0 − a0
ǫ
)
k + 1 ≥ log2
(
b0 − a0
ǫ
)
k ≥ log2
(
b0 − a0
ǫ
)
− 1 ou k ≥
ln
(
b0−a0
ǫ
)
ln(2)
− 1
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Exemplo
◮ Exemplo 5
Qual o nu´mero de iterac¸o˜es necessa´rias para encontrar uma
aproximac¸a˜o para o zero da func¸a˜o f(x) =
(
x
2
)2 − sen(x) no intervalo
[1,5; 2] de modo que b− a ≤ ǫ = 10−5?
◮ Soluc¸a˜o:
k ≥ log2
(
b0 − a0
ǫ
)
− 1 = log2
(
2− 1,5
10−5
)
− 1 ≈ 15,61− 1 = 14,61
Logo, encontra-se a aproximac¸a˜o para a soluc¸a˜o do problema com a
precisa˜o desejada a partir da iterac¸a˜o 15
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Ordem de Convergeˆncia
◮ Uma forma de avaliar o desempenho das te´cnicas e´ definir a rapidez
com a qual a sequeˆncia de aproximac¸o˜es {x0, x1, . . . } converge para a
raiz r
◮ Definic¸a˜o (Ordem de Convergeˆncia): Uma sequeˆncia {xn | n ≥ 0}
e´ dita convergir com ordem p ≥ 1 para um ponto r se
|r − xn| ≤ c|r − xn−1|p
para uma constante c > 0.
◮ Sendo c < 1, enta˜o diz-se que
◮ Se p = 1: convergeˆncia linear
◮ Se 1 < p < 2: convergeˆncia super-linear
◮ Se p = 2: convergeˆncia quadra´tica
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Ordem de Convergeˆncia
◮ No Me´todo da Bissec¸a˜o o erro cai pela metade (em me´dia) a cada
iterac¸a˜o, ou seja,
|r − xk|
|r − xk−1| ≤
1
2
Assim,
|r − xk| ≤ 1
2
|r − xk−1|
e verifica-se que este me´todo tem ordem de convergeˆncia p = 1
(linear)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Exemplo em Python
1 from pylab import *
2
3 def bissecao( f, a, b, epsilon=1e-8 ):
4 if f(a)*f(b) > 0:
5 print "Nao ha garantia de haver raiz no intervalo solicitado."
6 return None
7 k = 0
8 xk = a
9 while abs( b-a ) > epsilon:
10 xk = (a + b) / 2
11 print "%d\t%e\t%e" %( k, xk, f(xk) )
12 if f(a)*f(xk) < 0:
13 b = xk
14 else:
15 a = xk
16 k = k + 1
17 return xk
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Exemplo em Python – cont.
1 # Funcao que se deseja encontrar o zero
2 def f( x ):
3 return ( x / 2.0 )**2 - sin( x )
4
5 # Busca o zero da funcao f usando o Metodo da Bissecao
6 xk = bissecao( f, 1.5, 2, 1e-5 )
7
8 # Imprime o resultado: raiz da equacao f(x) = 0
9 print "Raiz da equacao: " + str( xk )
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜oHeder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Introduc¸a˜o
◮ Definic¸a˜o de raiz
◮ Definic¸a˜o de Multiplicidade
◮ Existeˆncia de ao menos uma raiz no intervalo [a, b] quando f(x) e´
cont´ınua e f(a)f(b) < 0
◮ Unicidade da raiz no intervalo
◮ Determinac¸a˜o de um intervalo que contenha alguma raiz
◮ Crite´rio de parada
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Me´todo da Bissec¸a˜o
◮ Utiliza a ideia da existeˆncia de ao menos uma raiz no intervalo [a, b]
quandof(x) e´ cont´ınua e f(a)f(b) < 0
◮ O intervalo e´ divido ao meio a cada iterac¸a˜o
◮ Ordem de convergeˆncia linear
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Introdução
	Método da Bisseção
	Revisão