El algoritmo de Petkovše es un algoritmo de álgebra computacional que calcula una solución en base de términos hipergeométricos de su ecuación de recurrencia lineal de entrada con coeficientes polinómicos . Igualmente, calcula un factor derecho de primer orden de operadores de diferencias lineales con coeficientes polinómicos. Este algoritmo fue desarrollado por Marko Petkovšek en su tesis doctoral de 1992. El algoritmo está implementado en todos los principales sistemas de álgebra computacional.
Representación de Gosper-Petkovšek Sea un campo de característica cero. Una secuencia no nula es hipergeométrica si . El algoritmo de Petkovšek utiliza como concepto clave que esta función racional tiene una representación específica, a saber, la forma normal de Gosper-Petkovšek . Sea una función racional no nula, entonces existen polinomios mónicos y de tal manera que
y
para cada entero no negativo , y .
Esta representación de se llama forma normal de Gosper-Petkovšek, que se pueden calcular explícitamente. Esta construcción de la representación es una parte esencial del algoritmo de Gosper . Petkovšek añadió las condiciones 2. y 3 de esta representación que hace que esta forma normal sea única.
Algoritmo Utilizando la representación de Gosper-Petkovšek, se puede transformar la ecuación de recurrencia original en una ecuación de recurrencia para una sucesión polinómica. . Los otros polinomios pueden tomarse como los factores mónicos del polinomio de primer coeficiente respectivamente. el último coeficiente polinómico desplazado . Entonces tiene que cumplir una determinada ecuación algebraica . Tomando todas las posibles ternas finitas y calculando la solución polinómica correspondiente de la ecuación de recurrencia transformada. proporciona una solución hipergeométrica si existe.
En el siguiente pseudocódigo se denota el grado de como y su coeficiente de como . algoritmo petkovsek es entrada: ecuación de recurrencia lineal . salida: Una solución hipergeométrica si hay alguna solución hipergeométrica
para cada divisor mónico de haz para cada monic divisor de haz para cada haz
para cada raíz de do Halla solución polinomial no nula de si existe una solución no nula entonces
devolver una solución no nula de Si no se encuentra una solución, es posible combinar todas las soluciones hipergeométricas para obtener una solución hipergeométrica general de la ecuación de recurrencia, es decir, un conjunto generador para el núcleo de la ecuación de recurrencia en el espacio lineal generado por las secuencias hipergeométricas.
Petkovšek también mostró cómo se puede resolver el problema de la heterogeneidad. Consideró el caso en el que el lado derecho de la ecuación de recurrencia es una suma de secuencias hipergeométricas. Tras agrupar ciertas secuencias hipergeométricas del lado derecho, se resuelve una determinada ecuación de recurrencia para obtener una solución racional en cada uno de esos grupos. Estas soluciones racionales pueden combinarse para obtener una solución particular de la ecuación no homogénea. Junto con la solución general del problema homogéneo, esto da la solución general del problema no homogéneo.
Ejemplos
Matrices de permutación con signo El número de matrices de permutación con signo de tamaño puede describirse mediante la secuencia que está determinado por la ecuación de recurrencia encima . Tomando como divisores mónicos de respectivamente, uno obtiene . Para La ecuación de recurrencia correspondiente que se resuelve en el algoritmo de Petkovšek es Esta ecuación de recurrencia tiene la solución polinómica para un arbitrario . Por eso y es una solución hipergeométrica. De hecho, es (salvo una constante) la única solución hipergeométrica y describe el número de matrices de permutación con signo.
Irracionalidad de Dado la suma
resultado de la prueba de Apéry sobre la irracionalidad de , el algoritmo de Zeilberger calcula la recurrencia lineal.
Dada esta recurrencia, el algoritmo no devuelve ninguna solución hipergeométrica, lo que demuestra que no se simplifica a un término hipergeométrico .
Referencias
Enlaces externos
Implementación de Mathematica por Petkovšek
Categoría:Combinatoria Categoría:Matemáticas Categoría:Matemática discreta Categoría:Matemática computacional Categoría:Wikipedia:Páginas con traducciones sin revisar