07 convergencia de MAS

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 a é uma de suas raízes e f, 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
f( x) = x,
que vai gerar a sequência das iteradas
 xk+1 = f(xk).
A intersecção de f com a reta y = x define o ponto fixo de f. E as projeções de f(xk) sobre a reta y = x
determinam os pontos xk+1 correspondentes, projetados no eixo x.
Se garantirmos que a seqüência gerada por f é uma seqüencia convergente e que a, o ponto fixo
de f é 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
sequência dados os gráficos da a e de y = x:
 
Figura 1: neste caso a sequência das iteradas é crescente e converge para
a raiz a, que é a intersecção de fcom a reta y=x.
x0 < x1 < x2 < ... < xk < ... a;
Figura 2: neste caso a sequência é decrescente e não temos a
convergência para a raiz a;
 
 
Figura 3: neste caso a sequência é oscilante e temos a convergência para a
raiz a ( a raiz fica confinada entre duas iteradas consecutivas);
 
 
Figura 4: neste caso a sequência é oscilante e não temos a convergência
para a raiz a (não importa o quão próximo da raiz seja o chute inicial);
Observações:
1 ) no caso de sequências oscilantes, a raiz está sempre entre duas iteradas
consecutivas. Se a sequência é convergente, quando a diferença 
 | xk+1 - xk| 
for menor que uma precisão pré-fixada, encontramos um resultado aproximado dentro de
um intervalo de interesse.
2) no caso de sequê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. Para sequências decrescentes e convergentes
vale o análogo, com a raiz a esquerda das iteradas.
 
Condições suficientes para garantir a convergência da sequê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
a , ponto fixo de f 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 sequê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 f, 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 a uma raiz de uma função f , isolada num intervalo I = [a, b] e seja f uma função tal
que
f(a) = a. Se as seguintes hipóteses são verificadas:
i) f e f ' são funções contínuas em I;
ii) k = max| f'(x)| <1, x no intervalo [a,b]
iii) x0 pertence ao intervalo I e xn+1 = f(xn ), para k = 0, 1, 2,... pertencem ao
intervalo I
então, a sequência converge para a raiz a.
 
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 ideia utilizada para demonstrar a
convergência.
Provar que
xn -> a,
é equivalente a mostrar que o erro absoluto | xn - a | vai pra zero quando n vai pra
infinito,ou seja,
 | xn - a | -> 0 qdo n -> infinito.
Como
xn+1 = f(xn ) e a = f(a) ,
Substituindo na expressão do erro absoluto temos
 | xn - a| = | f(xn-1 ) - f(a) |,
Aplicando o (*)Teorema do Valor Médio à função f(temos por hipótese que é contínua
com derivada contínua)
| xn - a| = | f(xn-1 ) - f(a) | = | xn - a| = |f'(xn-1 )| | xn-1 - a|,
como a I e por (iii) xn-1 I , então xn-1 I e por (ii) temos que
 |f'(xn-1 )| £ k < 1.
Isto significa que
| xn - a| = |f'(xn-1 )| | xn-1 - a | £ k | xn-1 - a|,
ou seja o ponto xn está mais próximo da raiz que xn-1. Repetindo o procedimento, para |
xn-1 - a| temos:
| xn-1 - a| = |f '(xn-2)| | xn-2 - a| £k | xn-2 - a|,
Substituindo na expressão de | xn - a| temos:
| xn - a| = |f'(xn-1 )| | xn-1 - a | £ k | xn-1 - a| £ k2 | xn-2 - a| 
Repetindo o processo até atingirmos o chute inicial x0
| xn - a| = |f'(xn-1 )| | xn-1 - a | £ k | xn-1 - a| £ k2 | xn-2 - a| £ kn | x0 - a|
Portanto,
| xn - a|£ kn| x0 - a|, logo
lim (n-> )| xn - a| £ | x0 - a| lim (n-> )kn = 0
se k < 1.
A sequência das iteradas {xn}converge para a raiz a
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 f gera uma sequência convergente para uma raiz a, da
equação f(x)=0, você deve passar pelas seguintes etapas:
1 ) ISOLAR A RAIZ a: 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 f, A PARTIR DE f(x) = 0: em geral essa função f 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) f e f ' são funções contínuas em I: a expressão de f ' deve
ser calculada. Caso f e f ' 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.
ii) k = max| f'(x)| <1, x no intervalo [a,b]: estimar o valor
máximo da derivada e verificar que é inferior a 1
iii) x 0 I e xn+1 = f(xn ) I, para k = 0, 1, 2,...
 
Como garantir o item (iii), ou seja, que toda a sequência está contida no intervalo I
Escolhendo o extremo mais próximo da raiz podemos garantir que toda a seqüência gerada por f
pertence a I.
Como já foram verificados os itens (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,