aula07_raiz (1)

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 Me´todo da Falsa Posic¸a˜o
3 Me´todo do Ponto Fixo
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
◮ 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
Aula Anterior
Aula Anterior
◮ 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
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
◮ Nesse me´todo, a aproximac¸a˜o xk para a raiz r passa a ser o zero da
reta que passa pelos pontos (ak, f(ak)) e (bk, f(bk))
◮ Assim como o Me´todo da Bissec¸a˜o, o intervalo e´ atualizado a cada
iterac¸a˜o mantendo a raiz em seu interior
◮ f(a)f(b) < 0
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
No Me´todo da Bissec¸a˜o
✲
x
✻
y
a x0 =
a+b
2
b
f(a)
f(b)
r r r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
✲
x
✻
y
a
b
reta
x0
f(a)
f(b)
r r
r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
✲
x
✻
y
b
reta
a
f(a)
f(b)
f(a)f(b) < 0
x1
r
r
r
r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
✲
x
✻
y
a
f(a)
f(b)
b
x2
r
r
r
r
r
r
r
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
◮ Determinando xk:
◮ A reta g(x) da equac¸a˜o que passa pelos pontos (ak, f(ak)) e
(bk, f(bk)) e´ tal que
g(x) = px+ q ⇒
{
f(a) = pa+ q
f(b) = pb+ q
◮ Subtraindo as equac¸o˜es
f(b)− f(a) = pb− pa ⇒ p = f(b)− f(a)
b− a
◮ Ale´m disso,
f(b) = pb− q ⇒ f(b) =
(
f(b)− f(a)
b− a
)
b+ q
⇒ q = f(b)−
(
f(b)− f(a)
b− a
)
b
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
◮ Determinando xk:
◮ Substituindo os valores determinados para p e q em g(x) = px+ q
g(x) =
(
f(b)− f(a)
b− a
)
x+ f(b)−
(
f(b)− f(a)
b− a
)
b
◮ xk e´ determinado de modo que g(xk) = 0, logo
0 =
(
f(b)− f(a)
b− a
)
xk + f(b)−
(
f(b)− f(a)
b− a
)
b(
f(b)− f(a)
b− a
)
xk = −f(b) +
(
f(b)− f(a)
b− a
)
b(
f(b)− f(a)
b− a
)
xk =
−f(b) (b− a) + (f(b)− f(a)) b
b− a
(f(b)− f(a))xk = −f(b) (b− a) + (f(b)− f(a)) b
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
◮ Determinando xk:
(f(b)− f(a))xk = −f(b) (b− a) + (f(b)− f(a)) b
(f(b)− f(a))xk = −bf(b) + af(b) + bf(b)− bf(a)
(f(b)− f(a))xk = af(b)− bf(a)
xk =
af(b)− bf(a)
f(b)− f(a)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o
◮ Dado um intervalo [a, b] que conte´m uma raiz para f(x) = 0, enta˜o o
Me´todo da Falsa Posic¸a˜o pode enta˜o ser descrito como
◮ Calcula-se a aproximac¸a˜o xk:
xk =
af(b)− bf(a)
f(b)− f(a)
◮ Determina-se o novo (sub-)intervalo, que 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
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸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 ←− af(b)−bf(a)f(b)−f(a) ;
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 Falsa Posic¸a˜o
Exemplo
◮ Exemplo 1
Encontre uma aproximac¸a˜o para o zero da func¸a˜o
f(x) =
(
x
2
)2 − sen(x) no intervalo [1,5; 2] utilizando o Me´todo da
Falsa Posic¸a˜o, com |f(xk)| < ǫ = 10−4.
◮ Soluc¸a˜o:
k a b xk f(a) f(b) f(xk)
0 1,5 2 1,913731 −4,349950e− 01 9,070e− 02 −2,618006e− 02
1 1,913731 2 1,933054 −2,618006e− 02 9,070e− 02 −9,243996e− 04
2 1,933054 2 1,933730 −9,243996e− 04 9,070e− 02 −3,193009e− 05
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o – Ordem de Convergeˆncia
◮ A ana´lise de convergeˆncia do Me´todo da Falsa Posic¸a˜o na˜o sera´
apresentada aqui
◮ O me´todo apresenta convergeˆncia linear
◮ Mais detalhes no livro:
◮ Algoritmos Nume´ricos
◮ Frederico F. Campos
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o – Implementac¸a˜o
1 #include <stdio.h>
2 #include <math.h>
3
4 /* Funcao f(x) */
5 float f(float x) {
6 return pow( x / 2.0 , 2 ) - sin( x );
7 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o – Implementac¸a˜o
1 float falsaPosicao( float a, float b, int maxIt, float tol ) {
2
3 int k = 0; // passo
4 float fA, fB, fXk; // valores de avaliacao da funcao
5 float xk; // aproximacao da raiz
6 float xkm1; // aproximacao no passo k-1
7
8 fA = f( a );
9 fB = f( b );
10 if ( fA == 0 ) { //solucao trivial
11 return a;
12 } else if (fB == 0) { //solucao trivial
13 return b;
14 } else if ( fA * fB < 0 ) { //existe solucao no intervalo
15 xk = ( a*fB - b*fA ) / ( fB - fA );
16 fXk = f( xk );
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Falsa Posic¸a˜o
Me´todo da Falsa Posic¸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*fB - b*fA ) / ( fB - fA );
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 Falsa Posic¸a˜o
Me´todo da Falsa Posic¸a˜o – Implementac¸a˜o
1 int main() {
2
3 float raiz = falsaPosicao( 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
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ Outra alternativa para encontrar a raiz r da equac¸a˜o
f(x) = 0,
onde f e´ uma func¸a˜o cont´ınua no intervalo [a, b] em que a raiz e´
procurada, e´ re-escrever f(x) na forma
x = φ(x)
◮ A soluc¸a˜o de x = φ(x) e´ chamada de ponto fixo de φ
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ A ideia e´ que a soluc¸a˜o r do problema original, ou seja, r e´ soluc¸a˜o se
f(r) = 0,
tambe´m satisfac¸a a equac¸a˜o associada, ou seja,
r = φ(r)
e que na˜o sejam introduzidas ra´ızes estranhas a` func¸a˜ooriginal
f(x) = 0
◮ Nota-se que o zero de f(x) e´ o ponto de intersec¸a˜o entre φ(x) e a
reta x
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ No Me´todo do Ponto Fixo
◮ Define-se x = φ(x)
◮ Algumas condic¸o˜es devem ser respeitadas
◮ Dada uma aproximac¸a˜o inicial x0 para a raiz r, enta˜o as aproximac¸o˜es
sucessivas xk sa˜o obtidas fazendo
xk = φ(xk−1), k = 1, 2, . . .
◮ O processo continua ate´ o crite´rio de parada ser atendido
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo da Falsa Posic¸a˜o
Entrada: Aproximac¸a˜o inicial x0, func¸a˜o associada φ(x), precisa˜o ǫ e
ma´ximo nu´mero de iterac¸o˜es
1 inicio
2 k ←− 1;
3 enquanto crite´rio de parada na˜o e´ satisfeito fac¸a
4 xk ←− φ(xk−1);
5 k ←− k + 1;
6 retorna xk
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Exemplo
◮ Exemplo 2
Determine equac¸o˜es associadas candidatas para a equac¸a˜o
f(x) = x2 − x− 2 = 0.
◮ Soluc¸a˜o:
◮ x = x2 − 2
◮ x =
√
2 + x
◮ x = 1 + 2
x
◮ Existem diversas formas de expressar f(x) = 0 como um problema de
ponto fixo x = φ(x)
◮ Entretanto, nem todas sa˜o adequadas
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Exemplo
◮ Exemplo 3
Determine uma aproximac¸a˜o para a raiz de f(x) = x2 − x− 2 = 0
utilizando o Me´todo do Ponto Fixo com x = φ(x) =
√
2 + x e
x0 = 2,5. Adote |xk − xk−1| ≤ ǫ = 3× 10−2 como crite´rio de parada.
◮ Soluc¸a˜o:
x3 = 2,007512
◮ Nota-se que o me´todo esta´ convergindo para a raiz r = 2
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Exemplo
◮ Exemplo 4
Determine uma aproximac¸a˜o para a raiz de f(x) = x2 − x− 2 = 0
utilizando o Me´todo do Ponto Fixo com x = φ(x) = x2 − 2 e
x0 = 2,5. Execute 3 passos do me´todo.
◮ Soluc¸a˜o:
x3 = 256,003906
◮ Neste caso, nota-se que o me´todo esta´ divergindo
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ Analisando graficamente o processo
◮ x0 foi alterado para simplificar a ilustrac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ Analisando graficamente o processo
◮ x0 foi alterado para simplificar a ilustrac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ Analisando graficamente o processo
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Ana´lise
◮ E´ importante definir as condic¸o˜es suficientes que a func¸a˜o de iterac¸a˜o
φ(x) deve satisfazer para que o me´todo convirja
◮ Teorema (TVM – Teorema do Valor Me´dio)
Se f e´ cont´ınua em [a, b] e diferencia´vel em (a, b), enta˜o existe pelo
menos um ponto t em [a, b], tal que
f ′(t) =
f(b)− f(a)
b− a ⇒ f(b)− f(a) = f
′(t)(b− a)
◮ Teorema
Seja f uma func¸a˜o real cont´ınua na vizinhanc¸a de x0. Se f(x0) 6= 0,
enta˜o f(x) 6= 0 para todo x numa vizinhanc¸a (pequena) de x0.
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Ana´lise
◮ Teorema (Ponto Fixo)
Seja φ(x) uma func¸a˜o cont´ınua e com derivada primeira cont´ınua
num intervalo fechado I = (r − h, r + h), cujo centro r e´ a soluc¸a˜o
de x = φ(x). Ale´m disso, sejam x0 ∈ I e M um limitante
|φ′(x)| ≤M < 1, ∀x ∈ I. Enta˜o,
1. a iterac¸a˜o xk = φ(xk−1), k = 1, 2, . . . pode ser executada
indefinidamente, pois xk ∈ I, ∀k
2. |xk − r| → 0 quando k →∞
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Ana´lise
◮ Demonstrac¸a˜o: (a)
◮ Por induc¸a˜o matema´tica
◮ Assumindo por hipo´tese x0 ∈ I e supondo que x1, x2, . . . , xk−1 ∈ I
◮ Sabe-se que
xk = φ(xk−1)
r = φ(r)
}
⇒ xk − r = φ(xk−1)− φ(r)
Pelo TVM
φ(xk−1)− φ(r) = φ′(tk−1)(xk−1 − r) = xk − r
onde tk−1 ∈ [xk−1, r]
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Ana´lise
◮ Aplicando mo´dulo, tem-se que
|xk − r| = |φ′(tk−1)(xk−1 − r)|
= |φ′(tk−1)| |xk−1 − r|
◮ Pela hipo´tese de induc¸a˜o xk−1 ∈ I, logo tk−1 ∈ I
◮ Sendo |φ′(x)| ≤M < 1, ∀x ∈ I, pela descric¸a˜o do teorema, enta˜o
|xk − r| ≤M |xk−1 − r| < |xk−1 − r|
◮ Portanto, xk ∈ I e, assim, a iterac¸a˜o xk = φ(xk−1), k = 1, 2, . . .
pode ser executada indefinidamente, pois xk ∈ I, ∀k
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Ana´lise
◮ Demonstrac¸a˜o: (b)
◮ Como resultado do item (a), tem-se que
|xk − r| ≤M |xk−1 − r| ≤M2|xk−2 − r| ≤ · · · ≤Mk|x0 − r|
◮ Como M < 1, no limite
lim
k→∞
Mk → 0⇒ |xk − r| → 0
◮ Ou seja, a sequeˆncia converge para a raiz da equac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo
◮ E´ importante observar que
◮ Se |φ′(x)| < 1, enta˜o existe um intervalo I ⊂ [a, b] centrado em r que
satisfaz as condic¸o˜es do teorema e o me´todo convergira´
◮ Se |φ′(x)| > 1, enta˜o o processo divergira´
◮ Nada pode ser dito se |φ′(x)| = 1
◮ Quanto menor for M , mais ra´pido a sequeˆncia converge para a soluc¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Exemplo
◮ Exemplo 5
Deseja-se encontrar o raiz de f(x) = x2 − x− 2 = 0. O Me´todo do
Ponto Fixo e´ convergente ao adotar x = φ(x) =
√
x+ 2 e
considerando I = [1,5; 2,5]?
◮ Soluc¸a˜o:
Sim, pois φ(x) =
√
x+ 2 e φ′(x) = 1
2
√
x+2
sa˜o cont´ınuas no intervalo
[1,5; 2,5], e max
x∈I
|φ′(x)| = 1
2
√
1,5 + 2
= 0.267261 < 1.
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Exemplo
◮ Exemplo 6
Deseja-se encontrar o raiz de f(x) = x2 − x− 2 = 0. O Me´todo do
Ponto Fixo e´ converge ao adotar x = φ(x) = x2 − 2 e considerando
I = [1,5; 2,5]?
◮ Soluc¸a˜o:
Na˜o, pois φ(x) = x2 − 2⇒ φ′(x) = 2x e, assim,
max
x∈I
|φ′(x)| = 2× 2,5 = 5 > 1.
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Ordem de Convergeˆncia
◮ Durante a demonstrac¸a˜o do item (a) do Teorema do Ponto Fixo,
observou-se que
|xk − r| ≤M |xk−1 − r|, com M < 1
◮ Logo, pela definic¸a˜o de ordem de convergeˆncia, p = 1 e a
convergeˆncia e´ linear
◮ E´ importante destacar que
|xk − r|
|xk−1 − r| ≤M
ou seja, a relac¸a˜o entre os erros de duas iterac¸o˜es e´ proporcional a
φ′(tk−1)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Implementac¸a˜o
1 #include <stdio.h>
2 #include <math.h>
3
4 /* Funcao f(x) */
5 float f(float x) {
6 return x*x - x - 2;
7 }
8
9 /* Equacao associada para o metodo do ponto fixo */
10 float phi(float x) {
11 return sqrt( 2 + x );
12 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Implementac¸a˜o
1 float pontoFixo( float x0, int maxIt, float tol ) {
2
3 int k = 0; // passo
4 float fXk; // valores de avaliacao da funcao
5 float xk; // aproximacao da raiz
6 float xkm1; // aproximacao no passo k-1
7
8 xk = x0;
9 fXk = f( xk ); //o calculo de f(x) nao e necessario
10 do {
11 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
12 xkm1 = xk;
13 xk = phi( xkm1 );
14 fXk = f( xk );
15 k++;
16 } while ( fabs( ( xk - xkm1 )/xk ) > tol && k < maxIt );
17 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
18 return xk;
19 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo do Ponto Fixo
Me´todo do Ponto Fixo – Implementac¸a˜o
1 int main() {
2
3 float raiz = pontoFixo( 2.5, 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
◮ Me´tododa Falsa Posic¸a˜o
◮ Similar ao Me´todo da Bissec¸a˜o
◮ xk =
af(b)−bf(a)
f(b)−f(a)
◮ Me´todo do Ponto Fixo
◮ Determinar a equac¸a˜o associada x = φ(x)
◮ Resolve-se o problema original resolvendo o problema do ponto fixo
◮ φ(x) e φ′(x) cont´ınuas para x ∈ I
◮ |φ′(x)| < 1, ∀x ∈ I
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Método da Falsa Posição
	Método do Ponto Fixo
	Revisão