Na verdade, gostaria de saber como pode ser encontrado que
x_{n+1} = x_n + y_n
y_{n+1} = 2*x_n + y_n
são as fórmulas recursivas de modo que a sequência possa convergir
para raíz_quadrada(2). Se ao invés de raíz_quadrada(2) fosse
raíz_quadrada(3), qual seria a recorrência?
2011/2/8 Bernardo Freitas Paulo da Costa <[email protected]>:
> 2011/2/8 Henrique Rennó <[email protected]>:
>> Na sequência 1/1, 3/2, 7/5, 17/12, 41/29, ..., o denominador de cada
>> termo a partir do segundo é a soma do numerador mais denominador
>> anterior e o numerador é a soma de duas vezes o denominador mais
>> numerador anterior. Essa sequência converge para raíz_quadrada(2).
>> Como isso pode ser demonstrado?
> Oi Henrique. Uma das coisas importantes nesse tipo de problemas é "dar
> nome aos burros". Assim, seja x_n a seqüência dos denominadores, y_n a
> dos numeradores. Você quer calcular o limite y_n/x_n. Agora, veja que
> você tem uma recorrência de x_n e y_n em função deles mesmos. Veja que
> dá
>
> x_{n+1} = x_n + y_n
> y_{n+1} = 2*x_n + y_n
>
> Mas o que você quer é o quociente. Vejamos o que dá pra fazer com y_n+1/x_n+1:
>
> y_{n+1}/x_{n+1} = ( 2*x_n + y_n ) / (x_n + y_n ) = 1 + x_n / (x_n +
> y_n ) = 1 + 1/(1 + y_n/x_n)
>
> Agora, *se* existir um limite L para y_n/x_n, será o mesmo que para
> y_{n+1}/x_{n+1}. Isso dá uma equação do segundo grau em L, você
> resolve, e pronto.
>
> Mas isso ainda não prova que converge ! Para provar a convergência, é preciso
> 1/ Fazer as contas com épsilons e n >= N, e ver que dá certo pra todo
> épsilon, ou
> 2/ Tentar mostrar uma propriedade que faça a convergência ficar clara.
>
> Eu deixo você provar usando o método 1 (não é tão difícil assim: uma
> vez que você sabe qual é o limite, é mais uma questão de estimar o
> erro na etapa n, e tentar calcular como ele vai diminuir quando você
> fizer a próxima operação! Dica: estime (y_n/x_n)^2 - 2 a cada vez,
> você vai ver que o erro divide por mais do que 3).
>
> O método 2 é o seguinte: veja que a seqüência é limitada: 0 < x_n <
> y_n < 2*x_n (veja que y_{n+1} = 2x_n + y_n < 2(x_n + y_n) =
> 2*x_{n+1}), o que quer dizer que y_n/x_n está sempre entre 1 e 2. Bom,
> a idéia é tentar provar que a seqüência é monótona (a gente não tem
> tanto teorema assim que ajuda a provar a convergência das coisas...).
> Mas nem vale a pena tentar: 1/1=1, 3/2=1,5, 7/5 = 1,4, e o outro 17/12
> é muito chato pra fazer de cabeça. Mas você pode tentar outra coisa...
> ela pode ficar "oscilando" em volta do limite.
>
> Vamos calcular y_{n+2}/x_{n+2} (nunca perca a coragem, e até agora as
> contas foram poucas!)
> Isso dá (4 x_n + 3 y_n)/(3 x_n + 2 y_n). Fatorando y_n/x_n (afinal, é
> com o quê a gente quer comparar), obtemos y_{n+2}/x_{n+2} = (y_n/x_n)
> * (3 + 4 x_n/y_n) / (3 + 2 y_n/x_n). O que dá um fator multiplicativo
> (3 + 4/a) / (3 + 2a), onde a = y_n/x_n. Suponha que a > raiz(2). Neste
> caso, a*a > 2, logo 2a > 4/a, o que faz um fator menor do que 1. Por
> outro lado, se a < raiz(2), o fator é maior do que 1.
>
> O que quer dizer que temos quase tudo para ter uma seqüência que fica
> "oscilando" entre o limite raiz(2).
>
> Falta só provar que o y_{n+2}/x_{n+2} continua menor do que raiz(2),
> mesmo depois de aumentar, se y_n/x_n for menor do que raiz(2), e
> reciprocamente no outro caso. Isso é fácil de ver assim : suponha que
> y_n/x_n < raiz(2). Vejamos o que acontece com y_{n+1}/x_{n+1} = 1 +
> 1/(1 + y_n/x_n) > 1 + 1/(1 + raiz(2)) = 1 + (raiz(2) - 1)/(2-1) =
> raiz(2). Oba! E como mudando y_n/x_n > raiz(2) a desigualdade na
> recorrência muda de sinal, a gente provou:
> 1/ A seqüência fica alternadamente maior / menor do que raiz(2)
> 2/ A cada duas etapas (ou seja, quando o sinal volta a ser o mesmo),
> está mais perto
> 3/ Agora, pegue o limite de cada uma das seqüências (a crescente e a
> decrescente, par / ímpar se você prefere), que existe porque é
> limitado e monótono (O teorema), eles satisfazem a mesma equação L =
> L(3 + 4/L)/(3 + 2L), ou seja 3 + 4/L = 3 + 2L, ou seja L^2 = 2, e são
> ambos positivos. Fim!
>
>
> Depois de escrever isso tudo, eu acho que o método 1 foi o mais
> fácil... (ok, precisa da idéia dos quadrados, mas é bastante razoável,
> né?). A vantagem do método 2 é que ele funciona em muitos casos em que
> é difícil obter uma estimativa da convergência!
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================
>
--
Henrique
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
