Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão Python

3.3 Iteração de ponto fixo


Nesta seção, discutimos a abordagem da iteração do ponto fixo para a solução numérica de equações de uma variável real. Observamos que sempre podemos reescrever uma equação da forma f(x) = 0 (problema de encontrar os zeros de uma função) em uma equação equivalente na forma g(x) = x (problema de ponto fixo). Um ponto x = x* tal que g(x*) = x* é chamado de ponto fixo da função g(x). Geometricamente, um ponto fixo de uma função é um ponto de interseção entre a reta y = x com o gráfico da função g(x) (veja Figura 3.3).


PIC

Figura 3.3: Ponto fixo g(x*) = x*.


Exemplo 3.3.1. Resolver a equação ex = x + 2 é equivalente a resolver f(x) = 0, com f(x) = ex - x - 2. Estes são equivalentes a resolver g(x) = x, com g(x) = ex - 2, isto é:

ex = x + 2 ex - x - 2 = 0 ex - 2 = x (3.25)

Dada uma função g(x), a iteração do ponto fixo consiste em computar a seguinte sequência recursiva:

x(n+1) = g(x(n)),n 1, (3.26)

onde x(1) é uma aproximação inicial do ponto fixo.

Exemplo 3.3.2 (Método babilônico). O método babilônico4 é de uma iteração de ponto fixo para extrair a raiz quadrada de um número positivo A, isto é, resolver a equação x2 = A.

Seja r > 0 uma aproximação para A. Temos três possibilidades:

  • r > AA r < AA A r ,r ;
  • r = AA r = A;
  • r < AA r > AA r, A r .

Ou seja, A sempre está no intervalo entre r e A r , no qual podemos buscar uma nova aproximação como, por exemplo, pelo ponto médio:

x = r + A r 2 . (3.27)

Aplicando esse método repetidas vezes, podemos construir a iteração (de ponto fixo): x(1) = r (3.28) x(n+1) = x(n) 2 + A 2x(n),n = 1,2,3,... (3.29)

Por exemplo, para obter uma aproximação para 5, podemos iniciar com a aproximação inicial r = 2 e A = 5. Então, tomamos x(1) = 2 e daí seguem as aproximações: x(2) = 2 2 + 2,5 2 = 2,25 (3.30) x(3) = 2,25 2 + 2,5 2,25 = 2,2361111 (3.31) x(4) = 2,2361111 2 + 2,5 2,2361111 = 2,236068 (3.32) x(5) = 2,236068 2 + 2,5 2,236068 = 2,236068 (3.33)

O método babilônico sugere que a iteração do ponto fixo pode ser uma abordagem eficiente para a solução de equações. Ficam, entretanto, as seguintes perguntas:

1.
Será que a iteração do ponto fixo é convergente?
2.
Caso seja convergente, será que o limite da sequência produzida, isto é, x* := lim nx(n) é um ponto fixo?
3.
Caso seja convergente, qual é a taxa de convergência?

A segunda pergunta é a mais fácil de ser respondida. No caso de g(x) ser contínua, se x(n) x* Dom (g), então:

x* = lim nx(n) = lim ng(x(n-1)) = g lim nx(n-1) = g(x*). (3.34)

Antes de respondermos as outras perguntas acima, vejamos mais um exemplo.

Exemplo 3.3.3. Considere o problema de encontrar o zero da função f(x) = xex - 10. Uma maneira geral de construir um problema de ponto fixo equivalente é o seguinte:

f(x) = 0 αf(x) = 0 x - αf(x) = x, (3.35)

para qualquer parâmetro α0. Consideremos, então, as seguintes duas funções:

g1(x) = x - 0,5f(x)eg2(x) = x - 0,05f(x). (3.36)

Notamos que o ponto fixo destas duas funções coincide com o zero de f(x). Construindo as iterações do ponto fixo:

x1(n+1) = g 1(x1(n))ex 2(n+1) = g 2(x2(n)), (3.37)

tomando x1(1) = x 2(1) = 1,7, obtemos os resultados apresentados na Tabela 3.2. Observamos que, enquanto, a iteração do ponto fixo com a função g1(x) (α = 0,5) parece divergir, a iteração com a função g2(x) (α = 0,05) parece convergir.



Tabela 3.2: Iterações do ponto fixo para o Exemplo 3.3.3.



n x1(n) x 2(n)



1 1,700 1,700
2 2,047 1,735
3 - 0,8812 1,743
4 4,3013 1,746
5 - 149,4 1,746




Em Python, podemos computar as iterações do ponto fixo x(n+1) = g 1(x(n)) com o seguinte código:

>>> def f(x): return x*np.exp(x)-10  
...  
>>> def g1(x): return x-0.5*f(x)  
...  
>>> x=1.7  
>>> x=g1(x);x  
2.0471447170318804  
>>> x=g1(x);x  
-0.88119413893725618

e, assim, sucessivamente. Itere com a função g2(x) e verifique a convergência!

A fim de estudarmos a convergência da iteração do ponto fixo, apresentamos o teorema do ponto fixo.

3.3.1 Teorema do ponto fixo


O teorema do ponto fixo nos fornece condições suficientes para a existência e unicidade do ponto fixo, bem como para a convergência das iterações do método.

Definição 3.3.1. Uma contração é uma função real g : [a,b] [a,b] tal que:

|g(x) - g(y)| β|x - y|,0 β < 1. (3.38)

Observação 3.3.1. Seja g : [a,b] [a,b], y=g(x).

  • Se g(x) é uma contração, então g(x) função contínua.
  • Se |g(x)| < k, 0 < k < 1, para todo x [a,b], então g(x) é uma contração.

Teorema 3.3.1 (Teorema do ponto fixo). Se g : [a,b] [a,b] é uma contração, então existe um único ponto x* [a,b] tal que g(x*) = x*, isto é, x* é ponto fixo de g(x). Além disso, a sequência {x(n)} n dada por:

x(n+1) = g(x(n)) (3.39)

converge para x* para qualquer x(1) [a,b].

Demonstração. Começamos demonstrando que existe pelo menos um ponto fixo. Para tal definimos a função f(x) = x - g(x) e observamos que:
f(a) = a - g(a) a - a = 0 (3.40)

e

f(b) = b - g(b) b - b = 0 (3.41)

Se f(a) = a ou f(b) = b, então o ponto fixo existe. Caso contrário, as desigualdades são estritas e a f(x) muda de sinal no intervalo. Como esta função é contínua, pelo teorema de Bolzano 3.1.1, existe um ponto x* no intervalo (a,b) tal que f(x*) = 0, ou seja, g(x*) = x*. Isto mostra a existência.

Para provar que o ponto fixo é único, observamos que se x* e x** são pontos fixos, eles devem ser iguais, pois:

|x* - x**| = |g(x*) - g(x**)| β|x* - x**|. (3.42)

A desigualdade |x* - x**| β|x* - x**| com 0 β < 1 implica |x* - x**| = 0.

Para demonstrar a convergência da sequência, observamos que:

|x(n+1) - x*| = |g(x(n)) - x*| = |g(x(n)) - g(x*)| β|x(n) - x*|. (3.43)

Daí, temos:

|x(n) - x*| β|x(n-1) - x*| β2|x(n-2) - x*| βn|x(0) - x*|. (3.44)

Portanto, como 0 β < 1, temos:

lim n|x(n) - x*| = 0, (3.45)

ou seja, x(n) x* quando n .

Observação 3.3.2. Do teorema do ponto fixo, temos que se g(x) é uma contração com constante 0 β < 1, então:

|x(n+1) - x*| β|x(n) - x*|,n 1. (3.46)

Isto é, as iterações do ponto fixo têm taxa de convergência linear.

Exemplo 3.3.4. Mostre que o teorema do ponto fixo se aplica a função g(x) = cos(x) no intervalo [12, 1], isto é, a iteração de ponto fixo converge para a solução da equação cos x = x. Então, calcule as iterações do ponto fixo com aproximação inicial x(1) = 0,7, estime o erro absoluto da aproximação e verifique a taxa de convergência.

Solução. Basta mostrarmos que:

a)
g [12,1] [12,1];
b)
|g(x)| < β,0 < β < 1,x [12,1].

Para provar a), observamos que g(x) é decrescente no intervalo, pelo que temos:

0,54 < cos(1) cos(x) cos(12) < 0,88 (3.47)

Como [0,54,0,88] [0,5,1], temos o item a).

Para provar o item b), observamos que:

g(x) = - sen (x). (3.48)

Da mesma forma, temos a estimativa:

-0,85 < - sen (1) - sen (x) - sen (12) < -0,47. (3.49)

Assim, |g(x)| < 0,85 e temos a desigualdade com β = 0,85 < 1.






n x(n) ϵ n := |x(n) - x*|




1 0,70000 3,9E -02
2 0,76484 2,6E -02
3 0,72149 1,8E -02
4 0,75082 1,2E -02
5 0,73113 8,0E -03
6 0,74442 5,3E -03
7 0,73548 3,6E -03





Tabela 3.3: Iteração do ponto fixo para o Exemplo 3.3.4.

A Tabela 3.3 apresenta o comportamento numérico da iteração do ponto fixo: x(1) = 0,7 (3.50) x(n+1) = cos(x(n)),n 1. (3.51)

Para estimar o erro, consideramos x* = 0,7390851605. A Figura 3.4 mostrar o decaimento do erro ϵn = |x(n) - x*| comparado com a taxa de convergência linear com β = 0,85.


PIC

Figura 3.4: Decaimento do erro ϵn = |x(n) - x*| da iteração do ponto fixo estudada no Exemplo 3.3.4.


Em Python, podemos computar estas iterações, o erro absoluto com o seguinte código:

#funcao do pto. fixo  
def g(x):  
    return np.cos(x)  
 
#est. da solucao  
xe = sci.optimize.fixed_point(g, 0.7)  
 
#aprox. inicial  
x0 = 0.7  
eps = np.fabs(x0-xe)  
print("x1 =  %.5f, eps =~ %.1e" % (x0, eps))  
 
for i in np.arange(7):  
    x = g(x0);  
    eps = np.fabs(x-xe);  
    print("%s =~ %.5f, eps =~ %.1e" % ((’x’+str(i+2)), x, eps))  
    x0 = x

3.3.2 Teste de convergência


Seja g : [a,b] uma função C0[a,b] e x* (a,b) um ponto fixo de g. Então x* é dito estável se existe uma região (x* - δ,x* + δ) chamada bacia de atração tal que x(n+1) = g(x(n)) é convergente sempre que x(0) (x* - δ,x* + δ).

Proposição 3.3.1 (Teste de convergência). Se g C1[a,b] e |g(x*)| < 1, então x* é estável. Se |g(x*)| > 1 é instável e o teste é inconclusivo quando |g(x*)| = 1.


PIC   PIC

Figura 3.5: Ilustração das iterações do ponto fixo para: (esquerda) y = g1(x) e (direita) y = g2(x). Veja Exemplo 3.3.5.


Exemplo 3.3.5. No Exemplo 3.3.3, observamos que a função g1(x) nos forneceu uma iteração divergente, enquanto que a função g2(x) forneceu uma iteração convergente (veja a Figura 3.5. Estes comportamentos são explicados pelo teste da convergência. Com efeito, sabemos que o ponto fixo destas funções está no intervalo [1,6, 1,8] e temos:

|g1(x)| = |1 - 0,5(x + 1)ex| > 4,8,x [1,6, 1,8], (3.52)

enquanto:

|g2(x)| = |1 - 0,05(x + 1)ex| < 0,962,x [1,6, 1,8]. (3.53)

3.3.3 Estabilidade e convergência


A fim de compreendermos melhor os conceitos de estabilidade e convergência, considere uma função Φ(x) com um ponto fixo x* = g(x*) e analisemos o seguinte processo iterativo: x(n+1) = g x(n) (3.54) x(0) = x (3.55)

Vamos supor que a função g(x) pode ser aproximada por seu polinômio de Taylor em torno do ponto fixo: g(x) = g(x*) + (x - x*)g(x*) + O (x - x*)2 (3.56) = x* + (x - x*)g(x*) + O (x - x*)2 (3.57) x* + (x - x*)g(x*) (3.58)

Substituindo na relação de recorrência, temos

x(n+1) = g x(n) x* + (x(n) - x*)g(x*) (3.59)

Ou seja:

x(n+1) - x* (x(n) - x*)g(x*) (3.60)

Tomando módulos, temos:

x(n+1) - x* ϵn+1 x(n) - x* ϵn g(x*) , (3.61)

onde ϵn = x(n) - x*.

Observação 3.3.3. Da análise acima, concluímos:

  • Se |g(x*)| < 1, então, a distância de x(n) até o ponto fixo x* está diminuindo a cada passo.
  • Se |g(x*)| > 1, então, a distância de x(n) até o ponto fixo x* está aumentando a cada passo.
  • Se |g(x*)| = 1, então, nossa aproximação de primeira ordem não é suficiente para compreender o comportamento da sequência.

3.3.4 Erro absoluto e tolerância


Na prática, quando se aplica uma iteração como esta, não se conhece de antemão o valor do ponto fixo x*. Assim, o erro ϵn = x(n) - x* precisa ser estimado com base nos valores calculados x(n). Uma abordagem frequente é analisar a evolução da diferença entre dois elementos da sequência:

Δn = x(n+1) - x(n) (3.62)

A pergunta natural é: Será que o erro ϵn = x(n) - x* será pequeno quando Δn = x(n+1) - x(n) for pequeno?

Para responder a esta pergunta, observamos que

x* = lim nx(n) (3.63)

portanto: x* - x(N) = x(N+1) - x(N) + x(N+2) - x(N+1) + x(N+3) - x(N+2) + (3.64) = k=0 x(N+k+1) - x(N+k) (3.65)

Usamos também as expressões: x(n+1) x* + (x(n) - x*)g(x*) (3.66) x(n) x* + (x(n-1) - x*)g(x*) (3.67)

Subtraindo uma da outra, temos: x(n+1) - x(n) (x(n) - x(n-1))g(x*) (3.68)

Portanto: x(N+k+1) - x(N+k) (x(N+1) - x(N)) g(x*) k (3.69)

E temos: x* - x(N) = k=0 x(N+k+1) - x(N+k) (3.70) k=0(x(N+1) - x(N)) g(x*) k (3.71) = (x(N+1) - x(N)) 1 1 - g(x*), g(x*) < 1 (3.72)

Tomando módulo, temos: x* - x(N) x(N+1) - x(N) 1 1 - g(x*) (3.73) ϵN ΔN 1 - g(x*) (3.74)

Observação 3.3.4. Tendo em mente a relação x(n+1) - x(n) (x(n) - x(n-1))g(x*), concluímos:

  • Quando g(x*) < 0, o esquema é alternante, isto é, o sinal do erro se altera a cada passo. O erro ϵN pode ser estimado diretamente da diferença ΔN, pois o denominador 1 - g(x*) > 1.
  • Quando 0 < g(x*) < 1, o esquema é monótono e 1 1-g(x*) > 1, pelo que o erro ϵN é maior que a diferença ΔN. A relação será tão mais importante quando mais próximo da unidade for g(x*), ou seja, quando mais lenta for a convergência. Para estimar o erro em função da diferença ΔN, observamos que g(x*) x(n+1)-x(n) x(n)-x(n-1) e
    g(x*) Δn Δn-1 (3.75)

    e portanto

    ϵN ΔN 1 - Δn Δn-1. (3.76)

Exercícios


E 3.3.1. Resolver a equação ex = x + 2 é equivalente a calcular os pontos fixos da função g(x) = ex - 2 (veja o Exemplo 3.3.1). Use a iteração do ponto fixo x(n+1) = g(xn) com x(1) = -1,8 para obter uma aproximação de uma das soluções da equação dada com 8 dígitos significativos.

Resposta. - 1,8414057

E 3.3.2. Mostre que a equação:

cos(x) = x (3.77)

possui uma única solução no intervalo [0, 1]. Use a iteração do ponto fixo e encontre uma aproximação para esta solução com 4 dígitos significativos.

Resposta.

0,7391

E 3.3.3. Mostre que a equação xex = 10 é equivalente às seguintes equações:

x = ln 10 x ex = 10e-x. (3.78)

Destas, considere as seguintes iterações de ponto fixo:

a)
x(n+1) = ln 10 x(n)
b)
x(n+1) = 10e-x(n)

Tomando x(1) = 1, verifique se estas sequências são convergentes.

Resposta.

Tomemos x(1) = 1 como aproximação inicial para a solução deste problema, iterando a primeira sequência a), obtemos: x(1) = 1 (3.79) x(2) = ln 10 1 = 2,3025851 (3.80) x(3) = ln 10 2,3025851 = 1,4685526 (3.81) (3.82) x(21) = 1,7455151 (3.83) x(31) = 1,745528 (3.84) x(32) = 1,745528 (3.85)

Iterando a segunda sequência b), obtemos: x(1) = 1 (3.86) x(2) = 10e-1 = 3,6787944 (3.87) x(3) = 10e-3,6787944 = 0,2525340 (3.88) x(4) = 10e-0,2525340 = 7,7682979 (3.89) x(5) = 10e-7,7682979 = 0,0042293 (3.90) x(6) = 10e-0,0042293 = 9,9577961 (3.91)

Este experimento numérico sugere que a iteração a) converge para 1,745528 e a iteração b) não é convergente.

E 3.3.4. Verifique (analiticamente) que a única solução real da equação:

xex = 10 (3.92)

é ponto fixo das seguintes funções:

  • g(x) = ln 10 x
  • g(x) = x - xex-10 15
  • g(x) = x - xex-10 10+ex

Implemente o processo iterativo x(n+1) = g(x(n)) para n 0 e compare o comportamento. Discuta os resultados com base na teoria estudada.

E 3.3.5. Verifique (analiticamente) que a única solução real da equação:

cos(x) = x (3.93)

é ponto fixo das seguintes funções:

  • g(x) = cos(x)
  • g(x) = 0,4x + 0,6 cos(x)
  • g(x) = x + cos(x)-x 1+sen (x)

Implemente o processo iterativo x(n+1) = g(x(n)) para n 0 e compare o comportamento. Discuta os resultados com base na teoria estudada.

E 3.3.6. Encontre a solução de cada equação com erro absoluto inferior a 10-6.

  • ex = x + 2 no intervalo (-2,0).
  • x3 + 5x2 - 12 = 0 no intervalo (1,2).
  • x = cos(x) no intervalo (0,1).

E 3.3.7. Encontre numericamente as três primeiras raízes positivas da equação dada por:

cos(x) = x 10 + x2 (3.94)

com erro absoluto inferior a 10-6.

Resposta. x1 1,4506619, x2 4,8574864, x3 = 7,7430681.

E 3.3.8. Considere os seguintes processos iterativos:

a x(n+1) = cos(x(n)) x(1) =.5  e  b x(n+1) =.4x(n) + .6 cos(x(n)) x(1) =.5 (3.95)

Use o teorema do ponto fixo para verificar que cada um desses processos converge para a solução da equação x* de cos(x) = x. Observe o comportamento numérico dessas sequências. Qual estabiliza mais rápido com cinco casas decimais? Discuta.

Dica: Verifique que cos([0.5,1]) [0.5,1] e depois a mesma identidade para a função f(x) = 0,4x + 0,6 cos(x).

E 3.3.9. Use o teorema do ponto fixo aplicado a um intervalo adequado para mostrar que a função g(x) = ln(100 - x) possui um ponto fixo estável.

E 3.3.10. (Fluidos) Na hidráulica, o fator de atrito de Darcy é dado pela implicitamente pela equação de Colebrook-White:

1 f = -2 log 10 ε 14.8Rh + 2.51 Ref (3.96)

onde f é o fator de atrito, ε é a rugosidade do tubo em metros, Rh é o raio hidráulico em metros e Re é o número de Reynolds. Considere ε = 2mm, Rh = 5cm e Re = 10000 e obtenha o valor de f pela iteração:

x(n+1) = -2 log 10 ε 14.8Rh + 2.51x(n) Re (3.97)

Resposta.

0.0431266

E 3.3.11. Encontre uma solução aproximada para a equação algébrica

180 - 100x = 0.052 senh -1(1013x) (3.98)

com erro absoluto inferior a 10-3 usando um método iterativo. Estime o erro associado ao valor de v = 180 - 100x = 0.052 senh -1(1013x), usando cada uma dessas expressões. Discuta sucintamente o resultado obtido. Dica: Este caso é semelhante ao Problema 3.2.8.

E 3.3.12. Considere que xn satisfaz a seguinte relação de recorrência:

xn+1 = xn - β xn - x* (3.99)

onde β e x* são constantes. Prove que

xn - x* = (1 - β)n-1(x 1 - x*). (3.100)

Conclua que xn x* quando |1 - β| < 1.

E 3.3.13. (Convergência lenta) Considere o seguinte esquema iterativo: x(n+1) = x n + qn, (3.101) x(0) = 0, (3.102)

onde q = 1 - 10-6.

  • Calcule o limite
    x = lim nx(n) (3.103)

    analiticamente.

  • Considere que o problema de obter o limite da sequência numericamente usando como critério de parada que |x(n+1) - x(n)| < 10-5. Qual o valor é produzido pelo esquema numérico? Qual o desvio entre o valor obtido pelo esquema numérico e o valor do limite obtido no item a? Discuta. (Dica: Você não deve implementar o esquema iterativo, obtendo o valor de x(n) analiticamente)
  • Qual deve ser a tolerância especificada para obter o resultado com erro relativo inferior a 10-2?

E 3.3.14. (Convergência sublinear) Considere o seguinte esquema iterativo:

x(n+1) = x(n) - [x(n)]3,x(n) 0 (3.104)

com x(0) = 10-2. Prove que {x(n)} é sequência de número reais positivos convergindo para zero. Verifique que são necessários mais de mil passos para que x(n) se torne menor que 0.9x(0).

E 3.3.15. (Taxa de convergência)

  • Use o teorema do ponto fixo para mostrar que a função g(x) = 1 - sen (x) possui um único ponto fixo estável o intervalo [ 1 10,1]. Construa um método iterativo x(n+1) = g(x(n)) para encontrar esse ponto fixo. Use o computador para encontrar o valor numérico do ponto fixo.
  • Verifique que função ψ(x) = 1 2 x + 1 - sen (x) possui um ponto fixo x* que também é o ponto fixo da função g do item a. Use o computador para encontrar o valor numérico do ponto fixo através da iteração x(n+1) = ψ(x(n)). Qual método é mais rápido?

E 3.3.16. (Esquemas oscilantes)(Esquemas oscilantes)

  • Considere a função g(x) e a função composta ψ(x) = g g = g g(x). Verifique todo ponto fixo de g também é ponto fixo de ψ.
  • Considere a função
    g(x) = 10 exp(-x) (3.105)

    e a função composta ψ(x) = g g = g g(x). Mostre que ψ possui dois pontos fixos que não são pontos fixos de g.

  • No problema anterior, o que acontece quando o processo iterativo x(n+1) = g(x(n)) é inicializado com um ponto fixo de ψ que não é ponto fixo de g?

E 3.3.17. (Aceleração de convergência - introdução ao método de Newton) Mostre que se f(x) possui uma raiz x* então a x* é um ponto fixo de ϕ(x) = x + γ(x)f(x). Encontre uma condição em γ(x) para que o ponto fixo x* de ϕ seja estável. Encontre uma condição em γ(x) para que ϕ(x*) = 0.

E 3.3.18. (Aceleração de convergência - introdução ao método de Newton) Considere que x(n) satisfaz a seguinte relação de recorrência:

x(n+1) = x(n) - γf(x(n)) (3.106)

onde γ é uma constante. Suponha que f(x) possui um zero em x*. Aproxime a função f(x) em torno de x* por

f(x) = f(x*) + f(x*)(x - x*) + O (x - x*)2 . (3.107)

Em vista do problema anterior, qual valor de γ você escolheria para que a sequência x(n) convirja rapidamente para x*.

E 3.3.19. Considere o problema da Questão 3.2.8 e dois seguintes esquemas iterativos.

A I(n+1) = 1 R V - vt ln 1 + I(n) IR ,n > 0 I(0) = 0  e  B I(n+1) = I R exp V -RI(n) vt - 1 ,n > 0 I(0) = 0 (3.108)

Verifique numericamente que apenas o processo A é convergente para a, b e c; enquanto apenas o processo B é convergente para os outros itens.

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 15/5/2019 às 15:24:50.

Informe erros ou edite você mesmo!