Home » Materiais

Links

    Universidade de S�o Paulo

    Instituto de Matem�tica e Estat�stica

    LE�NIDAS DE OLIVEIRA BRAND�O
    DCC / IME / USP

    http://www.ime.usp.br/~leo

    Como calcular a forma fechada de qualquer s�rie, desde que polinomial!

    Uma t�cnica muito simples (desconsiderando a dificuldade de se resolver um sistema linear) para se computar ``formas fechadas'' polinomiais de s�ries, � montar (e resolver) um sistema linear associado � s�rie, de modo que o valor do polin�mio no ponto k coincida com a s�rie calculada at� o inteiro k.

    [ Isto pode ser generalizado usando fun��es quaisquer (al�m das fun��es polinomiais xk). Por exemplo, se sabemos que a ``formas fechadas'' da s�rie at� o inteiro k �   a0 + a1ek + a2 seno(k) + ... + aL k cos( k ),   podemos escrever L+1 equa��es igualando a s�rie e sua suposta ``formas fechadas''.]

    Vamos examinar com um pouco mais de cuidado esta t�cnica, apenas no caso de ``formas fechadas'' polinomiais. Seja

    , onde f(k)=alguma fun��o com dom�nio nos naturais.

    Se


    para computarmos os coeficientes de P(.), basta escrevermos L+1 equa��es, impondo identidades do tipo . Por raz�es de simplicidade, tomaremos estas L+1 equa��es a partir de 0, ou seja, faremos, , para k entre 0 e L. Como, neste exemplo, P(0)=a0=0, devemos procurar apenas os valores para os coeficientes a0, a1 at� aL.

    Observa��o: Se desconhecemos o valor L, devemos superestim�-lo, isto � tentar com valores grandes para L, de modo que os coeficientes de pot�ncia maior que o grau do polin�mio efetivo ser�o 0.

    Passo 0 Compute , para (L � qualquer ``chute grande'')

    Passo 1 Resolva o sistema linear, (aqui vale a0=0 sempre)



    Para se resolver este sistema, pode-se usar qualquer programa computacional adequado, em particular, poder�amos nos utilizarmos de PARI-GP. A seguir s�o apresentados dois exemplos de utiliza��o deste pacote, que dever�o ser bem entendidos para se poder fazer o exerc�cio proposto ao final.

    Matrizes no Pari-GP: Digite o exemplo abaixo no diret�rio C:\TRAB com o nome sist-l.txt. 

    \\ --------------------------------------------------------------------\\
\\ EXEMPLO: uso de matrizes, vetores e resolucao de sistemas lineares no
\\          PARI-GP
\\ Modo de usar este programa (sist-l.txt no diretorio C:\TRAB):
\\      F:\LABMAT\GP\> gp < c:\trab\sist-l.txt
\\ --------------------------------------------------------------------\\

\\ define matriz A e matriz coluna b
A=[1,-1,3; 0,1,2; 2,3,7];
b=[6;0;3];

print( Gauss(A,b) );
\\ define vetor solucao, e confere resultado!
x=Gauss( A,b );
print("A x = b ?");
print("A x = ",A*x);
print("b =",b);
\q

    Sistemas Lineares no PARI-GP: Digite o exemplo abaixo no diret�rio C:\TRAB com o nome pol2.txt. 

    \\ --------------------------------------------------------------------\\
\\ EXEMPLO: como listar os valores de um polin�mio aplicado aos primeiros
\\          naturais no PARI-GP
\\ Modo de usar este programa (pol2.txt no diretorio C:\TRAB):
\\      F:\LABMAT\GP\> gp < c:\trab\pol2.txt
\\ --------------------------------------------------------------------\\

Ng=4;
x=[0,0,0,0,1];
for (j=1,10, aux=0;for(k=0,Ng,aux=aux+x[k+1]*j^k);print("p(",j,")=",aux));
\q

    Exerc�cio: Tente obter as ``formas fechadas'' para as s�ries abaixo apresentadas, fazendo quatro arquivos .txt (um para cada s�rie), com comando PARI-GP (vide os exemplos), que fa�am:

    • compute os coeficientes do polin�mio;
    • imprima a verifica��o da solu��o do sistema linear (como no primeiro exemplo, o ...confere resultado!)
    • imprima a verifica��o de corretude do polin�mio PARA A S�RIE, considerando os 15 primeiros naturais (como equematizado abaixo) 

          for( j=0,15, calcule_s�rie_at�_j_para_S; calcule_pol_em_j_para_aux;
         print1(j," Serie=",S,"P(",j,")=",aux))

    As s�ries s�o:



    Observa��o: Se chegou a conclus�o que alguma das s�ries n�o pode ser escrita como um polin�mio, apresente um CONTRA-EXEMPLO, isto �, SE o polin�mio foi computado corretamente (para valores muito grande de L - indique o �ltimo que computou) e existe algum ponto , ,   apresente estes valores.

    Solu��o:   

    \\ Exemplo de program Pari-GP: 25/08/1997
\\ --------------------------------------
\\ Encontra "formas fechadas" para series que tenham "solucao" polinomial
\\ Usa sistemas lineares
\\  Se         S(k):=f(0)+f(1)+ ... +f(k)  e 
\\   existem   L  e  P(j):=a_0 + a_1 j + a_2 j^2 +...+ a_L j^L, 
\\   tais que  S(j)=P(j), para todo j natural
\\                 
\\  Entao       A x = b, onde x[i]=a_i,  b[i]=S(i)  e
\\              _              _   _   _     _   _
\\             |1 0 0   ... 0   | | a_0 |   | b_0 |
\\             |1 1 1   ... 1   | | a_1 |   | b_1 |
\\             |1 2 2^2 ... 2^L | | a_2 | = | b_2 |
\\             |. . .           | | ... |   | ... |
\\             |1 L L^2 ... L^L | | a_L |   | b_L |
\\              -              -   -   -     -    -

\\ Define a serie S(k)
   [ f(n) = n^2 ]:
 
\\ "Chute" para o valor L => constroe matriz A[.,.]
   L = 10

   \\print(A):
   \\ No GP:  0^0=1
   \\ A=[ 1,0,0,  ...,0  ;
   \\     1,1,1,  ...,1  ; 
   \\     1,2,2^2,...,2^L; 
   \\     ...
   \\     1,L,L^2,...,L^L]:

\\ Constroe vetor b => b[i] = f(0) + f(1) + ... + f(i)
   b = vector( L+1, x, sum(0, n=0, x-1, f(n) ) ):
   \\print(b):

\\ Encontra os coeficientes do polinomio P(.)
   x=gauss(A,b): print():
   print("Coeficientes:",x):

\\ Confere se a solucao encontrada coincide com os valores da serie
   print("Para conferir Resultado: Serie efetiva  x  Pol. Calculado "):
   print("       Serie  Polinomio"):
   s=0:

   for(j=1,10,
         s=s+f(j):
         print1("j=",j," | S=",s,"     "):
         aux=0:
         for(k=1,L+1,
               aux=0:
               for(k=1,L+1,
                     aux=aux+x[k]*j^(k-1)
                  ):
               print(aux)
             )
       ):

\q