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

72. zeilberger


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

72.1 Introdução a zeilberger

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

zeilberger faz uso do método de optimizaçã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] [ ? ]

72.1.1 O problema dos somatórios hipergeométricos indefinidos

zeilberger implementa o algoritmo 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] [ ? ]

72.1.2 O problema dos somatórios hipergeométricos definidos

zeilberger implementa o algoritmo 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] [ ? ]

72.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 intermédios

VeryVerbose

Muita informação

Extra

Muito mais informação incluindo informação sobre o sistema linear no algoritmo de Zeilberger

Por exemplo: GosperVerbose, parGosperVeryVerbose, ZeilbergerExtra, AntiDifferenceSummary.


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

72.2 Definições 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 algoritmo retorna uma sequê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 algoritmo retorna uma sequê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] [ ? ]

72.3 Variáveis globais gerais

Variável global: MAX_ORD

Valor por omissão: 5

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

Variável global: simplified_output

Valor por omissã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 por omissão: linsolve

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

Variável global: warnings

Valor por omissã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 por omissã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 por omissã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] [ ? ]

72.4 Variáveis relacionadas ao teste modular

Variável global: mod_test

Valor por omissão: false

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

Variável global: modular_linear_solver

Valor por omissão: linsolve

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

Variável global: ev_point

Valor por omissã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 por omissão: big_primes[1]

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

Variável global: mod_threshold

Valor por omissã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, 19 2014 using texi2html 1.76.