05_Método do ponto-fixo

Prévia do material em texto

Me´todo do ponto fixo
ufca
Me´todo do Ponto Fixo
Considere a func¸a˜o a seguir:
f(x) = x− 1 +√2 cosx, x ∈ [a, b]
Se p e´ uma raiz de f , enta˜o por definic¸a˜o f(p) = 0
Enta˜o, se definirmos uma func¸a˜o g : [a, b]→ R como
g(x) = 1−
√
2 cosx
Teremos
g(p) = p
Dizemos que p e´ um ponto fixo de g
Portanto, obter um zero para f sera´ equivalente a obter um
ponto fixo para g
Me´todo do Ponto Fixo
Enta˜o, para o nosso exemplo temos que
g(x) = x ⇐⇒ x = 1−
√
2 cosx, x ∈ [a, b]
Portanto, p e´ ponto fixo de g se este e´ um ponto de intersec¸a˜o
entre a curva (x, g(x)) e a reta y = x
Me´todo do Ponto Fixo
f(x) = x− 1 +
√
2 cosx, x ∈ [−4, 4]
g(x) = 1−
√
2 cosx
Me´todo do Ponto Fixo
f(x) = x− 1 +
√
2 cosx, x ∈ [−4, 4]
g(x) = 1−
√
2 cosx
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Lema. Se g : [a, b] ⊂ R→ [a, b] e´ cont´ınua, enta˜o a func¸a˜o g
possui ao menos um ponto fixo em [a, b]
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Lema. Se g : [a, b] ⊂ R→ [a, b] e´ cont´ınua, enta˜o a func¸a˜o g
possui ao menos um ponto fixo em [a, b]
Demonstrac¸a˜o.
Considere a func¸a˜o f : [a, b]→ R definida por f(x) = g(x)− x
Certamente, f e´ cont´ınua. Suponha que o ponto fixo na˜o e´ a nem b
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Lema. Se g : [a, b] ⊂ R→ [a, b] e´ cont´ınua, enta˜o a func¸a˜o g
possui ao menos um ponto fixo em [a, b]
Demonstrac¸a˜o.
Considere a func¸a˜o f : [a, b]→ R definida por f(x) = g(x)− x
Certamente, f e´ cont´ınua. Suponha que o ponto fixo na˜o e´ a nem b
Sendo assim g(a) > a =⇒ f(a) > 0 e g(b) < b =⇒ f(b) < 0
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Lema. Se g : [a, b] ⊂ R→ [a, b] e´ cont´ınua, enta˜o a func¸a˜o g
possui ao menos um ponto fixo em [a, b]
Demonstrac¸a˜o.
Considere a func¸a˜o f : [a, b]→ R definida por f(x) = g(x)− x
Certamente, f e´ cont´ınua. Suponha que o ponto fixo na˜o e´ a nem b
Sendo assim g(a) > a =⇒ f(a) > 0 e g(b) < b =⇒ f(b) < 0
Pelo Teorema do Valor Intermedia´rio, existe p ∈ (a, b) tal que f(p) = 0
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Lema. Se g : [a, b] ⊂ R→ [a, b] e´ cont´ınua, enta˜o a func¸a˜o g
possui ao menos um ponto fixo em [a, b]
Demonstrac¸a˜o.
Considere a func¸a˜o f : [a, b]→ R definida por f(x) = g(x)− x
Certamente, f e´ cont´ınua. Suponha que o ponto fixo na˜o e´ a nem b
Sendo assim g(a) > a =⇒ f(a) > 0 e g(b) < b =⇒ f(b) < 0
Pelo Teorema do Valor Intermedia´rio, existe p ∈ (a, b) tal que f(p) = 0
Mas este p e´ um ponto fixo de g, pois
f(p) = 0 ⇐⇒ 0 = g(p)− p =⇒ g(p) = p
Logo, existe ao menos um ponto fixo para g
Existeˆncia
Um ponto fixo de uma func¸a˜o g : [a, b]→ R e´ um ponto
p ∈ [a, b] tal que g(p) = p
Lema. Se g : [a, b] ⊂ R→ [a, b] e´ cont´ınua, enta˜o a func¸a˜o g
possui ao menos um ponto fixo em [a, b]
Unicidade
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b]. Se
existir uma constante c tal que |g′(x)| ≤ c < 1, para todo
x ∈ [a, b], enta˜o g possui um u´nico ponto fixo em [a, b]
Unicidade
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b]. Se
existir uma constante c tal que |g′(x)| ≤ c < 1, para todo
x ∈ [a, b], enta˜o g possui um u´nico ponto fixo em [a, b]
Demonstrac¸a˜o.
Pelo teorema anterior, g possui ao menos um ponto fixo em [a, b]
Suponha que p 6= q sa˜o dois pontos fixos de g em [a, b] e que existe
c ∈ R tal que |g′(x)| ≤ c < 1, para todo x ∈ [a, b],
Pelo Teorema do Valor Me´dio, existe d ∈ [a, b] localizado entre p e q tal
que g(p)− g(q)
p− q = g
′(d) ⇐⇒ g(p)− g(q) = (p− q)g′(d)
Tomando o mo´dulo em ambos os lados
|g(p)− g(q)| = |(p− q)g′(d)| ≤ |p− q||g′(d)| ≤ c|p− q| < |p− q|
Como p e q sa˜o pontos fixos, temos tambe´m que
p− q = g(p)− g(q) ⇐⇒ |p− q| = |g(p)− g(q)| < |p− q| Contradic¸a˜o!
Exemplo 1
Mostre que g(x) = (x2 − 1)/3 possui um u´nico ponto fixo no
intervalo [−1, 1].
Escolha da func¸a˜o de iterac¸a˜o
Considere equac¸a˜o f(x) = x2 − x− 1 = 0
Escolha da func¸a˜o de iterac¸a˜o
Considere equac¸a˜o f(x) = x2 − x− 1 = 0
Neste caso, existem duas formas de definir g
ou
Escolha da func¸a˜o de iterac¸a˜o
Considere equac¸a˜o f(x) = x2 − x− 1 = 0
Neste caso, existem duas formas de definir g
ou
Escolha da func¸a˜o de iterac¸a˜o
g′(x) = 1
2
√
x+1
c ©
2
0
1
1
B
ro
o
k
s/
C
o
le
,
C
en
g
a
g
e
L
ea
rn
in
g
Escolha da func¸a˜o de iterac¸a˜o
g′(x) = 1
2
√
x+1
g′(x) = 1
2
√
x+1
< 1 ∀x > − 34
c ©
2
0
1
1
B
ro
o
k
s/
C
o
le
,
C
en
g
a
g
e
L
ea
rn
in
g
Escolha da func¸a˜o de iterac¸a˜o
g′(x) = − 1x2
c ©
2
0
1
1
B
ro
o
k
s/
C
o
le
,
C
en
g
a
g
e
L
ea
rn
in
g
Escolha da func¸a˜o de iterac¸a˜o
g′(x) = − 1x2
g′(x) < 0 ∀x ∈ R
c ©
2
0
1
1
B
ro
o
k
s/
C
o
le
,
C
en
g
a
g
e
L
ea
rn
in
g
Convergeˆncia
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b].
Suponha que existe uma constante 0 < c < 1 tal que
|g′(x)| ≤ c, para todo x ∈ [a, b].
Enta˜o, para qualquer valor inicial p0 ∈ [a, b], a sequeˆncia
definida por pn = g(pn−1), n ≥ 1, converge para um u´nico
ponto fixo p em [a, b]
Convergeˆncia
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b].
Suponha que existe uma constante 0 < c < 1 tal que
|g′(x)| ≤ c, para todo x ∈ [a, b].
Enta˜o, para qualquer valor inicial p0 ∈ [a, b], a sequeˆncia
definida por pn = g(pn−1), n ≥ 1, converge para um u´nico
ponto fixo p em [a, b]
Esboc¸o da demonstrac¸a˜o.
Convergeˆncia
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b].
Suponha que existe uma constante 0 < c < 1 tal que
|g′(x)| ≤ c, para todo x ∈ [a, b].
Enta˜o, para qualquer valor inicial p0 ∈ [a, b], a sequeˆncia
definida por pn = g(pn−1), n ≥ 1, converge para um u´nico
ponto fixo p em [a, b]
Esboc¸o da demonstrac¸a˜o.
Pelo Teorema do Valor Me´dio, existe p∗ entre pn−1 e p tal que
|pn − p| = |g(pn−1)− g(p)| ≤ |pn−1 − p||g′(p∗)|
≤ c|pn−1 − p|
≤ c (c|pn−2 − p|)
≤ c2 (c|pn−3 − p|)
...
≤ cn|p0 − p|
Convergeˆncia
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b].
Suponha que existe uma constante 0 < c < 1 tal que
|g′(x)| ≤ c, para todo x ∈ [a, b].
Enta˜o, para qualquer valor inicial p0 ∈ [a, b], a sequeˆncia
definida por pn = g(pn−1), n ≥ 1, converge para um u´nico
ponto fixo p em [a, b]
Esboc¸o da demonstrac¸a˜o.
Como 0 < c < 1, enta˜o
lim
n→∞ |pn − p| ≤ limn→∞ c
n|p0 − p| = 0
Convergeˆncia
Teorema. Seja g ∈ C1[a, b] e g(x) ∈ [a, b], ∀x ∈ [a, b].
Suponha que existe uma constante 0 < c < 1 tal que
|g′(x)| ≤ c, para todo x ∈ [a, b].
Enta˜o, para qualquer valor inicial p0 ∈ [a, b], a sequeˆncia
definida por pn = g(pn−1), n ≥ 1, converge para um u´nico
ponto fixo p em [a, b]
Esboc¸o da demonstrac¸a˜o.
Como 0 < c < 1, enta˜o
lim
n→∞ |pn − p| ≤ limn→∞ c
n|p0 − p| = 0
Logo, {pn}∞n=0 e´ convergente
Limitante do erro
Corola´rio. Sob as hipo´teses do teorema anterior, e´ poss´ıvel
mostrar que
|pn − p| ≤ cnmax{p0 − a, b− p0} (1)
|pn − p| ≤ c
n
1− c |p1 − p0| (2)
Ordem de convergeˆncia
Observe que:
lim
n→∞
|pn − p|
|pn−1 − p| = limn→∞
|g(pn−1)− g(p)|
|pn−1 − p|
= |g′(p)| ≤ c
Ordem de convergeˆncia
Observe que:
lim
n→∞
|pn − p|
|pn−1 − p| = limn→∞
|g(pn−1)− g(p)|
|pn−1 − p|
= |g′(p)| ≤ c
Logo, a ordem de convergeˆncia e´ linearOrdem de convergeˆncia
Observe que:
lim
n→∞
|pn − p|
|pn−1 − p| = limn→∞
|g(pn−1)− g(p)|
|pn−1 − p|
= |g′(p)| ≤ c
Logo, a ordem de convergeˆncia e´ linear
A convergeˆncia sera´ mais ra´pida quanto menor for
|g′(x)| ≤ c < 1
Geometria da convergeˆncia
c ©
2
0
1
1
B
ro
o
k
s/
C
o
le
,
C
en
g
a
g
e
L
ea
rn
in
g
Geometria da convergeˆncia
c ©
2
0
1
1
B
ro
o
k
s/
C
o
le
,
C
en
g
a
g
e
L
ea
rn
in
g
Algoritmo
function [ p , n i t e r ]= p o n t o f i x o ( g , p0 , t o l , nmax )
n i t e r = 0 ;
while %t
n i t e r = n i t e r + 1 ;
p = g ( p0 ) ;
e r r = t o l ∗max(1 , abs ( p ) ) ;
i f abs ( p − p0 ) < e r r | n i t e r > nmax then
break ;
end
p0 = p ;
end
i f n i t e r > nmax then
warning ( ’ ponto f i x o : Numero maximo de i t e r a c o e s a t i n g i d o . ’ ) ;
end
endfunction
Algoritmo
Resultado para g(x) =
√
x+ 1
−−>d e f f ( ’ y=g ( x ) ’ , ’ y=s q r t ( x + 1) ’ )
−−>[p , n i t e r ] = p o n t o f i x o ( g , 0 , 1e−2, 100)
i t e r p n p n+1 | p n+1−p n |
1 0.000000000 1.000000000 1.000000000
2 1.000000000 1.414213562 0.414213562
3 1.414213562 1.553773974 0.139560412
4 1.553773974 1.598053182 0.044279208
5 1.598053182 1.611847754 0.013794572
6 1.611847754 1.616121207 0.004273452
n i t e r =
6 .
p =
1.6161212
Algoritmo
Resultado para g(x) = 1x + 1
−−>d e f f ( ’ y=g ( x ) ’ , ’ y=1/x + 1 ’ )
−−>[p , n i t e r ] = p o n t o f i x o ( g , 1 , 1e−2, 100)
i t e r p n p n+1 | p n+1−p n |
1 1.000000000 2.000000000 1.000000000
2 2.000000000 1.500000000 0.500000000
3 1.500000000 1.666666667 0.166666667
4 1.666666667 1.600000000 0.066666667
5 1.600000000 1.625000000 0.025000000
6 1.625000000 1.615384615 0.009615385
n i t e r =
6 .
p =
1.6153846
	ECI0010 - Métodos Num. Aplicados à Eng. Civil - Zeros de funções não-lineares
	Método do Ponto Fixo
	Existência
	Unicidade
	Exemplo 1
	Escolha da função de iteração
	Convergência
	Limitante do erro
	Ordem de convergência
	Algoritmo