aula08_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 Me´todo de Newton
3 Me´todo da Secante
4 Me´todo de Newton – Ra´ızes Mu´ltiplas
5 Comparac¸a˜o entre os Me´todos
6 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Me´todo da 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
Me´todo de Newton
Me´todo de Newton
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton
◮ O Me´todo de Newton pode ser derivado utilizando Polinoˆmios de
Taylor
◮ Uma aproximac¸a˜o polinomial para f(x) em torno do ponto xk−1 pode
ser definida como
f(x) = f(xk−1) + (x− xk−1)f ′(xk−1) +R1(x)
◮ Desprezando o termo do erro
f(x) ≈ f(xk−1) + (x− xk−1)f ′(xk−1)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton
f(x) ≈ f(xk−1) + (x− xk−1)f ′(xk−1)
◮ Avaliando na raiz r, onde sabe-se que f(r) = 0, enta˜o
f(r) = 0 ≈ f(xk−1) + (r − xk−1)f ′(xk−1)
(r − xk−1)f ′(xk−1) ≈ −f(xk−1)
r − xk−1 ≈ − f(xk−1)
f ′(xk−1)
com f ′(xk−1) 6= 0
r ≈ xk−1 − f(xk−1)
f ′(xk−1)
◮ Assim, o Me´todo de Newton pode ser definido como
xk = xk−1 − f(xk−1)
f ′(xk−1)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton
Entrada: f(x), f ′(x), valor inicial x0, 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 − f(xk−1)f ′(xk−1) ;
5 k ←− k + 1;
6 retorna xk
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Exemplo
◮ Exemplo 1
Determine a menor raiz positiva da equac¸a˜o f(x) = 4 cos(x)− ex = 0
utilizando o Me´todo de Newton e adotando
|xk−xk−1|
|xk|
< ǫ = 10−2
como crite´rio de parada.
◮ Soluc¸a˜o:
x f(x)
0 3
0,5 1,861609
1 −0,557072
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Exemplo
◮ Exemplo 1
Determine a menor raiz positiva da equac¸a˜o f(x) = 4 cos(x)− ex = 0
utilizando o Me´todo de Newton e adotando
|xk−xk−1|
|xk|
< ǫ = 10−2
como crite´rio de parada.
◮ Soluc¸a˜o:
0.0 0.5 1.0 1.5 2.0 2.5
x
−20
−15
−10
−5
0
5
y
f(x) = 4*cos( x ) - exp( x )
◮ Adotando x0 = 1 enta˜o x2 = 0,905 e´ uma aproximac¸a˜o para a raiz
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton
◮ O Me´todo de Newton tambe´m pode ser deduzido utilizando
◮ Me´todo do Ponto Fixo
◮ Geometricamente
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Me´todo do Ponto Fixo
◮ A equac¸a˜o f(x) = 0 pode ser expressa na forma
x = φ(x)
ou de forma geral
φ(x) = x+A(x)f(x)
para qualquer A(x) tal que A(r) 6= 0
◮ Verificou-se que
◮ O me´todo convergira´ se φ(x) e φ′(x) forem cont´ınuas e se |φ′(x)| < 1,
∀x ∈ I
◮ Quanto menor |φ′(r)|, mais ra´pida sera´ a convergeˆncia
◮ Quando visto como um Me´todo de Ponto Fixo, a ideia do Me´todo de
Newton e´ garantir e acelerar a convergeˆncia
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Me´todo do Ponto Fixo
◮ Para isso, φ(x) e´ escolhido de modo que φ′(r) = 0
◮ Derivando a forma geral de φ(x), enta˜o
φ(x) = x+A(x)f(x)⇒ φ′(x) = 1 +A′(x)f(x) +A(x)f ′(x)
◮ Avaliando em x = r, tem-se que
φ′(r) = 1 +A′(r) f(r)︸︷︷︸
=0
+A(r)f ′(r)⇒ φ′(r) = 1 +A(r)f ′(r)
◮ Como deseja-se que φ′(r) = 0, enta˜o
0 = 1 +A(r)f ′(r)⇒ A(r)f ′(r) = −1⇒ A(r) = − 1
f ′(r)
com f ′(r) 6= 0
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Me´todo do Ponto Fixo
◮ Assim, definindo
A(x) = − 1
f ′(x)
e dado que
φ(x) = x+A(x)f(x)
enta˜o
φ(x) = x− f(x)
f ′(x)
◮ O Me´todo de Newton pode enta˜o ser definido como
xk = xk−1 − f(xk−1)
f ′(xk−1)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Geometricamente
◮ Seja xk−1 uma aproximac¸a˜o para a raiz r de f(x) = 0
◮ Trac¸a-se a reta tangente a` curva f(x) no ponto (xk−1, f(xk−1))
◮ A aproximac¸a˜o xk e´ o ponto de intersec¸a˜o da reta tangente com o
eixo x
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Geometricamente
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Geometricamente
◮ Ou seja,
tan(θ) = f ′(xk−1) =
f(xk−1)
xk−1 − xk
f ′(xk−1)(xk−1 − xk) = f(xk−1)
xk−1 − xk = f(xk−1)
f ′(xk−1)
xk − xk−1 = − f(xk−1)
f ′(xk−1)
xk = xk−1 − f(xk−1)
f ′(xk−1)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Exemplo
◮ Exemplo 2
Determine uma aproximac¸a˜o para a raiz da equac¸a˜o
f(x) = x− 3√x− 2 = 0 utilizando o Me´todo de Newton. Adote
x0 = 3 e |xk − xk−1| < ǫ = 10−3 como crite´rio de parada.
◮ Soluc¸a˜o:
◮ x3 = 3,52137971
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Convergeˆncia
◮ Teorema
Sejam f(x), f ′(x) e f ′′(x) cont´ınuas em um intervalo I que conte´m a
raiz r da equac¸a˜o f(x) = 0. Assumindo que f ′(r) 6= 0 e seja o
intervalo I¯ ⊂ I tal que a raiz r ∈ I¯. Se x0 ∈ I¯ enta˜o a sequeˆncia
gerada pelo Me´todo de Newton convergira´ para a raiz.
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Convergeˆncia
◮ Demonstrac¸a˜o
◮ O Me´todo de Newton e´ um Me´todo de Ponto Fixo com
φ(x) = x− f(x)
f ′(x)
◮ Assim, a convergeˆncia do Me´todo de Newton e´ verificado se as
hipo´teses do Teorema do Ponto Fixo forem satisfeitas
1. Existe I¯ tal que φ(x) e φ′(x) sa˜o cont´ınuas em I¯
2. |φ′(x)| < 1, ∀x ∈ I¯
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Convergeˆncia
◮ Demonstrac¸a˜o – (1)
◮ Como
φ(x) = x− f(x)
f ′(x)
◮ enta˜o
φ′(x) = 1− f
′(x)f ′(x)− f(x)f ′′(x)
(f ′(x))2
φ′(x) = 1− 1 + f(x)f
′′(x)
(f ′(x))2
φ′(x) =
f(x)f ′′(x)
(f ′(x))2
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Convergeˆncia
◮ Demonstrac¸a˜o – (1)
◮ Tem-se que
φ(x) = x− f(x)
f ′(x)
⇒ φ′(x) = f(x)f
′′(x)
(f ′(x))2
◮ Pelas hipo´teses do teorema: f ′(r) 6= 0 e f ′(x) e´ cont´ınua em um
intervalo I que conte´m a raiz r
◮ Logo, existe um intervalo I1 ⊂ I em que f ′(x) 6= 0, ∀x ∈ I1
◮ Ale´m disso, tambe´m por hipo´tese do teorema, f(x), f ′(x) e f ′′(x)
sa˜o cont´ınuas em I e, por consequeˆncia, em I1
◮ Portanto, φ(x) e φ′(x) sa˜o cont´ınuas em I1
◮ Pela continuidade da soma e produto
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Convergeˆncia
◮ Demonstrac¸a˜o – (2)
◮ Observa-se que
φ′(x) =
f(x)f ′′(x)
(f ′(x))2
⇒ φ′(r) =
=0︷︸︸︷
f(r) f ′′(r)
(f ′(r))2
⇒ φ′(r) = 0
◮ Como |φ′(r)| = 0 < 1 e sendo φ′(x) cont´ınua em I1 enta˜o existe
I2 ⊂ I1 tal que |φ′(x)| < 1, ∀x ∈ I2
◮ Ale´m disso, I2 pode ser definido de modo que r esteja centrado nesse
intervalo
◮ Portanto, sendo I¯ = I2 enta˜o existe I¯ ⊂ I centrado em r no qual
φ(x) e φ′(x) sa˜o cont´ınuas e |φ′(x)| < 1, ∀x ∈ I¯
◮ Me´todo de Newton converge
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Ordem de Convergeˆncia
◮ Supondo as hipo´teses do teorema verdadeiras
◮ O Me´todo de Newton visto como o Me´todo de Ponto Fixo
xk = φ(xk−1)
r = φ(r)
}
⇒ xk − r = φ(xk−1)− φ(r)
◮ Sendo a aproximac¸a˜o de φ(xk−1) por Polinoˆmios de Taylor em torno
de r dadapor
φ(xk−1) = φ(r) + (xk−1 − r)φ′(r)︸ ︷︷ ︸
=0
+
(xk−1 − r)2
2
φ′′(tk−1)︸ ︷︷ ︸
R1(xk−1)
φ(xk−1) = φ(r) +
(xk−1 − r)2
2
φ′′(tk−1), tk−1 ∈ [r, xk−1]
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Ordem de Convergeˆncia
◮ Assim,
xk − r = φ(xk−1)− φ(r)
xk − r = φ(r) + (xk−1 − r)
2
2
φ′′(tk−1)− φ(r)
xk − r = (xk−1 − r)
2
2
φ′′(tk−1)
xk − r
(xk−1 − r)2 =
1
2
φ′′(tk−1)
◮ Logo,
|xk − r|
|xk−1 − r|2 =
∣∣∣∣12φ′′(tk−1)
∣∣∣∣ ≤ c
◮ Portanto, pela definic¸a˜o de convergeˆncia, p = 2 e o Me´todo de
Newton tem convergeˆncia quadra´tica
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton
◮ Observac¸a˜o
◮ O Me´todo de Newton requer o ca´lculo da func¸a˜o f(x) e de sua
derivada a cada passo
◮ Apesar da convergeˆncia quadra´tica, esses ca´lculos podem ser
computacionalmente muito caros
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Problemas
◮ Aproximac¸a˜o inicial ruim
◮ f ′(x0) = 0⇒ x1 = x0 − f(x0)f ′(x0) = x0 −
f(x0)
0
◮ O me´todo pode executar indefinidamente
◮ Por exemplo, se f(x) = x3 − 2x+ 2 e x0 = 0 enta˜o o me´todo gera a
sequeˆncia {1, 0, 1, 0, . . . }
◮ Nesses casos, pode-se utilizar um outro me´todo para obter uma
aproximac¸a˜o inicial adequada
◮ Derivada
◮ Descont´ınua
◮ Na˜o existe na raiz
◮ Na˜o pode ser definida
◮ Convergeˆncia na˜o quadra´tica
◮ Quando a raiz tem multiplicidade m > 1, ou seja, f ′(r) = 0
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Implementac¸a˜o
1 #include <stdio.h>
2 #include <math.h>
3
4 /* Funcao f(x) */
5 float f(float x) {
6 return 4*cos( x ) - exp(x);
7 }
8
9 /* Funcao df(x) */
10 float df(float x) {
11 return -4*sin( x ) - exp( x );
12 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Implementac¸a˜o
1 float newton( float x0, int maxIt, float tol ) {
2 int k = 0; // passo
3 float fXk; // valores de avaliacao da funcao
4 float xk; // aproximacao da raiz
5 float xkm1; // aproximacao no passo k-1
6 float fXkm1; // valores de avaliacao da funcao no passo k-1
7
8 xk = x0;
9 fXk = f( xk );
10 do {
11 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
12 xkm1 = xk;
13 fXkm1 = fXk;
14 xk = xkm1 - fXkm1 / df( xkm1 );
15 fXk = f( xk );
16 k++;
17 } while ( fabs( ( xk - xkm1 )/xk ) > tol && k < maxIt );
18 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
19 return xk;
20 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton
Me´todo de Newton – Implementac¸a˜o
1 int main() {
2
3 float raiz = newton( 1, 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 da Secante
Me´todo da Secante
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante
◮ Algumas desvantagens do Me´todo de Newton
◮ Determinar f ′(x)
◮ Calcular f ′(x) a cada passo
◮ Uma adaptac¸a˜o poss´ıvel e´ substituir f ′(x) pela aproximac¸a˜o
f ′(xk−1) ≈ f(xk−1)− f(xk−2)
xk−1 − xk−2
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante
◮ Assim,
xk = xk−1 − f(xk−1)
f ′(xk−1)
= xk−1 − f(xk−1)f(xk−1)−f(xk−2)
xk−1−xk−2
= xk−1 − f(xk−1)(xk−1 − xk−2)
f(xk−1)− f(xk−2)
=
xk−1(f(xk−1)− f(xk−2))− f(xk−1)(xk−1 − xk−2)
f(xk−1)− f(xk−2)
=
xk−1f(xk−1)− xk−1f(xk−2)− xk−1f(xk−1) + xk−2f(xk−1)
f(xk−1)− f(xk−2)
=
xk−2f(xk−1)− xk−1f(xk−2)
f(xk−1)− f(xk−2)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante
◮ O Me´todo da Secante adota o processo iterativo dado por
xk =
xk−2f(xk−1)− xk−1f(xk−2)
f(xk−1)− f(xk−2)
◮ Nota-se que
◮ xk e´ obtido considerando xk−1 e xk−2
◮ Duas aproximac¸o˜es iniciais sa˜o requeridas
◮ O me´todo e´ similar ao Me´todo da Falsa Posic¸a˜o
◮ intervalo [a, b] – Me´todo da Falsa Posic¸a˜o
◮ 2 aproximac¸o˜es – Me´todo da Secante
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante
Entrada: f(x), valores iniciais x0 e x1, precisa˜o ǫ e ma´ximo nu´mero de
iterac¸o˜es
1 inicio
2 k ←− 2;
3 enquanto crite´rio de parada na˜o e´ satisfeito fac¸a
4 xk ←− xk−2f(xk−1)−xk−1f(xk−2)f(xk−1)−f(xk−2) ;
5 k ←− k + 1;
6 retorna xk
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Exemplo
◮ Exemplo 3
Determine uma aproximac¸a˜o para a raiz da equac¸a˜o
f(x) =
√
x− 5e−x = 0 utilizando o Me´todo da Secante. Adote
x0 = 1,4, x1 = 1,5 e |xk − xk−1| < ǫ = 10−2 como crite´rio de parada.
◮ Soluc¸a˜o:
◮ x3 = 1,431
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante
◮ 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 p = 1+
√
5
2 ≈ 1,618
◮ Observac¸o˜es
◮ A ordem de convergeˆncia e´ menor do que a do Me´todo de Newton
◮ O Me´todo da Secante na˜o requer f ′(x)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante – Implementac¸a˜o
1 #include <stdio.h>
2 #include <math.h>
3
4 /* Funcao f(x) */
5 float f(float x) {
6 return sqrt( x ) - 5*exp(-x);
7 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante – Implementac¸a˜o
1 float secante( float x0, float x1, int maxIt, float tol ) {
2 int k = 1; // passo
3 float xk, xkm1, xkm2; // aproximacoes da raiz
4 float fXk, fXkm1, fXkm2; // valores das avaliacoes da funcao
5
6 xk = x1; fXk = f( xk );
7 xkm1 = x0; fXkm1 = f( xkm1 );
8 do {
9 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
10 xkm2 = xkm1; fXkm2 = fXkm1;
11 xkm1 = xk; fXkm1 = fXk;
12 xk = ( xkm2*fXkm1 - xkm1*fXkm2 )/( fXkm1 - fXkm2 );
13 fXk = f( xk );
14 k++;
15 } while ( fabs( ( xk - xkm1 )/xk ) > tol && k < maxIt );
16 printf("Passo: %i\tAproximacao: f( %f ) = %f.\n", k, xk, fXk);
17 return xk;
18 }
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo da Secante
Me´todo da Secante – Implementac¸a˜o
1 int main() {
2
3 float raiz = secante( 1.4, 1.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
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ O Me´todo de Newton pode na˜o convergir de forma quadra´tica
◮ Quando uma raiz tem multiplicidade m > 1, o Me´todo de Newton
apresenta uma convergeˆncia na˜o quadra´tica
◮ Para analisar esse caso, primeiro determina-se o Polinoˆmio de Taylor
em torno de da raiz r que aproxima f(x), ou seja
f(x) = Pn(x) +Rn(x) =
n∑
k=0
f (k)(r)
(x− r)k
k!
+ f (n+1)(t)
(x− r)n+1
(n+ 1)!
◮ Tomando o polinoˆmio aproximador de grau m− 1, enta˜o
f(x) =
m−1∑
k=0
f (k)(r)
(x− r)k
k!
+ f (m)(t)
(x− r)m
m!
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Quando uma raiz r tem multiplicidade m > 1, enta˜o
f(r) = f ′(r) = · · · = f (m−1)(r) = 0 e f (m)(r) 6= 0
◮ Logo,
f(x) =
m∑
k=0
f (k)(r)
(x− r)k
k!
+ f (m)(t)
(x− r)m
m!
= f(r)︸︷︷︸
=0
+(x− r) f ′(r)︸ ︷︷ ︸
=0
+ · · ·+ (x− r)
m−1
(m− 1)! f
(m−1)(r)︸ ︷︷ ︸
=0
+
(x− r)m
m!
f (m)(t)
=
(x− r)m
m!
f (m)(t) t ∈ [x, r]
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Aexpressa˜o
f(x) =
(x− r)m
m!
f (m)(t)
◮ pode ser redefinida como
f(x) = (x− r)mg(x) onde g(x) = f
(m)(t)
m!
, t ∈ [x, r], g(r) 6= 0
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Assim, tem-se que
f(x) = (x− r)mg(x)
f ′(x) = m(x− r)m−1g(x) + (x− r)mg′(x)
◮ e a func¸a˜o associada φ(x) do Me´todo de Newton visto como o
Me´todo de Ponto Fixo fica como
φ(x) = x− f(x)
f ′(x)
= x− (x− r)
mg(x)
m(x− r)m−1g(x) + (x− r)mg′(x)
= x− (x− r)
m−1(x− r)g(x)
(x− r)m−1 [mg(x) + (x− r)g′(x)]
= x− (x− r)g(x)
mg(x) + (x− r)g′(x)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Fazendo g(x) = g (por simplicidade), tem-se que
φ(x) = x− (x− r)g
mg + (x− r)g′
◮ e derivando obte´m-se
φ′(x) = 1− [g + (x− r)g
′] [mg + (x− r)g′]− [(x− r)g] [mg′ + g′ + (x− r)g′′]
[mg + (x− r)g′]2
◮ Avaliando em x = r
φ′(r) = 1− [g +
=0︷ ︸︸ ︷
(r − r)g′][mg +
=0︷ ︸︸ ︷
(r − r)g′]− [
=0︷ ︸︸ ︷
(r − r)g][mg′ + g′ +
=0︷ ︸︸ ︷
(r − r)g′′]
[mg + (r − r)g′︸ ︷︷ ︸
=0
]2
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Assim,
φ′(r) = 1− [g(r)][mg(r)]
[mg(r)]2
= 1− mg
2(r)
m2g2(r)
= 1− 1
m
=
m− 1
m
◮ Logo, como m > 1 tem-se que φ′(r) = m−1
m
6= 0 e o me´todo na˜o
mais apresenta convergeˆncia quadra´tica
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Uma adaptac¸a˜o do Me´todo de Newton permite calcular uma raiz de
multiplicidade m, mantendo a convergeˆncia quadra´tica
◮ Proposta por Schro¨der
◮ Verificou-se que
f(x) =
(x− r)m
m!
f (m)(t)
◮ Aproximando f (m)(t) por uma contante c, enta˜o
f(x) ≈ (x− r)
mc
m!
⇒ f ′(x) ≈ m(x− r)
m−1c
m!
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Logo,
f(x)
f ′(x)
=
(x−r)mc
m!
m(x−r)m−1c
m!
=
(x− r)mc
m!
m!
m(x− r)m−1c
=
(x− r)
m
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Portanto,
f(x)
f ′(x)
=
(x− r)
m
f(x)
f ′(x)
m = x− r
r = x−m f(x)
f ′(x)
◮ E o Me´todo de Newton modificado fica como
xk = xk−1 −m f(xk−1)
f ′(xk−1)
◮ Uma desvantagem desse me´todo e´ a requisic¸a˜o da multiplicidade m
da raiz que se esta´ aproximando
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
Entrada: f(x), f ′(x), valor inicial x0, precisa˜o ǫ, ma´ximo nu´mero de
iterac¸o˜es e multiplicidade m da raiz
1 inicio
2 k ←− 1;
3 enquanto crite´rio de parada na˜o e´ satisfeito fac¸a
4 xk = xk−1 −m f(xk−1)f ′(xk−1) ;
5 k ←− k + 1;
6 retorna xk
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Uma alternativa para o caso de raiz mu´ltipla e´ adotar
u(x) =
f(x)
f ′(x)
◮ Sabendo que, para g(r) 6= 0, tem-se que
f(x) = (x− r)mg(x)
f ′(x) = m(x− r)m−1g(x) + (x− r)mg′(x)
◮ Logo,
u(x) =
(x− r)mg(x)
m(x− r)m−1g(x) + (x− r)mg′(x)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Logo,
u(x) =
(x− r)mg(x)
m(x− r)m−1g(x) + (x− r)mg′(x)
=
(x− r)mg(x)
(x− r)m−1 [mg(x) + (x− r)g′(x)]
=
(x− r)g(x)
[mg(x) + (x− r)g′(x)]
◮ Assim, na˜o e´ dif´ıcil perceber que r e´ raiz da equac¸a˜o u(x) = 0 com
multiplicidade 1
◮ Portanto, o Me´todo de Newton pode aplicado a u(x)
◮ a soluc¸a˜o encontrada e´ raiz da equac¸a˜o original f(x) = 0
◮ convergeˆncia quadra´tica
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
◮ Tendo que
u(x) =
f(x)
f ′(x)
⇒ u′(x) = f
′(x)f ′(x)− f(x)f ′′(x)
[f ′(x)]2
⇒ u′(x) = [f
′(x)]2 − f(x)f ′′(x)
[f ′(x)]2
◮ enta˜o
xk = xk−1 − u(xk−1)
u′(xk−1)
= xk−1 −
f(xk−1)
f ′(xk−1)
[f ′(xk−1)]
2−f(xk−1)f ′′(xk−1)
[f ′(xk−1)]
2
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
xk = xk−1 −
f(xk−1)
f ′(xk−1)
[f ′(xk−1)]
2−f(xk−1)f ′′(xk−1)
[f ′(xk−1)]
2
= xk−1 − f(xk−1)
f ′(xk−1)
[f ′(xk−1)]
2
[f ′(xk−1)]
2 − f(xk−1)f ′′(xk−1)
= xk−1 − f(xk−1)f
′(xk−1)
[f ′(xk−1)]
2 − f(xk−1)f ′′(xk−1)
◮ E o Me´todo de Newton modificado fica como
xk = xk−1 − f(xk−1)f
′(xk−1)
[f ′(xk−1)]
2 − f(xk−1)f ′′(xk−1)
◮ Neste caso, f ′′(x) tambe´m e´ requerida no processo
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Newton – Ra´ızes Mu´ltiplas
Me´todo de Newton – Ra´ızes Mu´ltiplas
Entrada: f(x), f ′(x), f ′′(x), valor inicial x0, 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 − f(xk−1)f
′(xk−1)
[f ′(xk−1)]
2−f(xk−1)f ′′(xk−1)
;
5 k ←− k + 1;
6 retorna xk
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Comparac¸a˜o entre os Me´todos
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Comparac¸a˜o entre os Me´todos
◮ Me´todo da Bissec¸a˜o e Falsa Posic¸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
◮ Convergeˆncia linear
◮ Me´todo do Ponto Fixo
◮ Define-se uma func¸a˜o associada φ(x) de modo que φ(x) e φ′(x) sejam
cont´ınuas para x ∈ I e |φ′(x)| < 1, ∀x ∈ I
◮ Convergeˆncia linear
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Comparac¸a˜o entre os Me´todos
◮ Me´todo de Newton
◮ Possui crite´rios mais restritivos para a convergeˆncia
◮ Requer o ca´lculo de f(x) e f ′(x) a cada passo
◮ Convergeˆncia quadra´tica
◮ Convergeˆncia mais lenta quando r e´ raiz com multiplicidade m > 1
◮ Pode ser modificado de forma a manter a convergeˆncia quadra´tica
◮ Me´todo da Secante
◮ Similar ao Me´todo de Newton
◮ Ca´lculo de f ′(x) e´ substitu´ıdo por uma aproximac¸a˜o
◮ Convergeˆncia super-linear
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Comparac¸a˜o entre os Me´todos
◮ De forma geral, entre os me´todos apresentados aqui
◮ O Me´todo de Newton e´ o mais indicado
◮ Sempre que for poss´ıvel garantir as condic¸o˜es de convergeˆncia, e f ′(x)
estiver dispon´ıvel e for simples de ser avaliada
◮ Se f ′(x) na˜o estiver dispon´ıvel ou for computacionalmente custosa,
enta˜o sugere-se o Me´todo da Secante
◮ Pode-se utilizar os Me´todos da Bissec¸a˜o ou Falsa Posic¸a˜o quando se
deseja garantir a convergeˆncia ou para obter uma melhor aproximac¸a˜o
inicial para os demais me´todos
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Exemplo
◮ Exemplo 4
Determine a menor raiz positiva da equac¸a˜o f(x) = e−x
2 − cos(x)
adotando uma precisa˜o ǫ = 10−8.
◮ Soluc¸a˜o:
x f(x)
0 0,0 = 0
1,0 −0,172422864697 < 0
2,0 0,434462475436 > 0
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Exemplo
◮ Exemplo 4
Determine a menor raiz positiva da equac¸a˜o
f(x) = e−x
2 − cos(x) = 0 adotando uma precisa˜o ǫ = 10−8.
◮ Soluc¸a˜o:
Usando φ(x) = cos(x)− e−x2 + x quando necessa´rio e sendo
f ′(x) = sen(x)− 2xe−x2 .
Me´todo Dados Iterac¸o˜es
Bissec¸a˜o [1, 2] 27
Falsa Posic¸a˜o [1, 2] 12
Ponto Fixo x0 = 2 18
Newton x0 = 2 5
Secante x0 = 1 e x1 = 2 8
Heder S. Bernardino Ca´lculo Nume´rico
Comparac¸a˜o entre os Me´todos
Exemplo
◮ Exemplo 5
Considerandof(x) = (x− 5)3ex, adotando uma precisa˜o ǫ = 10−8, e
sendo
◮ f ′(x) = 3(x− 5)2ex + (x− 5)3ex e
◮ f ′′(x) = 6(x− 5)ex + 6(x− 5)2ex + (x− 5)3ex
enta˜o
Me´todo Dados Iterac¸o˜es
Newton x0 = 4 39
Secante x0 = 4 e x1 = 6 56
Newton Modificado com m = 3 x0 = 4 6
Newton Modificado usando f ′′(x) x0 = 4 6
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Me´todo de Newton
◮ Convergeˆncia quadra´tica
◮ Requer que f ′(xk−1) seja calculada a cada passo
xk = xk−1 − f(xk−1)
f ′(xk−1)
◮ Me´todo da Secante
◮ Convergeˆncia super-linear
◮ Requer 2 aproximac¸o˜es para determinar xk
xk =
xk−2f(xk−1)− xk−1f(xk−2)
f(xk−1)− f(xk−2)
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Me´todo de Newton para Ra´ızes Mu´ltiplas
xk = xk−1 −m f(xk−1)
f ′(xk−1)
xk = xk−1 − f(xk−1)f
′(xk−1)
[f ′(xk−1)]
2 − f(xk−1)f ′′(xk−1)
◮ Comparac¸a˜o entre os Me´todos
◮ Requisitos para convergeˆncia
◮ Ordem de convergeˆncia
◮ Exemplos
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Método de Newton
	Método da Secante
	Método de Newton – Raízes Múltiplas
	Comparação entre os Métodos
	Revisão