Petkovšekův algoritmus - Petkovšeks algorithm - Wikipedia

Petkovšekův algoritmus (taky Hyper) je počítačová algebra algoritmus, který počítá základ hypergeometrické termíny řešení jeho vstupu lineární rekurenční rovnice s polynomiálními koeficienty. Ekvivalentně vypočítá lineární faktor prvního řádu správného řádu operátory rozdílu s polynomiálními koeficienty. Tento algoritmus vyvinul Marko Petkovšek ve své disertační práci 1992.^[1] Algoritmus je implementován ve všech hlavních systémech počítačové algebry.

Gosper-Petkovšek zastoupení

Nechat ${ textstyle mathbb {K}}$ být pole z charakteristický nula. Nenulová sekvence ${ textový y (n)}$ se nazývá hypergeometrický, pokud je poměr dvou po sobě jdoucích členů Racionální, tj. ${ textový styl y (n + 1) / y (n) v mathbb {K} (n)}$. Petkovšekův algoritmus používá jako klíčový koncept, že tato racionální funkce má specifické zastoupení, konkrétně Gosper-Petkovšek normální forma. Nechat ${ textstyle r (n) v mathbb {K} [n]}$ být nenulovou racionální funkcí. Pak existují monické polynomy ${ textstyle a, b, c v mathbb {K} [n]}$ a ${ textstyle 0 neq z in mathbb {K}}$ takhle

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

a

1. ${ textstyle gcd (a (n), b (n + k)) = 1}$ pro každé nezáporné celé číslo ${ textstyle k in mathbb {N}}$,
2. ${ textstyle gcd (a (n), c (n)) = 1}$ a
3. ${ textstyle gcd (b (n), c (n + 1)) = 1}$.

Toto znázornění ${ textstyle r (n)}$ se nazývá Gosper-Petkovšek normální forma. Tyto polynomy lze vypočítat explicitně. Tato konstrukce reprezentace je podstatnou součástí Gosperův algoritmus.^[2] Petkovšek přidal podmínky 2. a 3. této reprezentace, což činí tuto normální formu jedinečnou.^[1]

Algoritmus

Pomocí Gosper-Petkovškovy reprezentace lze transformovat původní rekurenční rovnici na rekurenční rovnici pro polynomiální sekvenci ${ textstyle c (n)}$. Ostatní polynomy ${ textstyle a (n), b (n)}$ lze brát jako monické faktory prvního polynomu prvního koeficientu ${ textstyle p_ {0} (n)}$ resp. polynom posledního koeficientu posunut ${ textstyle p_ {r} (n-r + 1)}$. Pak ${ textstyle z}$ musí splnit určité algebraická rovnice. Vezmeme všech možných konečně mnoho ztrojnásobí ${ textstyle (a (n), b (n), z)}$ a výpočet odpovídajících polynomiální řešení transformované rekurenční rovnice ${ textstyle c (n)}$ poskytuje hypergeometrické řešení, pokud existuje.^[1][3][4]

V následujícím pseudokódu je stupeň polynomu ${ textový styl p (n) v mathbb {K} [n]}$ je označen ${ textstyle deg (p (n))}$ a koeficient ${ textstyle n ^ {d}}$ je označen ${ textstyle { text {coeff}} (p (n), n ^ {d})}$.

algoritmus petkovsek je    vstup: Rovnice lineární rekurence ${ textstyle  sum _ {k = 0} ^ {r} p_ {k} (n) , y (n + k) = 0, p_ {k}  v  mathbb {K} [n], p_ { 0}, p_ {r}  neq 0}$.    výstup: Hypergeometrické řešení ${ textový styl}$ pokud existují nějaká hypergeometrická řešení. pro každého monický dělitel ${ textstyle a (n)}$ z ${ textstyle p_ {0} (n)}$ dělat        pro každého monický dělitel ${ textstyle b (n)}$ z ${ textstyle p_ {r} (n-r + 1)}$ dělat            pro každého ${ textstyle k = 0,  tečky, r}$ dělat                ${ textstyle { tilde {p}} _ {k} (n) = p_ {k} (n)  prod _ {j = 0} ^ {k-1} a (n + j)  prod _ {i = k} ^ {r-1} b (n + i)}$        ${ textstyle d =  max _ {k = 0,  tečky, r}  deg ({ tilde {p}} _ {k} (n))}$        pro každého vykořenit ${ textstyle z}$ z ${ textstyle  sum _ {k = 0} ^ {r} { text {coeff}} ({ tilde {p}} _ {k} (n), n ^ {d}) z ^ {k}}$ dělat            Najděte nenulové polynomické řešení ${ textstyle c (n)}$ z ${ textstyle  sum _ {k = 0} ^ {r} z ^ {k} , { tilde {p}} _ {k} (n) , c (n + k) = 0}$            -li takové nenulové řešení ${ textstyle c (n)}$ existuje pak                ${ textový styl r (n) = z , a (n) / b (n) , c (n + 1) / c (n)}$                vrátit se nenulové řešení ${ textový y (n)}$ z ${ textový styl y (n + 1) = r (n) , y (n)}$

Pokud jeden nekončí, pokud je nalezeno řešení, je možné kombinovat všechna hypergeometrická řešení a získat obecné hypergeometrické řešení rekurenční rovnice, tj. Generující množinu jádra rekurentní rovnice v lineárním rozpětí hypergeometrických sekvencí.^[1]

Petkovšek také ukázal, jak lze nehomogenní problém vyřešit. Zvažoval případ, kdy je pravá strana rekurenční rovnice součtem hypergeometrických sekvencí. Po seskupení určitých hypergeometrických sekvencí na pravé straně je pro každou z těchto skupin vyřešena určitá rovnice opakování pro racionální řešení. Tato racionální řešení lze kombinovat a získat konkrétní řešení nehomogenní rovnice. Spolu s obecným řešením homogenního problému to dává obecné řešení nehomogenního problému.^[1]

Příklady

Podepsané permutační matice

Počet podepsané permutační matice velikosti ${ textový styl n krát n}$ lze popsat posloupností ${ textový y (n)}$ který je určen rovnicí rekurence

přes ${ textstyle mathbb {Q}}$. Brát ${ textstyle a (n) = n + 1, b (n) = 1}$ jako moničtí dělitelé ${ textstyle p_ {0} (n) = 4 (n + 1) ^ {2}, p_ {2} (n) = - 1}$ jeden dostane ${ textstyle z = pm 2}$. Pro ${ textstyle z = 2}$ odpovídající rekurenční rovnice, která je řešena Petkovškovým algoritmem, jeTato rovnice rekurence má polynomiální řešení ${ textstyle c (n) = c_ {0}}$ pro svévolné ${ textstyle c_ {0} in mathbb {Q}}$. Proto ${ textstyle r (n) = 2 (n + 1)}$ a ${ textový styl y (n) = 2 ^ {n} , n!}$ je hypergeometrické řešení. Ve skutečnosti je (až do konstanty) jediným hypergeometrickým řešením a popisuje počet podepsaných permutačních matic.^[5]

Iracionalita ${ displaystyle zeta (3)}$

Vzhledem k součtu

${ displaystyle a (n) = součet _ {k = 0} ^ {n} {{ binom {n} {k}} ^ {2} { binom {n + k} {k}} ^ {2 }},}$

přicházející z Apéry je důkaz iracionality ${ displaystyle zeta (3)}$, Zeilberger Algoritmus počítá lineární opakování

${ displaystyle (n + 2) ^ {3} , a (n + 2) - (17n ^ {2} + 51n + 39) (2n + 3) , a (n + 1) + (n + 1 ) ^ {3} , a (n) = 0.}$

Vzhledem k tomuto opakování algoritmus nevrací žádné hypergeometrické řešení, což to dokazuje ${ displaystyle a (n)}$ nezjednodušuje na a hypergeometrický termín.^[3]

Reference