2011/2/8 Henrique Rennó <[email protected]>:
> 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?
Bom, lendo a minha solução (ou a do Luís), você tem uma fórmula. Eu
vou explicar a minha, porque eu entendo melhor ;-) (a do Luís me faz
pensar muito em Fibonacci, com os conjugados 1+U e 1-U aparecendo,
(1+U)(1-U) = 1 - U^2 = 1 - 2 = -1, o que dá uma equação do segundo
grau, e o "fator do termo dominante" é U)
Lembra da equação do limite, L = 1 + 1/(1+ L) ? (ou a outra, 3 + 2L =
3 + 4/L, na ordem dois, mais é mais difícil "voltar"). Bom, essa
equação tem raízes +- raiz(2). Se você quisesse ter +- raiz(3), o quê
fazer ? Bom, faça tudo ao contrário:
L = +- raiz(3)
L^2 = 3
L^2 - 1 = 2
(L+1)(L-1) = 2
L - 1 = 2/(L+1)
L = 1 + 2/(L+1)
Agora, lembre que a gente tinha que um dos L era y_{n+1}/x_{n+1},
enquanto o outro era y_n/x_n (e no limite era igual). Devolvendo isso
na formuleta:
y_{n+1}/x_{n+1} = 1 + 2/(y_n/x_n + 1) = 1 + 2 x_n/(x_n + y_n) = (y_n +
3 x_n)/(y_n + x_n).
Isso dá uma recorrência possível (mas certamente não todas!).
Bom, parece que a gente tem uma fórmula para calcular essas raízes, né ?
y_{n+1} = y_n + N x_n
x_{n+1} = y_n + x_n
L = 1 + (N-1)/(L - 1) <=> L^2 - 1 = N - 1.
Eu acredito que fazendo uma análise semelhante à que eu fiz (ou o
Luís... a fórmula dele deve ser praticamente a mesma, agora com U =
raiz(N), se você começar ainda com 1/1) você consegue provar que a
seqüência y_n/x_n converge.
Bom, agora vamos voltar à realidade (ou seja, você usa um algoritmo
desses para calcular aproximações). Note que (graças à solução do
Luís) a gente vê que a convergência é geométrica: o erro na etapa n é,
aproximadamente, (U-1)^n/(U+1)^n, que tende a zero (U = raiz(N),
enfim, parece... não acredito que possa ser outra coisa vista a
solução do Luís, o fato que é uma recorrência de segunda ordem, etc,
etc, mas sei lá). O método de Newton, por outro lado, converge muito
mais rapidamente, com um erro do tipo t^(n^2), com 0 < t < 1. A gente
chama de convergência quadrática, é meio enganoso, o erro não é 1/n^2,
mas exp(-Kn^2) em vez de exp(-Kn). Isso porque o erro na etapa n+1 é
aproximadamente o quadrado do erro da etapa n. E quando o erro é
pequeno, elevar ao quadrado é muito, mas muito mais rápido do que
dividir por uma constante (como eu "mais ou menos" disse que dava pra
mostrar no caso da recorrência). Uma forma de ver isso é que as casas
decimais vão ficando exatas "uma a uma" no caso de uma convergência
geométrica, enquanto no método de Newton o número de casas decimais
certas aproximadamente *dobra* a cada iteração. A única vantagem desse
método aqui é que, formando sequências "alternantes", você consegue
uma estimativa do erro : você sabe que *sempre* vai convergir (ao
contrário do método de Newton, que você tem que *primeiro*, provar que
vai estar na região de convergência - ok, não deve ser muito difícil
mostrar que o método de Newton para x^2 = N converge sempre para um
valor inicial igual a 1, por exemplo, olhando no gráfico, mas pense
"em geral"), e o erro é menor do que a diferença de dois termos
consecutivos.
Ah, e falando em "convergência", frações e recorrência, me passou pela
cabeça que (pode ser que) esse teu método calcule aproximações em
frações parciais... Seria legal provar isso ! (ou mostrar que eu
chutei longe demais)
Um grande abraço
--
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
=========================================================================
