El algoritmo de Petkovšek (también Hyper ) es un algoritmo de álgebra computacional que calcula una solución basada en términos hipergeométricos de su ecuación de recurrencia lineal de entrada con coeficientes polinomiales . De manera equivalente, calcula un factor correcto de primer orden de operadores de diferencia lineal con coeficientes polinomiales. Este algoritmo fue desarrollado por Marko Petkovšek en su tesis doctoral de 1992. [1] El algoritmo se implementa en todos los principales sistemas informáticos de álgebra.
Representación de Gosper-Petkovšek
Dejar ser un campo de característica cero. Una secuencia distinta de cerose llama hipergeométrica si la razón de dos términos consecutivos es racional , es decir. 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 . Dejarser una función racional distinta de cero. Entonces existen polinomios monicos y tal que
y
- por cada entero no negativo ,
- y
- .
Esta representación de se llama forma normal de Gosper-Petkovšek. Estos polinomios se pueden calcular explícitamente. Esta construcción de la representación es una parte esencial del algoritmo de Gosper . [2] Petkovšek agregó las condiciones 2. y 3. de esta representación que hacen que esta forma normal sea única. [1]
Algoritmo
Usando la representación de Gosper-Petkovšek se puede transformar la ecuación de recurrencia original en una ecuación de recurrencia para una secuencia polinomial . Los otros polinomios se puede tomar como los factores monicos del primer polinomio de coeficientes resp. el último polinomio de coeficiente desplazado. Luegotiene que cumplir una determinada ecuación algebraica . Tomando todos los posibles, un número finito de triplesy calcular la solución polinomial correspondiente de la ecuación de recurrencia transformadada una solución hipergeométrica si existe. [1] [3] [4]
En el siguiente pseudocódigo el grado de un polinomio se denota por y el coeficiente de se denota por .
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 monico de hacer para cada divisor mónico de hacer para cada uno hacer para cada raíz de no encontrar una solución polinomio distinto de cero de si tal solución distinta de cero existe entonces devolver una solución distinta de cero de
Si uno no termina si 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 intervalo lineal de secuencias hipergeométricas. [1]
Petkovšek también mostró cómo se puede resolver el problema no homogéneo. Consideró el caso en el que el lado derecho de la ecuación de recurrencia es una suma de secuencias hipergeométricas. Después de agrupar ciertas secuencias hipergeométricas del lado derecho, para cada uno de esos grupos se resuelve una cierta ecuación de recurrencia para una solución racional. Estas soluciones racionales se pueden combinar 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. [1]
Ejemplos de
Matrices de permutación firmadas
El número de matrices de permutación firmadas de tamaño puede ser descrito por la secuencia que está determinada por la ecuación de recurrencia
Irracionalidad de
Dada la suma
procedente de la prueba de Apéry de la irracionalidad de, El algoritmo de Zeilberger calcula la recurrencia lineal
Ante esta recurrencia, el algoritmo no devuelve ninguna solución hipergeométrica, lo que demuestra que no se simplifica a un término hipergeométrico . [3]
Referencias
- ↑ a b c d e Petkovšek, Marko (1992). "Soluciones hipergeométricas de recurrencias lineales con coeficientes polinomiales". Revista de Computación Simbólica . 14 (2–3): 243–264. doi : 10.1016 / 0747-7171 (92) 90038-6 . ISSN 0747-7171 .
- ^ Gosper, R. William (1978). "Procedimiento de decisión por suma hipergeométrica indefinida" (PDF) . Proc. Natl. Acad. Sci. USA . 75 (1): 40–42. doi : 10.1073 / pnas.75.1.40 . PMC 411178 . PMID 16592483 . Archivado desde el original (PDF) el 27 de julio de 2018.
- ^ a b Petkovšek, Marko; Wilf, Herbert S .; Zeilberger, Doron (1996). A = B . AK Peters. ISBN 1568810636. OCLC 33898705 .
- ^ Kauers, Manuel; Paule, Peter (2011). El tetraedro concreto: sumas simbólicas, ecuaciones de recurrencia, funciones generadoras, estimaciones asintóticas . Viena: Springer. ISBN 9783709104453. OCLC 701369215 .
- ^ "A000165 - OEIS" . oeis.org . Consultado el 2 de julio de 2018 .