Baixe o app para aproveitar ainda mais
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
Compartilhar