7. convergencia aprox s

Prévia do material em texto

Convergência do Método das Aproximações 
Sucessivas 
Identificar em que circunstâncias um algoritmo converge para a solução exata não 
é tarefa simples. Mas, partindo de resultados teóricos iremos definir quais as 
condições que garantem a convergência a priori. 
Estas condições deverão ser sempre verificadas antes de iniciar o processo 
computacional. 
 
 
Um pouco sobre convergência 
 
Dada uma função f tal que α é uma de suas raizes e φ, obtida através de 
manipulações algébricas da equação 
f(x) =0 (lembrando que precisamos respeitar as regras básicas 
como não dividir por zero,...) 
chegamos à equação 
φ( x) = x, 
que vai gerar a seqüência das iteradas 
 x
k+1 
= φ(xk).
 
A intersecção de φcom a reta y = x é o ponto fixo de φ. E as projeções de φ(xk) 
sobre a reta y = x determinam os pontos x
k+1
 correspondentes, projetados no eixo 
x. 
Se garantirmos que a seqüência gerada por φ é uma seqüencia convergente 
e que α, o ponto fixo de φ é raiz de f , então x0, x1, ... xk é uma seqüência que 
converge para a raiz de f. 
Análise gráfica da convergência 
Vamos analisar algumas possibilidades para o comportamento destas iteradas 
através de uma análise gráfica. As figuras de 1 a 4 representam as possíveis 
situações que podemos encontrar, para a seqüência dados os gráficos da α e de y 
= x: 
Página 1 de 7Convergência do Método das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm
 
Figura1: neste caso a seqüência das iteradas é crescente e 
converge para a raiz α, que é a intersecção de φcom a reta 
y=x. 
x0 < x1 < x2 < ... < xk < ... α; 
 
 
Figura2: neste caso a seqüência é decrescente e não temos 
a convergência para a raiz α; 
 
 
Figura3: neste caso a seqüência é oscilante e temos a 
convergência para a raiz α ( a raiz fica confinada entre duas 
iteradas consecutivas); 
Página 2 de 7Convergência do Método das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm
 
 
 
 
Figura 4: neste caso a seqüência é oscilante e não temos a 
convergência para a raiz α (não importa o quão próximo da 
raiz conseguimos dar o chute inicial); 
Observações: 
1 ) no caso de seqüências oscilantes, a raiz está sempre entre duas 
iteradas consecutivas. Se a seqüência é convergente, quando a 
diferença 
| x
k+1 - 
xk| for menor que uma precisão pré-fixada, encontramos um 
resultado aproximado dentro de um intervalo de interesse. 
2) no caso de seqüências crescentes e convergentes a raiz está 
sempre à direita dos valores calculados para as iteradas. Portanto, não 
é suficiente verificar que a distância entre duas iteradas consecutiva 
(xk e xk+1) é menor que a precisão pré-fixada, para garantir que essa 
precisão foi atingida. 
 
Condições suficientes para garantir a convergência da seqüência das 
iteradas 
 
Lembrete: uma condição suficiente significa que se verificada, garante 
determinado resultado mas, caso
 não seja verificada não podemos dizer que não 
garantimos o resultado. 
No caso do Método das aproximações Sucessivas é possível garantir a 
convergência das iteradas para α , ponto fixo de φ e raiz de f, se as hipóteses do 
teorema do ponto fixo forem verificadas. 
Quando não é possível verificar todas as hipóteses, não poderemos afirmar que a 
Página 3 de 7Convergência do Método das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm
seqüência não converge para a raiz. Só podemos dizer que não podemos garantir 
a convergência. 
Por prudência, quando a convergência não puder ser garantida para uma 
determinada função φ, vamos evitar usar essa função para gerar as iteradas. 
 
 
Lembrete: uma condição suficiente significa que se verificada, garante 
determinado resultado mas, caso não seja verificada não podemos dizer que não 
garantimos o resultado. Neste caso do Método das aproximações Sucessivas, 
estas condições quando verificadas vão garantir a convergência para a raiz, 
entretanto, quando não verificadas não poderemos afirmar que a seqüência não 
converge para a raiz. Por prudência, quando nào pudermos garantir a 
convergência, vamos evitar usar essa função para gerar as iteradas. 
 
Teorema do ponto fixo (condições suficientes para garantir a convergência das iteradas 
do método das aproximações sucessivas) 
Seja αuma raiz de uma função f , isolada num intervalo I = [a, b] e 
seja φuma função tal que 
φ(α) = α. Se as seguintes hipóteses são verificadas: 
i) φe φ 'são funções contínuas em
 I; 
ii) 
 < 1; 
iii) x
0 I e xn+1 = φ(xn ), para k = 0, 1, 2,...
 
então, a seqüência converge para a raiz α. 
 
Prova: 
 
Estude esta demonstração com atenção e identifique nela as hipóteses 
que foram feitas, analise como os resultados foram construídos, pense 
na idéia utilizada para demonstrar a convergência. 
Página 4 de 7Convergência do Método das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm
Provar que 
x
n 
-> α,
 
é equivalente a mostrar que o erro absoluto | x
n 
- α| vai pra zero 
quando n vai pra infinito,ou seja, 
 | x
n
 
- α| -> 0 qdo n -> . 
 
Como 
x
n+1 
= φ(x
n 
) e α= φ(α) , 
 
Substituindo na expressão do erro absoluto temos 
 | x
n
 
- α| = | φ(x
n-1
 
) - φ(α) |, 
 
Aplicando o (*)Teorema do Valor Médio à função φ(temos por 
hipótese que é contínua com derivada contínua) 
| x
n 
- α| = | φ(x
n-1 
) - φ(α) | = | x
n 
- α| = |φ'(ξ
n-1 
)| | x
n-1
 - α|, 
 
como α I e por (iii) xn-1 I , então ξn-1 I e por (ii) temos que 
 
 |φ'(ξ
n-1 
)| ≤ k < 1. 
 
Isto significa que 
| x
n
 
- α| = |φ'(ξ
n-1
 
)| | x
n-1
 - α | ≤ k | x
n-1
 - α|, 
 
ou seja o ponto x
n
 
está mais próximo da raiz que x
n-1. 
Repetindo o 
procedimento, para | x
n-1
 - α| temos: 
| x
n-1
 
- α| = |φ '(ξ
n-2
)| | x
n-2
 - α| ≤k | x
n-2
 - α|, 
 
Substituindo na expressão de | x
n
 
- α| temos:
 
| x
n 
- α| = |φ'(ξ
n-1 
)| | x
n-1
 - α | ≤ k | x
n-1
 - α| ≤ k2 | x
n-2
 - α| 
 
Página 5 de 7Convergência do Método das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm
Repetindo o processo até atingirmos o chute inicial x0 
| x
n
 
- α| = |φ'(ξ
n-1
 
)| | x
n-1
 - α | ≤ k | x
n-1
 - α| ≤ k2 | x
n-2
 - α| ≤ 
kn | x0 - α| 
Portanto, 
| x
n 
- α|≤ kn| x0 - α|, logo
 
lim (n-> )| xn - α| ≤ | x0 - α| lim (n-> )kn = 0 
 
se k < 1. 
A seqüência das iteradas {x
n
}converge para a raiz α
 
Atenção: 
Diversas questões (em provas, principalmente) abordam a 
convergência das iteradas do método da Aproximações Sucessivas. 
Para provar que uma função φ gera uma seqüência convergente para 
uma raiz α, da equação f(x)=0, você deve passar pelas seguintes 
etapas: 
1 ) ISOLAR A RAIZ α: deve provar que a raiz está isolada e 
é única num intervalo [a,b], utilizando os resultados teóricos 
que aprendeu no Cálculo Diferencial sobre funções; 
2 ) GERAR UMA φ, A PARTIR DE f(x) = 0: em geral essa 
função φ já é dada, mas pode ser que tenha que fazer umas 
manipulações algébricas com f(x)=0 para encontra uma 
candidata; 
3 ) TESTAR AS HIPÓTESES DO TEOREMA DO PONTO 
FIXO 
i) φ e φ ' são funções contínuas em I: a 
expressão de φ ' deve ser calculada. Caso φ 
e φ ' não sejam contínuas nesse intervalo, 
encontrar o sub-intervalo J de I no qual elas 
sejam contínuas e verificar se a raiz continua 
isolada em J. 
Página 6 de 7Convergência doMétodo das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm
ii) <1: estimar o valor máximo da 
derivada e verificar que é inferior a 1 
iii) x 0 I e xn+1 = φ(xn ), para k = 0, 1, 2,...
 
 
Como garantir o item (iii), que toda a seqüência está contida no intervalo I 
Escolhendo o extremo mais próximo da raiz podemos garantir que toda a 
seqüência gerada por φ pertence a I. 
Como já foram verificados os ítens (i) e (ii), sabemos que a cada iterada o valor 
calculado está mais próximo da raiz, portanto, ao escolher o extremo mais próximo 
da raiz, definimos que nenhum valor calculado estará mais distante da raiz que 
esse extremo, o que garante a condição (iii). 
 
(*)Teorema do Valor Médio 
 
 
Seja f uma função real, definida e contínua em [a,b], derivável em (a,b), então 
existe c (a,b) tal que 
f(b) - f(a) = f '(c) (b-a). 
Geometricamente, 
 
Página 7 de 7Convergência do Método das Aproximações Sucessivas
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\convergencia_aprox_sucessivas.htm