[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75. zeilberger


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.1 Introdução a zeilberger

zeilberger é uma implementação do algorítmo de Zeilberger para somatório hipergeométricos definidos, e também para o algorítmo de Gosper para somatórios hipergeométricos indefinidos.

zeilberger faz uso do método de otimização "filtering" desenvolvido por Axel Riese.

zeilberger foi desenvolvido por Fabrizio Caruso.

load (zeilberger) torna esse pacote disponível para uso.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.1.1 O problema dos somatórios hipergeométricos indefinidos

zeilberger implementa o algorítmo de Gosper para somatório hipergeométrico indefinido. Dado um termo hipergeométrico F_k em k queremos encontrar sua anti-diferença hipergeométrica, isto é, um termo hipergeométrico f_k tal que F_k = f_(k+1) - f_k.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.1.2 O problema dos somatórios hipergeométricos definidos

zeilberger implementa o algorítmo de Zeilberger para somatório hipergeométrico definido. Dado um termo hipergeométrico apropriado (em n e k) F_(n,k) e um inteiro positivo d queremos encontrar um d-ésima ordem de recorrência linear com coeficientes polinomiais (em n) para F_(n,k) e uma função racional R em n e k tal que

a_0 F_(n,k) + ... + a_d F_(n+d),k = Delta_K(R(n,k) F_(n,k))

onde Delta_k é o k-seguinte operador de diferença, i.e., Delta_k(t_k) := t_(k+1) - t_k.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.1.3 Níveis de detalhe nas informações

Existe também versões de níveis de detalhe fornecidos pelos comandos que são chamados (os níveis) através da adição de um dos seguintes prefixos:

Summary

Apenas um sumário é mostrado no final

Verbose

Algumas informações nos passos intermediários

VeryVerbose

Muita informação

Extra

Muito mais informação incluindo informação sobre o sistema linear no algorítmo de Zeilberger

Por exemplo: GosperVerbose, parGosperVeryVerbose, ZeilbergerExtra, AntiDifferenceSummary.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.2 Funções e Variáveis Definidas para zeilberger

Função: AntiDifference (F_k, k)

Retorna a anti-diferença hipergeométrica de F_k, se essa anti-diferença. De outra forma AntiDifference retorna no_hyp_antidifference.

Função: Gosper (F_k, k)

Retorna o certificado racional R(k) para F_k, isto é, uma função racional tal que

F_k = R(k+1) F_(k+1) - R(k) F_k

se essa função racional exitir. De outra forma, Gosper retorna no_hyp_sol.

Função: GosperSum (F_k, k, a, b)

Retorna o somatório de F_k de k = a a k = b se F_k tiver ma diferença hipergeométrica. De outra forma, GosperSum retorna nongosper_summable.

Exemplos:

(%i1) load (zeilberger);
(%o1)  /usr/share/maxima/share/contrib/Zeilberger/zeilberger.mac
(%i2) GosperSum ((-1)^k*k / (4*k^2 - 1), k, 1, n);

Dependent equations eliminated:  (1)
                           3       n + 1
                      (n + -) (- 1)
                           2               1
(%o2)               - ------------------ - -
                                  2        4
                      2 (4 (n + 1)  - 1)
(%i3) GosperSum (1 / (4*k^2 - 1), k, 1, n);
                                3
                          - n - -
                                2       1
(%o3)                  -------------- + -
                                2       2
                       4 (n + 1)  - 1
(%i4) GosperSum (x^k, k, 1, n);
                          n + 1
                         x          x
(%o4)                    ------ - -----
                         x - 1    x - 1
(%i5) GosperSum ((-1)^k*a! / (k!*(a - k)!), k, 1, n);
                                n + 1
                a! (n + 1) (- 1)              a!
(%o5)       - ------------------------- - ----------
              a (- n + a - 1)! (n + 1)!   a (a - 1)!
(%i6) GosperSum (k*k!, k, 1, n);

Dependent equations eliminated:  (1)
(%o6)                     (n + 1)! - 1
(%i7) GosperSum ((k + 1)*k! / (k + 1)!, k, 1, n);
                  (n + 1) (n + 2) (n + 1)!
(%o7)             ------------------------ - 1
                          (n + 2)!
(%i8) GosperSum (1 / ((a - k)!*k!), k, 1, n);
(%o8)                  nonGosper_summable
Função: parGosper (F_{n,k}, k, n, d)

Tenta encontrar uma recorrência de d-ésima ordem para F_{n,k}.

O algorítmo retorna uma seqüência [s_1, s_2, ..., s_m] de soluções. Cada solução tem a forma

[R(n, k), [a_0, a_1, ..., a_d]]

parGosper retorna [] caso não consiga encontrar uma recorrência.

Função: Zeilberger (F_{n,k}, k, n)

Tenta calcular o somatório hipergeométrico indefinido de F_{n,k}.

Zeilberger primeiro invoca Gosper, e se Gosper não conseguir encontrar uma solução, então Zeilberger invoca parGospercom ordem 1, 2, 3, ..., acima de MAX_ORD. Se Zeilberger encontrar uma solução antes de esticar MAX_ORD, Zeilberger para e retorna a solução.

O algorítmo retorna uma seqüência [s_1, s_2, ..., s_m] de soluções. Cada solução tem a forma

[R(n,k), [a_0, a_1, ..., a_d]]

Zeilberger retorna [] se não conseguir encontrar uma solução.

Zeilberger invoca Gosper somente se gosper_in_zeilberger for true.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.3 Variáveis globais gerais

Variável global: MAX_ORD

Valor padrão: 5

MAX_ORD é a ordem máxima de recorrência tentada por Zeilberger.

Variável global: simplified_output

Valor padrão: false

Quando simplified_output for true, funções no pacote zeilberger tentam simplificação adicional da solução.

Variável global: linear_solver

Valor padrão: linsolve

linear_solver nomeia o resolvedor que é usado para resolver o sistema de equações no algorítmo de Zeilberger.

Variável global: warnings

Valor padrão: true

Quando warnings for true, funções no pacote zeilberger imprimem mensagens de alerta durante a execução.

Variável global: gosper_in_zeilberger

Valor padrão: true

Quando gosper_in_zeilberger for true, a função Zeilberger chama Gosper antes de chamar parGosper. De outra forma, Zeilberger vai imediatamente para parGosper.

Variável global: trivial_solutions

Valor padrão: true

Quando trivial_solutions for true, Zeilberger retorna soluções que possuem certificado igual a zero, ou todos os coeficientes iguais a zero.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

75.4 Variáveis relacionadas ao teste modular

Variável global: mod_test

Valor padrão: false

Quando mod_test for true, parGosper executa um teste modular discartando sistemas sem solução.

Variável global: modular_linear_solver

Valor padrão: linsolve

modular_linear_solver nomeia o resolvedor linear usado pelo teste modular em parGosper.

Variável global: ev_point

Valor padrão: big_primes[10]

ev_point é o valor no qual a variável n é avaliada no momento da execução do teste modular em parGosper.

Variável global: mod_big_prime

Valor padrão: big_primes[1]

mod_big_prime é o módulo usado pelo teste modular em parGosper.

Variável global: mod_threshold

Valor padrão: 4

mod_threshold is the maior ordem para a qual o teste modular em parGosper é tentado.


[ << ] [ >> ]           [Top] [Contents] [Índice] [ ? ]

This document was generated by Jaime Villate on Outubro, 14 2014 using texi2html 1.76.