Método do Ponto Fixo-MPF

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 9 - Cap.2- 2.4.3 Me´todo do Ponto Fixo-MPF
Definic¸a˜o 2.2: Um nu´mero p e´ um ponto fixo de uma func¸a˜o
dada g se g(p) = p.
Equivaleˆncia entre o problema do ponto fixo e o de se
encontrar as ra´ızes
f (δ)⇔ φ(x) = x
Usando um artif´ıcio alge´brico pode-se transformar o problema
f (x) = 0 em x = φ(x).
Graficamente, uma raiz da equac¸a˜o x = φ(x) e´ a abscissa do
ponto de intersecc¸a˜o da reta y = x e da curva y = φ(x).
Vimos que para certas func¸o˜es de iterac¸a˜o φ(x) o processo
pode gerar uma sequeˆncia que na˜o converge para a raiz δ.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Dada uma equac¸a˜o f (x) = 0, existe mais de uma func¸a˜o
φ(x), tal que f (δ)⇔ φ(x) = x .
De acordo com os gra´ficos estudados na aula passada, vimos
que na˜o e´ qualquer escolha de func¸a˜o de iterac¸a˜o que garante
que o processo iterativo xk+1 = φ(xk) gere uma sequeˆncia que
convirja para a raiz δ.
Ex.1:Seja a equac¸a˜o f (x) = x2 + x − 6 = 0 vamos usar duas
func¸o˜es de iterac¸a˜o para demonstrar a convergeˆncia ou na˜o do
processo iterativo.
Sabemos que as ra´ızes desta equac¸a˜o sa˜o dadas por δ1 = −3 e
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Dada uma equac¸a˜o f (x) = 0, existe mais de uma func¸a˜o
φ(x), tal que f (δ)⇔ φ(x) = x .
De acordo com os gra´ficos estudados na aula passada, vimos
que na˜o e´ qualquer escolha de func¸a˜o de iterac¸a˜o que garante
que o processo iterativo xk+1 = φ(xk) gere uma sequeˆncia que
convirja para a raiz δ.
Ex.1:Seja a equac¸a˜o f (x) = x2 + x − 6 = 0 vamos usar duas
func¸o˜es de iterac¸a˜o para demonstrar a convergeˆncia ou na˜o do
processo iterativo.
Sabemos que as ra´ızes desta equac¸a˜o sa˜o dadas por δ1 = −3 e
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ1(x) = 6− x2,
escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando a equac¸a˜o
de iterac¸a˜o temos:
xi+1 φ(xi ) 6− x2i =
x1 φ(x0) 6− (1.5)2 3.75
x2 φ(x1) 6− (3.75)2 −8.0625
x3 φ(x2) 6− (−8.0625)2 −59.003906
x4 φ(x3) 6− (−59.003906)2 −3475.4609
x5 φ(x4) 6− (−3475.4609)2 −1.2078822467428811 ∗ 107
Podemos ver que xi na˜o parece estar convergindo para a raiz
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ1(x) = 6− x2,
escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando a equac¸a˜o
de iterac¸a˜o temos:
xi+1 φ(xi ) 6− x2i =
x1 φ(x0) 6− (1.5)2 3.75
x2 φ(x1) 6− (3.75)2 −8.0625
x3 φ(x2) 6− (−8.0625)2 −59.003906
x4 φ(x3) 6− (−59.003906)2 −3475.4609
x5 φ(x4) 6− (−3475.4609)2 −1.2078822467428811 ∗ 107
Podemos ver que xi na˜o parece estar convergindo para a raiz
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ1(x) = 6− x2,
escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando a equac¸a˜o
de iterac¸a˜o temos:
xi+1 φ(xi ) 6− x2i =
x1 φ(x0) 6− (1.5)2 3.75
x2 φ(x1) 6− (3.75)2 −8.0625
x3 φ(x2) 6− (−8.0625)2 −59.003906
x4 φ(x3) 6− (−59.003906)2 −3475.4609
x5 φ(x4) 6− (−3475.4609)2 −1.2078822467428811 ∗ 107
Podemos ver que xi na˜o parece estar convergindo para a raiz
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ1(x) = 6− x2,
escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando a equac¸a˜o
de iterac¸a˜o temos:
xi+1 φ(xi ) 6− x2i =
x1 φ(x0) 6− (1.5)2 3.75
x2 φ(x1) 6− (3.75)2 −8.0625
x3 φ(x2) 6− (−8.0625)2 −59.003906
x4 φ(x3) 6− (−59.003906)2 −3475.4609
x5 φ(x4) 6− (−3475.4609)2 −1.2078822467428811 ∗ 107
Podemos ver que xi na˜o parece estar convergindo para a raiz
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ1(x) = 6− x2,
escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando a equac¸a˜o
de iterac¸a˜o temos:
xi+1 φ(xi ) 6− x2i =
x1 φ(x0) 6− (1.5)2 3.75
x2 φ(x1) 6− (3.75)2 −8.0625
x3 φ(x2) 6− (−8.0625)2 −59.003906
x4 φ(x3) 6− (−59.003906)2 −3475.4609
x5 φ(x4) 6− (−3475.4609)2 −1.2078822467428811 ∗ 107
Podemos ver que xi na˜o parece estar convergindo para a raiz
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ1(x) = 6− x2,
escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando a equac¸a˜o
de iterac¸a˜o temos:
xi+1 φ(xi ) 6− x2i =
x1 φ(x0) 6− (1.5)2 3.75
x2 φ(x1) 6− (3.75)2 −8.0625
x3 φ(x2) 6− (−8.0625)2 −59.003906
x4 φ(x3) 6− (−59.003906)2 −3475.4609
x5 φ(x4) 6− (−3475.4609)2 −1.2078822467428811 ∗ 107
Podemos ver que xi na˜o parece estar convergindo para a raiz
δ2 = 2.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x e
novamente escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando
a equac¸a˜o de iterac¸a˜o temos:
xi+1 φ(xi )
√
6− xi =
x1 φ(x0)
√
6− 1.5 2.12132
x2 φ(x1)
√
6− 2.12132 1.96944
x3 φ(x2)
√
6− 1.96944 2.00763
x4 φ(x3)
√
6− 2.00763 1.99809
x5 φ(x4)
√
6− 1.99809 2.0048
Podemos ver que xi esta´ convergindo para a raiz δ2 = 2!
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x e
novamente escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando
a equac¸a˜o de iterac¸a˜o temos:
xi+1 φ(xi )
√
6− xi =
x1 φ(x0)
√
6− 1.5 2.12132
x2 φ(x1)
√
6− 2.12132 1.96944
x3 φ(x2)
√
6− 1.96944 2.00763
x4 φ(x3)
√
6− 2.00763 1.99809
x5 φ(x4)
√
6− 1.99809 2.0048
Podemos ver que xi esta´ convergindo para a raiz δ2 = 2!
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x e
novamente escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando
a equac¸a˜o de iterac¸a˜o temos:
xi+1 φ(xi )
√
6− xi =
x1 φ(x0)
√
6− 1.5 2.12132
x2 φ(x1)
√
6− 2.12132 1.96944
x3 φ(x2)
√
6− 1.96944 2.00763
x4 φ(x3)
√
6− 2.00763 1.99809
x5 φ(x4)
√
6− 1.99809 2.0048
Podemos ver que xi esta´ convergindo para a raiz δ2 = 2!
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x e
novamente escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando
a equac¸a˜o de iterac¸a˜o temos:
xi+1 φ(xi )
√
6− xi =
x1 φ(x0)
√
6− 1.5 2.12132
x2 φ(x1)
√
6− 2.12132 1.96944
x3 φ(x2)
√
6− 1.96944 2.00763
x4 φ(x3)
√
6− 2.00763 1.99809
x5 φ(x4)
√
6− 1.99809 2.0048
Podemos ver que xi esta´ convergindo para a raiz δ2 = 2!
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x e
novamente escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando
a equac¸a˜o de iterac¸a˜o temos:
xi+1 φ(xi )
√
6− xi =
x1 φ(x0)
√
6− 1.5 2.12132
x2 φ(x1)
√
6− 2.12132 1.96944
x3 φ(x2)
√
6− 1.96944 2.00763
x4 φ(x3)
√
6− 2.00763 1.99809
x5 φ(x4)
√
6− 1.99809 2.0048
Podemos ver que xi esta´ convergindo para a raiz δ2 = 2!
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Seja a raiz δ2 = 2 e a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x e
novamente escolhemos como aproximac¸a˜o inicial x0 = 1.5 usando
a equac¸a˜o de iterac¸a˜o temos:
xi+1 φ(xi )
√
6− xi =
x1 φ(x0)
√
6− 1.5 2.12132
x2 φ(x1)
√
6− 2.12132 1.96944
x3 φ(x2)
√
6− 1.96944 2.00763
x4 φ(x3)
√
6− 2.00763 1.99809
x5 φ(x4)
√
6− 1.99809 2.0048
Podemos ver que xi esta´ convergindo para a raiz δ2 = 2!
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
2.4.3 Me´tododo Ponto Fixo-MPF - Estudo da
convergeˆncia
Teorema 2.2:
Seja φ(x) uma func¸a˜o cont´ınua e diferencia´vel num intervalo
I = [a, b] cujo centro e´ a raiz procurada δ. Seja x0 ∈ I uma
aproximac¸a˜o inicial para a raiz. Se |φ′(x)| ≤ M < 1 enta˜o a
sequeˆncia xk gerada pelo processo iterativo xk+1 = φ(xk) pertence
a I e converge para a raiz procurada δ.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Voltemos ao exemplo anterior: f (x) = x2 + x − 6 = 0 com
x0 = 1.5 para as func¸o˜es φ1(x) = 6− x2 e φ4(x) =
√
6− x .
Quando φ1(x) = 6− x2 temos que φ′1(x) = −2x , ambas
func¸o˜es cont´ınuas em <.
|φ′1(x)| < 1⇔ |2x | < 1⇔ −
1
2
< x <
1
2
.
Logo, neste caso na˜o existe um intervalo I centrado em
δ2 = 2 tal que |φ′(x)| < 1 ∀x ∈ I . Portanto φ1(x) = 6− x2
na˜o atende a`s exigeˆncias do teorema 2.2 e como vimos gerou
uma sequeˆncia de aproximac¸o˜es que na˜o converge para a raiz
procurada.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
Agora temos a func¸a˜o de iterac¸a˜o φ4(x) =
√
6− x com x0 = 1.5.
Quando φ4(x) =
√
6− x temos que φ′4(x) = −12√6−x .
1 φ4(x) =
√
6− x e´ uma func¸a˜o cont´ınua em
S = {x ∈ <|x ≤ 6}
2 φ′4(x) =
−1
2
√
6−x e´ uma func¸a˜o cont´ınua em
S ′ = {x ∈ <|x < 6}
|φ′4(x)| < 1⇔ |
−1
2
√
6− x | < 1⇒ x < 5.75.
Aqui vemos que e´ poss´ıvel obter um intervalo I centrado em
δ2 = 2 tal que |φ′(x)| < 1 ∀x ∈ I e nesse caso temos uma
sequeˆncia convergente de aproximac¸o˜es para a raiz procurada.
2.4.3 Me´todo do Ponto Fixo-MPF - Estudo da
convergeˆncia
No exemplo anterior como as ra´ızes eram conhecidas foi
poss´ıvel escolher um intervalo I centrado em δ2 = 2 tal que
em I as condic¸o˜es do teorema 2.2 sa˜o satisfeitas.
Pore´m, ao se aplicar o MPF na resoluc¸a˜o de uma equac¸a˜o
f (x) = 0, escolhe-se I “aproximadamente” centrado em δ.
Quanto melhor for o isolamento de δ maior precisa˜o teremos
na escolha de I .
2.4.3 Me´todo do Ponto Fixo-MPF-Algoritmo
Considere a equac¸a˜o f (x) = 0 e a equac¸a˜o equivalente x = φ(x).
Supor que as hipo´teses do teorema 2.2 esta˜o satisfeitas.
1 Dados iniciais: x0 e a precisa˜o �.
2 Se |f (x0)|) < �, enta˜o x¯ = x0 e´ a raiz procurada e o processo
terminou.
3 k = 1
4 x1 = φ(x0)
5 Se |f (x1)|) < � ou
|x1 − x0| < �
enta˜o x¯ = x1 e´ a raiz procurada e o processo terminou.
6 x0 = x1
7 k = k + 1 volte ao passo 4.
2.4.3 Me´todo do Ponto Fixo-MPF
Ex. Seja f (x) = x3 − 9x + 3 encontre a menor raiz positiva com
� = 5x10−4.
Da Fase 1 sabemos que as ra´ızes esta˜o em δ1 ∈ [−4,−3],
δ2 ∈ [0, 1] e δ3 ∈ [2, 3].
Tomemos x0 = 0.5 e � = 5x10
−4 = 0.0005.
Seja a func¸a˜o de iterac¸a˜o φ(x) = x
3
9 +
1
3 , pelo teorema 2.2
temos que φ′(x) = x
2
3 .
|φ′(x)| < 1⇒ x23 < 1⇔ −
√
3 < x <
√
3,
logo e´ poss´ıvel encontrar um intervalo I centrado na raiz tal
que |φ′(x)| < 1.
2.4.3 Me´todo do Ponto Fixo-MPF
Ex. Seja f (x) = x3 − 9x + 3 encontre a menor raiz positiva com
� = 5x10−4.
Da Fase 1 sabemos que as ra´ızes esta˜o em δ1 ∈ [−4,−3],
δ2 ∈ [0, 1] e δ3 ∈ [2, 3].
Tomemos x0 = 0.5 e � = 5x10
−4 = 0.0005.
Seja a func¸a˜o de iterac¸a˜o φ(x) = x
3
9 +
1
3 , pelo teorema 2.2
temos que φ′(x) = x
2
3 .
|φ′(x)| < 1⇒ x23 < 1⇔ −
√
3 < x <
√
3,
logo e´ poss´ıvel encontrar um intervalo I centrado na raiz tal
que |φ′(x)| < 1.
2.4.3 Me´todo do Ponto Fixo-MPF
i xi+1 = φ(xi ) f (xi+1)
1 0.347222 −0.8313799 ∗ 10−1
2 0.3379847 −0.3253222 ∗ 10−2
3 0.3376233 −0.1239777 ∗ 10−3
enta˜o x¯ = 0.3376233 e´ a raiz procurada pois
|f (x¯)| = 0.1239777 ∗ 10−3 < �.
2.4.3 Me´todo do Ponto Fixo-MPF
i xi+1 = φ(xi ) f (xi+1)
1 0.347222 −0.8313799 ∗ 10−1
2 0.3379847 −0.3253222 ∗ 10−2
3 0.3376233 −0.1239777 ∗ 10−3
enta˜o x¯ = 0.3376233 e´ a raiz procurada pois
|f (x¯)| = 0.1239777 ∗ 10−3 < �.
2.4.3 Me´todo do Ponto Fixo-MPF
i xi+1 = φ(xi ) f (xi+1)
1 0.347222 −0.8313799 ∗ 10−1
2 0.3379847 −0.3253222 ∗ 10−2
3 0.3376233 −0.1239777 ∗ 10−3
enta˜o x¯ = 0.3376233 e´ a raiz procurada pois
|f (x¯)| = 0.1239777 ∗ 10−3 < �.
2.4.3 Me´todo do Ponto Fixo-MPF
Exerc´ıcio: Seja a equac¸a˜o f (x) = 3x2 − ex encontre uma soluc¸a˜o
positiva desta equac¸a˜o com � = 10−5 usando o me´todo do ponto
fixo.
2.4.3 Me´todo do Ponto Fixo-Ordem de Convergeˆncia
Definic¸a˜o 2.3: Seja {xk} uma sequeˆncia que converge para um
nu´mero δ e seja ek = xk − δ o erro na iterac¸a˜o k.
Se existir um nu´mero p > 1 e uma constante C > 0, tais que
lim
k→∞
|ek+1|
|ek |p = C
enta˜o p e´ chamada de ordem de convergeˆncia da sequeˆncia {xk} e
C e´ a constante assinto´tica do erro.
Se lim
k→∞
ek+1
ek
= C , 0 ≤ |C | < 1, enta˜o a convergeˆncia e´ pelo
menos linear.
2.4.3 Me´todo do Ponto Fixo-Ordem de Convergeˆncia
Uma vez obtida a ordem de convergeˆncia p de um me´todo
iterativo, ela nos da´ uma informac¸ao sobre a rapidez de
convergeˆncia do processo, uma vez que podemos escrever a
seguinte relac¸a˜o:
|ek+1| ≈ C |ek |p para k→∞.
Considerando que a sequeˆncia {xk} e´ convergente, temos que
ek → 0 quando k →∞, portanto quanto maior for p, mais
pro´ximo de zero estara´ o valor C |ek |p.
O que garante uma convergeˆncia mais ra´pida da sequeˆncia
{xk}.
2.4.3 Me´todo do Ponto Fixo-Ordem de Convergeˆncia
Assim, se dois processos iterativos geram sequeˆncias {x1k} e
{x2k}, ambas convergentes para δ com ordem de convergeˆncia
p1 e p2 respectivamente, e se p1 > p2 ≥ 1, o processo que
gera a sequeˆncia {x1k} converge mais rapidamente que o outro.
O me´todo do ponto fixo MPF tem convergeˆncia apenas linear!
Pro´xima aula
Me´todo de Newton- Raphson
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.