Método do Ponto Fixo para Equações Não Lineares

Prévia do material em texto

MAT 012 versa˜o 2018.1 Prof. Rodrigo Lima
Me´todo do Ponto Fixo
Na aula de hoje vamos desenvolver o Me´todo do Ponto Fixo e investigar como este
me´todo pode ser utilizado para resolver de forma aproximada equac¸o˜es na˜o lineares da forma
f(x) = 0.
Definic¸o˜es e Resultados
Seja g : D ⊂ R → R uma func¸a˜o cont´ınua em D. Dizemos que p ∈ D e´ um ponto fixo da
func¸a˜o g se g(p) = p. Ou seja, ao avaliarmos g(x) em p obtemos como resultado o pro´prio
nu´mero p. Geometricamente significa dizer que o gra´fico de g(x) intercepta a reta y = x
exatamente em x = p (veja a Figura 1).
x
y
y = x
g(x)
0 p
p
Figura 1: Ilustrac¸a˜o para o ponto fixo de uma func¸a˜o.
Exemplo 1:
Determine todos os pontos fixos da func¸a˜o g(x) = x2 − 2. (Fonte: Numerical Analysis - R.
Burden, J. D. Faires - 9a Edic¸a˜o - Editora Cengage Learning - pa´g. 56.)
Resoluc¸a˜o: Para encontrar os pontos fixos de g(x) basta que resolvamos a equac¸a˜o g(x) = x
na varia´vel x. Assim, obtemos g(x) = x ⇒ x2 − 2 = x ⇒ x2 − x− 2 = 0. Como a equac¸a˜o
resultante e´ do segundo grau, e´ fa´cil resolveˆ-la. Portanto, x = −1 e x = 2 sa˜o os valores
procurados. Nem sempre e´ fa´cil resolver a equac¸a˜o g(x) = x a` ma˜o para determinarmos
os pontos fixos da func¸a˜o g. Mais adiante veremos alguns exemplos onde na˜o e´ poss´ıvel
encontrar uma soluc¸a˜o anal´ıtica para g(x) = x.
1
O resultado a seguir mostra quais condic¸o˜es devem ser satisfeitas para que uma func¸a˜o
g(x) tenha um u´nico ponto fixo em seu domı´nio.
Teorema 1 (Existeˆncia e Unicidade): Seja g : [a, b]→ R uma func¸a˜o cont´ınua em [a, b].
Se g(x) ∈ [a, b] para todo x ∈ [a, b], enta˜o g possui pelo menos um ponto fixo em [a, b]. Se,
ale´m disso, existir uma constante α tal que |g′(x)| ≤ α < 1 para todo x ∈ (a, b), enta˜o g tem
um u´nico ponto fixo em [a, b].
Prova: Para provar que existe pelo menos um ponto fixo para g, dadas as hipo´teses, devemos
excluir os casos triviais g(a) = a ou g(b) = b pois, nestas situac¸o˜es, claramente g possui um
ponto fixo em [a, b]. Sendo assim, admitimos g(a) > a e g(b) < b. Considere a func¸a˜o
h(x) = g(x) − x. Como g(x) e´ cont´ınua em [a, b], h(x) tambe´m e´ cont´ınua em [a, b]. Ale´m
disso, h(a) = g(a)−a > 0 e h(b) = g(b)−b < 0. Logo, pelo Teorema do Valor Intermedia´rio,
existe x∗ ∈ [a, b] tal que h(x∗) = 0. Portanto, h(x∗) = g(x∗) − x∗ = 0 ⇒ g(x∗) = x∗, ou
seja, g(x∗) possui um ponto fixo em [a, b]. Para provar a unicidade supomos por absurdo que
existem dois pontos fixos x∗1 e x
∗
2 de g em [a, b]. Deste modo, pelo Teorema do Valor Me´dio,
existe c entre x∗1 e x
∗
2 tal que
|g′(c)| = |g(x
∗
2)− g(x∗1)|
|x∗2 − x∗1|
.
Como |g′(x)| ≤ α < 1 para todo x ∈ (a, b), chegamos a uma contradic¸a˜o, pois
|g(x∗2)− g(x∗1)|
|x∗2 − x∗1|
≤ α < 1⇒ |g(x∗2)− g(x∗1)| < |x∗2 − x∗1| ⇒ |x∗2 − x∗1| < |x∗2 − x∗1|.
Portanto, g possui um u´nico ponto fixo no intervalo [a, b].
Exemplo 2:
Mostre que a func¸a˜o g(x) = cos(x) possui um u´nico ponto fixo no intervalo [0, 1]. (Fonte:
Numerical Methods Using MATLAB - J. Mathews, K. Fink - 4a Edic¸a˜o - Editora Pearson -
pa´g. 44.)
Resoluc¸a˜o: Para resolver este exerc´ıcio precisamos mostrar que a func¸a˜o dada satisfaz todas
as hipo´teses do Teorema 1. De fato, g(x) = cos(x) e´ decrescente no intervalo [0, 1]. Como
g(0) = 1 e g(1) = cos(1), sua imagem e´ o intervalo [cos(1), 1] que esta´ contido em [0, 1]. De
acordo com o teorema, isso garante a existeˆncia de pelo menos um ponto fixo para g. Ale´m
disso,
|g′(x)| = | − sen(x)| = sen(x) < sen(1) = 0.841471 < 1 para todo x ∈ (0, 1).
Portanto, g(x) possui um u´nico ponto fixo em [0, 1]. Notemos que na˜o e´ poss´ıvel resolver a
equac¸a˜o g(x) = x a` ma˜o para determinar o ponto fixo neste exemplo.
2
Exemplo 3:
A func¸a˜o g(x) = 3−x possui um u´nico ponto fixo no intervalo [0, 1]. Por queˆ o Teorema 1
falha neste caso? (Fonte: Numerical Analysis - R. Burden, J. D. Faires - 9a Edic¸a˜o - Editora
Cengage Learning - pa´g. 59.)
Resoluc¸a˜o: A func¸a˜o g(x) e´ decrescente em [0, 1]. Como g(0) = 1 e g(1) = 1/3, sua imagem
e´ o intervalo [1/3, 1] que esta´ contido em [0, 1]. Isso garante a existeˆncia de pelo menos um
ponto fixo de g no intervalo [0, 1]. Por outro lado,
g′(x) = − ln(3)3−x e |g′(0)| = ln 3 = 1.09861 > 1,
ou seja, na˜o e´ verdade que |g′(x)| < 1 para todo x ∈ (0, 1). Por essa raza˜o, na˜o conseguimos
utilizar o teorema para garantir a unicidade do ponto fixo de g mesmo sabendo que ele e´
u´nico dentro do intervalo [0, 1] (veja a Figura 2). Isso significa que o Teorema 1 fornece
uma condic¸a˜o suficiente (mas na˜o necessa´ria) para que o ponto fixo da func¸a˜o g exista e seja
u´nico.
0.2 0.4 0.6 0.8 1.0
0.2
0.4
0.6
0.8
1.0
x
y
y = x
g(x) = 3−x
0
Figura 2: g(x) = 3−x na˜o satisfaz todas as hipo´teses do Teorema 1.
Nos exemplos 2 e 3 que acabamos de discutir na˜o conseguimos resolver as equac¸o˜es g(x) =
x analiticamente, ou seja, na˜o conseguimos obter a soluc¸a˜o dessas equac¸o˜es simplesmente
aplicando uma fo´rmula. Isso significa que para obtermos uma aproximac¸a˜o para o ponto fixo
da func¸a˜o g nestes exemplos, precisamos desenvolver um me´todo nume´rico para calcula´-lo de
forma iterativa. Veremos a seguir um procedimento que, sob determinadas condic¸o˜es, obte´m
uma aproximac¸a˜o razoa´vel para a soluc¸a˜o da equac¸a˜o g(x) = x.
3
Processo Iterativo do Ponto Fixo
O me´todo do ponto fixo e´ definido como o seguinte processo iterativo
xk+1 = g(xk), para k = 0, 1, 2, . . . (1)
onde g(x) e´ a func¸a˜o para o qual desejamos encontrar o ponto fixo x∗.
Vamos ilustrar graficamente o comportamento deste me´todo em alguns exemplos e inves-
tigar sob quais condic¸o˜es sua convergeˆncia esta´ garantida. Em quaisquer dos casos mostrados
nas Figuras 3 e 4, a interpretac¸a˜o gra´fica do processo (1) e´ bem simples: comec¸ando no ponto
(x0, 0) sobre o eixo x, movemos verticalmente para o ponto (x0, g(x0)) = (x0, x1) na curva
y = g(x). Em seguida, movemos horizontalmente de (x0, x1) para o ponto (x1, x1) na reta
y = x e repetimos este procedimento indefinidamente.
A Figura 3a) ilustra a evoluc¸a˜o do me´todo para a obtenc¸a˜o do ponto fixo da func¸a˜o
g(x) =
√
2x no intervalo [0, 2] partindo de x0 = 0.1. Neste caso, a sequeˆncia nume´rica (xk)k
gerada converge para o ponto fixo de g(x) (x∗ = 2) e podemos notar que o zigue-zague
formado pela poligonal que une os pontos se aproxima do ponto (2, 2). A Figura 3b) ilustra
um caso em que o me´todo gera uma sequeˆncia nume´rica (xk)k divergente para a func¸a˜o
g(x) = x
2
4
+ x
2
mesmo tomando como valor inicial um nu´mero pro´ximo do ponto fixo de g(x)
(x∗ = 2). Em ambos os casos as sequeˆncias nume´ricas obtidas sa˜o mono´tonas crescentes.
0.5 1.0 1.5 2.0
0.5
1.0
1.5
2.0
x
y y = x
g(x)
0
a) g(x) =
√
2x, x0 = 0.1
1 2 3 4
1
2
3
4
x
y y = xg(x)
0
b) g(x) =
x2
4
+
x
2
, x0 = 2.03
Figura 3: As sequeˆncias geradas pelo me´todo sa˜o crescentes.
As Figuras 4a) e 4b) ilustram exemplos em que o me´todo do ponto fixo gera sequeˆncias
nume´ricas oscilantes. Na Figura 4a) a sequeˆncia (xk)k converge para o ponto fixo (x
∗ = 2)
da func¸a˜o g(x) = 8
x+2
no intervalo [0, 4] partindo de x0 = 4 e, na Figura 4b), utilizando
g(x) = −x2
4
− x
2
+ 4, a sequeˆncia se afasta do ponto fixo (x∗ = 2) mesmo tomando como
chute inicial um valor pro´ximo (x0 = 1.9). Os exemplos que ilustram essa sec¸a˜o foram
4
1 2 3 4
1
2
3
4
x
y y = x
g(x)
0
a) g(x) =
8
x+ 2
, x0 = 4
1 2 3 4
1
2
3
4
x
y y = x
g(x)
0
b) g(x) = −x
2
4
− x
2
+ 4, x0 = 1.9
Figura 4: As sequeˆncias geradas pelo me´todo sa˜o oscilantes.
retirados do enderec¸o http://mathfaculty.fullerton.edu/mathews/a2001/Animations/
RootFinding/FixedPoint/FixedPoint.html
Propriedades do Me´todoComo vimos nos exemplos anteriores, o me´todo do ponto fixo pode falhar dependendo do
valor inicial x0 escolhido para dar in´ıcio as iterac¸o˜es. O resultado a seguir diz sobre o
comportamento da sequeˆncia nume´rica gerada pelo me´todo.
Teorema 2: Seja g uma func¸a˜o cont´ınua e suponha que (xk)k e´ a sequeˆncia gerada pelo
processo iterativo (1). Se (xk)k e´ convergente, isto e´,
lim
k→∞
xk = x
∗,
enta˜o x∗ e´ ponto fixo da func¸a˜o g.
Prova: Basta mostrarmos que g(x∗) = x∗ usando o fato de que g(x) e´ cont´ınua e
lim
k→∞
xk = lim
k→∞
xk+1 = x
∗.
Assim, podemos escrever,
g(x∗) = g
(
lim
k→∞
xk
)
= lim
k→∞
g(xk) = lim
k→∞
xk+1 = x
∗.
Portanto, x∗ e´ um ponto fixo da func¸a˜o g.
5
O teorema a seguir mostra quais sa˜o as condic¸o˜es que devem ser cumpridas para o bom
funcionamento do me´todo do ponto fixo.
Teorema 3: Seja g : [a, b] → R uma func¸a˜o cont´ınua com primeira derivada tambe´m
cont´ınua em [a, b]. Considere α uma constante real, x0 ∈ [a, b] e suponha que g(x) ∈ [a, b]
para todo x ∈ [a, b].
� Se |g′(x)| ≤ α < 1 para todo x ∈ (a, b), enta˜o o me´todo do ponto fixo gera uma
sequeˆncia (xk)k que converge para o u´nico ponto fixo de g em [a, b]. Nesse caso, o
ponto fixo e´ chamado atrator.
� Se |g′(x)| > 1 para todo x ∈ (a, b), o me´todo gera uma sequeˆncia divergente e o ponto
fixo e´ chamado repulsivo.
Prova: a demonstrac¸a˜o desse resultado pode ser encontrada, por exemplo, em Numerical
Analysis - R. Burden, J. Faires - 9a Edic¸a˜o - Editora Cengage Learning - pa´gs. 62, 63.
Algoritmo
A implementac¸a˜o computacional do processo iterativo do ponto fixo e´ simples e pode ser
descrita atrave´s dos seguintes passos:
0: Dados M ∈ N, uma toleraˆncia � > 0 e uma aproximac¸a˜o inicial x0 ∈ [a, b], fac¸a k ← 1.
1: Enquanto k ≤M fac¸a:
2: x1 ← g(x0)
3: Se |x1 − x0| < �: imprima x1 e pare o algoritmo.
4: Caso contra´rio: fac¸a x0 ← x1, k ← k + 1 e volte ao passo 1.
5: Fim
Observemos que e´ necessa´rio introduzir um crite´rio de parada neste algoritmo (vejam o passo
3). Caso x1 esteja suficientemente pro´ximo de x0, interrompemos as iterac¸o˜es e aceitamos
x1 como uma aproximac¸a˜o para o ponto fixo de g. Este crite´rio e´ razoa´vel porque se temos
|x1 − x0| = |g(x0)− x0| < �, significa que g(x0) ≈ x0. Na pior das hipo´teses, se o crite´rio de
para na˜o for atingido, o algoritmo para porque atingiu o nu´mero ma´ximo de iterac¸o˜es M .
Equac¸o˜es Na˜o Lineares e o Me´todo do Ponto Fixo
E´ poss´ıvel aplicar o me´todo do ponto fixo para encontrar soluc¸o˜es aproximadas de equac¸o˜es
na˜o lineares da forma f(x) = 0. Para isso, a func¸a˜o f(x) precisa estar escrita na forma
f(x) = g(x) − x, ou ainda, f(x) = x − g(x). Assim, se x∗ for soluc¸a˜o da equac¸a˜o f(x) = 0
sera´ tambe´m ponto fixo de g(x) pois f(x∗) = 0 ⇒ g(x∗) − x∗ = 0 ⇒ g(x∗) = x∗. A
dificuldade de utilizar essa estrate´gia para resolver equac¸o˜es na˜o lineares esta´ no fato de na˜o
sabermos, em princ´ıpio, se a func¸a˜o g(x) atende as hipo´teses do Teorema 3 que garantem
a convergeˆncia do me´todo do ponto fixo. Verificar estas condic¸o˜es pode na˜o ser tarefa fa´cil.
6
Exemplo 4:
Considere a func¸a˜o g(x) = 1 +x−x2/4 e a tarefa de determinar os pontos fixos de g atrave´s
do processo iterativo (1). Sabendo que os pontos fixos sa˜o −2 e 2, analise o comportamento
do me´todo partindo dos valores iniciais x0 = −2.05, x0 = 1.6, considerando os respectivos
intervalos [−3,−1] e [1, 3]. (Fonte: Numerical Methods Using MATLAB - J. Mathews, K.
Fink - 4a Edic¸a˜o - Editora Pearson - pa´g. 48.)
Resoluc¸a˜o: Algumas iterac¸o˜es esta˜o ilustradas na tabela abaixo.
Caso 1: [−3,−1] Caso 2: [1, 3]
x0 = −2.05 x0 = 1.6
x1 = −2.100625 x1 = 1.96
x2 = −2.20378135 x2 = 1.9996
x3 = −2.41794441 x3 = 1.99999996
...
...
lim
k→∞
xk = −∞ lim
k→∞
xk = 2
No Caso 1 temos que |g′(x)| > 3/2 no intervalo [−3,−1] e, ale´m disso, a imagem de g(x)
na˜o esta´ inteiramente contida em [−3,−1]. Assim, g(x) na˜o cumpre as condic¸o˜es suficientes
estabelecidas no Teorema 3. Ja´ no Caso 2 essas condic¸o˜es sa˜o satisfeitas pois temos
que g(x) ∈ [1, 3] e |g′(x)| < 1
2
para todo x ∈ [1, 3]. Logo, a convergeˆncia do me´todo esta´
garantida.
Exemplo 5:
Sabendo que f(x) = x3 + 4x2 − 10 = 0 possui uma u´nica raiz x∗ em [1, 2], proponha uma
func¸a˜o g(x) de forma que a equac¸a˜o dada possa ser escrita como f(x) = x− g(x). Verifique
se o me´todo do ponto fixo pode ser aplicado para encontrar x∗. (Fonte: Numerical Analysis
- R. Burden, J. D. Faires - 9a Edic¸a˜o - Editora Cengage Learning - pa´g. 59.)
Resoluc¸a˜o: somando e subtraindo x na expressa˜o da equac¸a˜o f(x) = 0, podemos escrever
f(x) = x − x + x3 + 4x2 − 10 = 0 ⇒ x = x − x3 − 4x2 + 10. Assim, definimos a func¸a˜o
g(x) = x−x3−4x2 +10. Notemos que g(1) = 6 e g(2) = −12, ou seja, a imagem de g(x) na˜o
esta´ contida em [1, 2] para todo x ∈ [1, 2]. Ale´m disso, g′(x) = 1− 3x2− 8x, implicando que
|g′(x)| > 1 para todo x ∈ [1, 2]. Como o Teorema 3 na˜o garante que o me´todo falha para
esta escolha de g(x), na˜o podemos esperar que a convergeˆncia do me´todo esteja garantida.
De fato, realizando algumas iterac¸o˜es partindo de x0 = 1.5 obtemos
x0 = 1.5, x1 = −0.875, x2 = 6.732, x3 = −469.7, x4 = 1.03× 108, . . .
7
Uso de softwares
Alguns softwares possuem rotinas espec´ıficas para trabalhar com pontos fixos de func¸o˜es. O
software Mathematica, por exemplo, possui o comando FixedPoint[ ] que implementa uma
versa˜o do processo iterativo (1). Segue abaixo um exemplo de como utilizar este comando.
Exemplo 6
Utilizando o comando FixedPoint[ ], determine os pontos fixos da func¸a˜o g(x) = 1+x−x2/4.
Resoluc¸a˜o: a sintaxe do comando requer dois argumentos de entrada separados por v´ırgula:
a expressa˜o da func¸a˜o g(x) entre pareˆnteses, onde a varia´vel x e´ substitu´ıda pelo s´ımbolo
# juntamente com o s´ımbolo & apo´s o fechamento dos pareˆnteses e o valor inicial x0. Esta
func¸a˜o g(x) ja´ foi discutida no Exemplo 4. A Figura 5 ilustra as respostas do comando
para os valores iniciais x0 = 1.6 e x0 = −2.05. Como vimos naquele exemplo, x0 = 1.6 e´ um
bom valor inicial para iterar com o me´todo. Ja´ x0 = −2.05 produz uma sequeˆncia nume´rica
com nu´meros cada vez mais negativos e mais distantes do ponto fixo x∗ = −2, o que obriga
o software a imprimir uma mensagem de overflow.
Figura 5: Exemplo de uso do comando FixedPoint[ ].
Exerc´ıcios
1. Considerando a func¸a˜o g(x) = −4 + 4x− 1
2
x2, investigue o comportamento do me´todo
do ponto fixo respondendo os itens abaixo.
a) Resolva a equac¸a˜o x = g(x) para mostrar que x = 2 e x = 4 sa˜o pontos fixos.
b) Aplique o me´todo do ponto fixo partindo de x0 = 1.9 e calcule x1, x2 e x3.
c) Aplique o me´todo do ponto fixo partindo de x0 = 3.8 e calcule x1, x2 e x3.
d) Calcule os erros absolutos obtidos em cada iterac¸a˜o dos itens b) e c).
e) Que concluso˜es podemos obter a partir do Teorema 3?
8
2. Verifique graficamente se o me´todo do ponto fixo converge nos seguintes casos:
a) g(x) = 1 + 2/x e x0 = 4 (o ponto fixo e´ x = 2),
b) g(x) = x2/3 e x0 = 3.5 (o ponto fixo e´ x = 3).
3. Seja g(x) = pi + 0.5 sen(x/2).
a) Mostre que g(x) possui um u´nico ponto fixo em [0, 2pi].
b) Aplique treˆs iterac¸o˜es do me´todo do ponto fixo para estimar x∗ tal que g(x∗) = x∗.
4. Utilize o me´todo do ponto fixo para determinar uma soluc¸a˜o aproximada para a equac¸a˜o
g(x) = x4 − 3x2 − 3 = 0 no intervalo [1, 2] com precisa˜o inferior a 10−2. Considere
x0 = 1.
5. Suponha que g(x) e g′(x) sa˜o cont´ınuas em (a, b) e que existe uma constante α tal que
|g′(x)| < α. Suponha tambe´m que x0, x1, x2 ∈ (a, b) e que x1 = g(x0), x2 = g(x1).
a) Mostre que |x2 − x1| < α|x1 − x0|.
b) Suponha agora que x˜ e´ ponto fixo de g em (a, b) e |g′(x)| > 1 em (a, b). Mostre
que |x˜ − x1| > |x˜ − x0|. O que se pode afirmar sobre a convergeˆncia do me´tododo ponto fixo em uma vizinhanc¸a de x0?
Dica: use o Teorema do Valor Me´dio em ambos os itens.
6. Dadas as func¸o˜es g(x) abaixo, determine todos os pontos fixos de g. O me´todo do ponto
fixo pode ser utilizado para encontrar as soluc¸o˜es da equac¸a˜o x = g(x)? Justifique.
a) g(x) = x cos(x)
b) g(x) = x2 + x− 4
7. Se x∗ e´ um ponto fixo de g(x), por queˆ e´ vantajoso para o me´todo do ponto fixo termos
g′(x∗) ≈ 0?
8. Considere o processo iterativo xk+1 = 2 +
1
xk
comec¸ando em x0 = 2.
a) Mostre que xk ∈ [2, 2.5] para todo k.
b) Mostre que a sequeˆncia (xk)k gerada pelo processo e´ convergente.
c) Calcule lim
k→∞
xk.
9