[obm-l] Re: [obm-l] Re: [obm-l] Convergência uniforme
2013/1/8 Artur Costa Steiner steinerar...@gmail.com: Legal Bernardo! Vc está dizendo que se f_n é uma sequência de holomorfas, uniformemente limitadas por um M em um compacto K, que convirja neste conjunto para uma função f, então a convergência é uniforme? É essa a idéia? Isso mesmo. Escreva o que aconteceria se a convergência não fosse uniforme (uma seqüência x_n vai aparecer, o que é bom porque K é compacto). Agora, tente lembrar dos contra-exemplos clássicos de convergência uniforme e veja que uma derivada vai explodir. Mas a fórmula de Cauchy garante que, longe do bordo de K, a derivada não pode explodir. 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 =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Convergência de Matriz
nao vale para a matriz 2x2 0 1 1 0 se for o caso, é corolário do Perron–Frobenius para matrizes irredutiveis (que nao é o caso do exemplo acima) http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Perron.E2.80.93Frobenius_theorem_for_irreducible_matrices On Sun, Nov 20, 2011 at 7:52 AM, Artur Costa Steiner steinerar...@gmail.com wrote: E as colunas são iguais ao auto-vetor correspondente ao auto-valor 1 tal que a soma das componentes é 1. Artur Artur Costa Steiner Em 19/11/2011 00:10, Willy George Amaral Petrenko wgapetre...@gmail.com escreveu: Esse problema é meio complicado, mas ele é um corolário desse teorema: http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem 2011/11/17 Henrique Rennó henrique.re...@gmail.com Suponha a matriz [aij]mxm, onde cada aij representa a probabilidade de um evento i levar a um evento j e aij 0 para todo i,j. Calculando as potências dessa matriz, é possível provar que ela converge para uma matriz P em que todas as colunas são iguais? Vi essa propriedade no livro Álgebra Linear do Boldrini, na parte sobre cadeias de Markov. -- 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 =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Convergência de Matriz
Repare que parte do problema é: aij 0 para todo i,j 2011/11/22 Jaare Oregim jaare.ore...@gmail.com nao vale para a matriz 2x2 0 1 1 0 se for o caso, é corolário do Perron–Frobenius para matrizes irredutiveis (que nao é o caso do exemplo acima) http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Perron.E2.80.93Frobenius_theorem_for_irreducible_matrices On Sun, Nov 20, 2011 at 7:52 AM, Artur Costa Steiner steinerar...@gmail.com wrote: E as colunas são iguais ao auto-vetor correspondente ao auto-valor 1 tal que a soma das componentes é 1. Artur Artur Costa Steiner Em 19/11/2011 00:10, Willy George Amaral Petrenko wgapetre...@gmail.com escreveu: Esse problema é meio complicado, mas ele é um corolário desse teorema: http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem 2011/11/17 Henrique Rennó henrique.re...@gmail.com Suponha a matriz [aij]mxm, onde cada aij representa a probabilidade de um evento i levar a um evento j e aij 0 para todo i,j. Calculando as potências dessa matriz, é possível provar que ela converge para uma matriz P em que todas as colunas são iguais? Vi essa propriedade no livro Álgebra Linear do Boldrini, na parte sobre cadeias de Markov. -- 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 =
[obm-l] Re: [obm-l] Re: [obm-l] Convergência de Matriz
E as colunas são iguais ao auto-vetor correspondente ao auto-valor 1 tal que a soma das componentes é 1. Artur Artur Costa Steiner Em 19/11/2011 00:10, Willy George Amaral Petrenko wgapetre...@gmail.com escreveu: Esse problema é meio complicado, mas ele é um corolário desse teorema: http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem 2011/11/17 Henrique Rennó henrique.re...@gmail.com Suponha a matriz [aij]mxm, onde cada aij representa a probabilidade de um evento i levar a um evento j e aij 0 para todo i,j. Calculando as potências dessa matriz, é possível provar que ela converge para uma matriz P em que todas as colunas são iguais? Vi essa propriedade no livro Álgebra Linear do Boldrini, na parte sobre cadeias de Markov. -- Henrique
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Convergência de pi
Agora, lembre que (a+1)(a-1) = a^2 - 1, logo n/d é crescente nos k
pares, e decrescente nos k ímpares. Como a seqüência dos ímpares é
decrescente e limitada por 0, ela converge; seja L o seu limite. Como
o quociente dos pares pelos ímpares é (n+1)/n, que tende a 1, o limite
da seqüência dos pares existe também, e é o mesmo.
O quociente dos pares pelos ímpares seria n/(n+1), que tende a 1, com
n tendendo ao infinito. Não entendi por que sabendo que o quociente
dos pares pelos ímpares converge, conclui-se que o limite da sequência
dos pares é o mesmo que o da sequência dos ímpares.
Seja p_n a seqüência dos pares, i_n a seqüência dos ímpares.
Seja I = limite i_n, que a gente sabe que existe.
Então p_n = i_n * n/(n+1), e como ambos os limites de i_n e n/(n+1)
existem, o limite do produto existe e vale o produto dos limites (se
você nunca provou isso, é um exercício legal de somar e subtrair o
termo do meio para fazer aparecerem os limites que você quer: a_n *
b_n - A*B = a_n (b_n - B) + B*(a_n - A), e como a_n é limitado por ter
um limite finito, você pode concluir). Assim, lim p_n = lim i_n * lim
n/(n+1) = I * 1 = I.
Agora note que I_n - I_{n+1} é muito pequeno, e tende a zero. Mas por
um lado I_0 = pi, e I_1 = 1, logo fazendo o produto até a etapa n,
você vê que tem uma relação entre pi e 1 dada por um monte de produtos
de cada lado. Passe todo mundo pro lado do 1, e você terá as suas
recorrências.
Bom, ninguém reparou que aqui tem um argumento errado, então eu vou
dizer: I_n e I_{n+1} tendem as duas para zero, logo não é de se
espantar que a diferença também tenda a zero. O que é mais legal é
provar que a diferença é muito menor do que o valor da integral, e
portanto quando a gente passar pro outro lado vai dar certo. Idéia:
veja que ser sin(x)^n não é tão importante assim para estimar a
diferença. Prove primeiro que a diferença é muito menor do que o
valor para J_n = integral de -1 a 1 |x^n| dx (ou seja, (J_n -
J_{n+1})/J_n tende a zero), e depois descubra como adaptar a mesma
coisa - talvez até com um teorema genérico - para sin(x) que é a
valores em [-1,1].
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
=
[obm-l] Re: [obm-l] Re: [obm-l] Convergência de pi
2011/2/18 Bernardo Freitas Paulo da Costa bernardo...@gmail.com:
2011/2/17 Henrique Rennó henrique.re...@gmail.com:
A sequência $\frac{4}{1}, \frac{8}{3}, \frac{32}{9}, \frac{128}{45},
\frac{768}{225}, ...$ converge para pi muito lentamente. Sendo o
primeiro termo $a_1$, o segundo $a_2$ etc, a partir do segundo termo,
cada termo de índice par é igual ao termo anterior multiplicado por
$\frac{n}{n+1}$ e cada termo de índice ímpar é igual ao termo anterior
multiplicado por $\frac{n+1}{n}$, onde n é o índice. Como pode ser
demonstrada essa convergência?
Estou utilizando a notação do LaTeX. Caso usem o gmail, existe o
GmailTeX que pode ser instalado e ativado para visualizar os dados
acima.
Henrique, nada (mas absolutamente nada) contra o TeX. Mas um pouco
contra o uso forçado do Gmail: veja bem, se você dependesse de algo
que funcionasse no yahoo ? Puxando a analogia um pouco mais: pense no
futuro. Um mail em ASCII é como um livro, todos lêem. Um treco que
depende de montes de plugins e um webmail em particular, é como um
disquete de 5 1/2. Ninguém mais consegue ler hoje em dia. Eu tô
falando isso também porque acho meio exagerado você usar \frac etc e
tal em vez de simplesmente 4/1, 8/3, 32/9, 128/45, ... que me parece
muito melhor para todos. Inclusive os jovens da lista que nunca
ouviram falar de LaTeX, usam um e-mail no computador dos pais e
sabe-se lá se eles podem instalar um treco (ou se é que eles *sabem* o
que é isso).
Bom, isso dito, vamos à matemática.
Você tem duas seqüências, n_k e d_k (n = numerador, d = denominador).
n_1 = 4, d_1 = 1.
você tem duas recorrências, uma para os pares, outra para os ímpares. Veja:
n_{2k} = n_{2k-1} * 2k
d_{2k} = d_{2k-1} * (2k+1)
n_{2k+1} = n_{2k} * (2k+2)
d_{2k+1} = d_{2k} * (2k+1)
Assim,
n_{2k+2} = (2k+2) * n_{2k+1} = (2k+2)^2 n_{2k}
d_{2k+2} = (2k+3) * n_{2k+1} = (2k+3)*(2k+1) d_{2k}
n_{2k+1} = (2k+2) * n_{2k} = (2k+2)*2k * n_{2k-1}
d_{2k+1} = (2k+1) * d_{2k} = (2k+1)^2 * d_{2k-1}
Agora, lembre que (a+1)(a-1) = a^2 - 1, logo n/d é crescente nos k
pares, e decrescente nos k ímpares. Como a seqüência dos ímpares é
decrescente e limitada por 0, ela converge; seja L o seu limite. Como
o quociente dos pares pelos ímpares é (n+1)/n, que tende a 1, o limite
da seqüência dos pares existe também, e é o mesmo.
O quociente dos pares pelos ímpares seria n/(n+1), que tende a 1, com
n tendendo ao infinito. Não entendi por que sabendo que o quociente
dos pares pelos ímpares converge, conclui-se que o limite da sequência
dos pares é o mesmo que o da sequência dos ímpares.
Bom, agora eu suponho que você quer na verdade que eu mostre que L =
pi. Isso é mais complicado. Esse produto infinito é conhecido de antes
do cálculo, e se chama Produto de Wallis. Uma forma de mostrar isso
é o seguinte:
- sin(x) tem raízes 0, +- pi, +- 2pi, +- 3pi, etc, etc.
- sin(x)/x tem raízes simétricas, portanto é uma função de x^2
- sin(x)/x = 1 em x = 0
Assim, você pode tentar escrever o produto infinito
sin(x)/x = (1 - x^2 / pi^2)*(1 - x^2 / 4pi^2)*(1 - x^2 / 9pi^2)* ...
(veja que ambos os lados se anulam somente para x = +- pi, +- 2pi, ...
e que ambos valem 1 em x = 0. Essa belíssima idéia de comparar uma
função com infinitos zeros e um polinômio em (1 - x/raiz) é do Euler:
em vez de fazer (x - raiz) como a gente está acostumado, fazer (1 -
x/raiz) garante que o limite vai dar certo pelo menos para x = 0; isso
é o ponto crucial da demonstração de que ambos os lados são realmente
iguais).
Agora, substitua x = pi/2 nessa fórmula. Porquê ? Porque primeiro o
seno vai ser um número inteiro (a gente podia tentar pi/6 também, mas
o 6 não aparece tanto assim na sua fórmula para valer a pena, e os
outros ou são irracionais em pi, ou são de seno irracional). sin(pi/2)
= 1, e a fórmula fica
2/pi = (1 - 1/4) * (1 - 1/16) * (1 - 1/36) * ... = Produto(4n^2 - 1)/(4n^2).
Agora, é só expandir os n_k e d_k em ímpares / pares e ver que vai dar
certo.
Uma outra forma de demonstrar isso, que você deve ter visto num curso
de cálculo, é calcular as integrais de sin(x)^n, por indução, usando
sin(x)^2 = 1 - cos(x)^2 para criar um fator integrante. Daí você faz
uma integração por partes com
u = sin(x)^{n-2}*cos(x) e
dv = cos(x)dx
e daí vai aparecer um cos(x)^2. Que você transforma (de novo...) em 1
- sin(x)^2. Se você integrar de 0 a pi, isso dá uma fórmula de
recorrência
I_n = (n-1)/n I_{n-2} onde I_n = integral de 0 a pi sin(x)^n dx.
Agora note que I_n - I_{n+1} é muito pequeno, e tende a zero. Mas por
um lado I_0 = pi, e I_1 = 1, logo fazendo o produto até a etapa n,
você vê que tem uma relação entre pi e 1 dada por um monte de produtos
de cada lado. Passe todo mundo pro lado do 1, e você terá as suas
recorrências.
De qualquer forma, as demonstrações demandam um pouco de trabalho
porque você tem que ver que os produtos para os quais você tem uma
fórmula dão o mesmo resultado que o n_k/d_k. O mais legal é que,
[obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Convergência
Sauda,c~oes,
Com mais tempo resolvi o sistema em diferenças e expressei
a_n numa forma fechada: Se U=\sqrt{2}, então
a_n = \frac{U(1+U)^n + U(1-U)^n}{(1+U)^n - (1-U)^n}
E lim a_n = U.
Esta é a solução bruta. A(s) do Bernardo é a elegante.
[]'s
Luís
From: qed_te...@hotmail.com
To: obm-l@mat.puc-rio.br
Subject: [obm-l] RE: [obm-l] Re: [obm-l] Convergência
Date: Tue, 8 Feb 2011 18:24:40 +
Sauda,c~oes,
Obrigado Bernardo por tal solução. Devemos reconhecer
e apreciar a colaboração (muitas) de membros como você.
Eu procederia da seguinte maneira: seja o sistema
x_{n+1} = x_n + y_n
y_{n+1} = 2*x_n + y_n
Resolvendo o sistema acima (alguém sabe como fazer isso?)
obtemos x_n e y_n e daí a_n = y_n/x_n.
Então tendo a_n usamos um daqueles testes manjados para
testar a convergência de séries (positivas). Será que daria certo?
[]'s
Luís
Date: Tue, 8 Feb 2011 16:54:04 +0100
Subject: [obm-l] Re: [obm-l] Convergência
From: bernardo...@gmail.com
To: obm-l@mat.puc-rio.br
2011/2/8 Henrique Rennó henrique.re...@gmail.com:
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
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Convergência
2011/2/8 Henrique Rennó henrique.re...@gmail.com:
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
=
[obm-l] Re: [obm-l] Re: [obm-l] Convergência
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 bernardo...@gmail.com:
2011/2/8 Henrique Rennó henrique.re...@gmail.com:
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
=
[obm-l] RE: [obm-l] Re: [obm-l] Convergência
Sauda,c~oes,
Obrigado Bernardo por tal solução. Devemos reconhecer
e apreciar a colaboração (muitas) de membros como você.
Eu procederia da seguinte maneira: seja o sistema
x_{n+1} = x_n + y_n
y_{n+1} = 2*x_n + y_n
Resolvendo o sistema acima (alguém sabe como fazer isso?)
obtemos x_n e y_n e daí a_n = y_n/x_n.
Então tendo a_n usamos um daqueles testes manjados para
testar a convergência de séries (positivas). Será que daria certo?
[]'s
Luís
Date: Tue, 8 Feb 2011 16:54:04 +0100
Subject: [obm-l] Re: [obm-l] Convergência
From: bernardo...@gmail.com
To: obm-l@mat.puc-rio.br
2011/2/8 Henrique Rennó henrique.re...@gmail.com:
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
=
