Algoritme de Petkovšek

L'algoritme de Petkovši és un algoritme d'àlgebra computacional que calcula una solució en base de térmens hipergeométricos de la seua equació de recurrencia llineal d'entrada en coeficients polinòmics . Igualment, calcula un factor dret de primer orde d'operadors de diferències llineals en coeficients polinòmics. Este algoritme va ser desenrollat per Marko Petkovšek en la seua tesis doctoral de 1992. L'algoritme està implementat en tots els principals sistemes d'àlgebra computacional.

Representació de Gosper-Petkovšek

Siga $𝕂$ un camp de característica zero. Una seqüència no nula $y(n)$ és hipergeométrica si $\frac{y(n+1)}{y(n)}\in 𝕂(n)$ . L'algoritme de Petkovšek utilisa com a concepte clau que esta funció racional té una representació específica, a saber, la forma normal de Gosper-Petkovšek . Siga $r(n)\in 𝕂[n]$ una funció racional no nula, llavors existixen polinomis mónicos $a,b,c\in 𝕂[n]$ i $z\in {𝕂}^{*}$ de tal manera que

$r(n)=z\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}$

i

1. $\mathrm{mcd}(a(n),b(n+k))=1$ per a cada sancer no negatiu $k\in \mathbb{N}$ ,
2. $\mathrm{mcd}(a(n),c(n))=1$ i
3. $\mathrm{mcd}(b(n),c(n+1))=1$ .

Esta representació de $r(n)$ es diu forma normal de Gosper-Petkovšek, que es poden calcular explícitament. Esta construcció de la representació és una part essencial del algoritme de Gosper . Petkovšek va afegir les condicions 2. i 3 d'esta representació que fa que esta forma normal siga única.

Algoritme

Utilisant la representació de Gosper-Petkovšek, es pot transformar l'equació de recurrencia original en una equació de recurrencia per a una successió polinòmica. $c(n)$ . Els atres polinomis $a(n),b(n)$ poden prendre's com els factors mónicos del polinomi de primer coeficient $p_0(n)$ respectivament. l'últim coeficient polinòmic desplaçat $p_r(n-r+1)$ . Llavors $z$ té que complir una determinada equació algebraica . Prenent totes les possibles ternes finitas $(a(n),b(n),z)$ i calculant la solució polinòmica corresponent de l'equació de recurrencia transformada. $c(n)$ proporciona una solució hipergeométrica si existix.

En el següent pseudocódigo es denota el grau de $p(n)\in 𝕂[n]$ com $\mathrm{deg}(p(n))$ i el seu coeficient de $n^d$ com $\text{coeff}(p(n),n^d)$ .

algoritme petkovsek és
    entrada: equació de recurrencia llineal ${\sum }_{k=0}^r{p}_k(n)y(n+k)=0,p_k\in 𝕂[n],p_0,p_r\ne 0$.
    eixida: Una solució hipergeométrica $y$ si hi ha alguna solució hipergeométrica

    per a cada divisor mónico $a(n)$ de $p_0(n)$ fes

per a cada monic divisor $b(n)$ de $p_r(n-r+1)$ fes

            para cada $k=0,\dots ,r$ fes
                ${\tilde{p}}_k(n)=p_k(n){\prod }_{j=0}^{k-1}a(n+j){\prod }_{i=k}^{r-1}b(n+i)$
        $d=\underset{k=0,\dots ,r}{\max }\mathrm{deg}({\tilde{p}}_k(n))$
        per a cada raïl $z$ de ${\sum }_{k=0}^r\text{coeff}({\tilde{p}}_k(n),n^d)z^k$ do
            Troba solució polinomial no nula $c(n)$ de ${\sum }_{k=0}^r{z}^k{\tilde{p}}_k(n)c(n+k)=0$
            si existix una solució no nula $c(n)$ llavors
                $r(n)=za(n)/b(n)c(n+1)/c(n)$
                tornar una solució no nula $y(n)$ de $y(n+1)=r(n)y(n)$

Si no es troba una solució, és possible combinar totes les solucions hipergeométricas per a obtindre una solució hipergeométrica general de l'equació de recurrencia, és dir, un conjunt generador per al núcleu de l'equació de recurrencia en l'espai llineal generat per les seqüències hipergeométricas.

Petkovšek també va mostrar cóm es pot resoldre el problema de l'heterogeneïtat. Va considerar el cas en el que el costat dret de l'equació de recurrencia és una suma de seqüències hipergeométricas. Despuix d'agrupar certes seqüències hipergeométricas del costat dret, es resol una determinada equació de recurrencia per a obtindre una solució racional en cada u d'eixos grups. Estes solucions racionals poden combinar-se per a obtindre una solució particular de l'equació no homogénea. Junt en la solució general del problema homogéneu, açò dona la solució general del problema no homogéneu.