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
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 um intervalo 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
HederS. 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 que
|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 – Implementac¸a˜o
1 #include <stdio.h>
2 #include <math.h>
3
4 float f(float x) {
5 return pow( x / 2.0 , 2 ) - sin( x );
6 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Implementac¸a˜o
1 float bissecao( float a, float b, int maxIt, float tol ) {
2 int k = 0; // passo
3 float fA, fB, fXk; // valores de avaliacao da funcao
4 float xk; // aproximacao da raiz
5 float xkm1; // aproximacao no passo k-1
6 fA = f( a );
7 fB = f( b );
8 if ( fA == 0 ) { //solucao trivial
9 return a;
10 } else if (fB == 0) { //solucao trivial
11 return b;
12 } else if ( fA * fB < 0 ) { //existe solucao no intervalo
13 xk = ( a + b ) / 2;
14 fXk = f( xk );
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Implementac¸a˜o
1 do {
2 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
3 if ( fA * fXk < 0 ) {
4 b = xk; fB = fXk;
5 } else {
6 a = xk; fA = fXk;
7 }
8 xkm1 = xk;
9 xk = ( a + b ) / 2;
10 fXk = f( xk );
11 k++;
12 } while ( fabs( ( xk - xkm1 )/xk ) > tol && k < maxIt );
13 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
14 return xk;
15 } else {
16 printf("Nao ha garantia de haver raiz nesse intervalo.\n");
17 return NAN;
18 }
19 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Bissec¸a˜o
Me´todo da Bissec¸a˜o – Implementac¸a˜o
1 int main() {
2
3 float raiz = bissecao( 1.5, 2.0, 100, 1e-5 );
4
5 printf( "Aproximacao encontrada para a raiz: %f\n", raiz);
6
7 return 0;
8
9 }
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder 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