P-rekurzivní rovnice - P-recursive equation
tento článek potřebuje pozornost odborníka na matematiku. Specifický problém je: zkontrolovat článek.Říjen 2019) ( |
V matematice a P-rekurzivní rovnice je lineární rovnice sekvence kde lze posoudit sekvence koeficientů jako polynomy. P-rekurzivní rovnice jsou lineární rekurenční rovnice (nebo lineární relace opakování nebo lineární diferenční rovnice) s polynomiálními koeficienty. Tyto rovnice hrají důležitou roli v různých oblastech matematiky, konkrétně v kombinatorika. Sekvence, které jsou řešením těchto rovnic, se nazývají holonomický, P-rekurzivní nebo D-konečné.
Od konce 80. let 20. století byly vyvinuty první algoritmy k nalezení řešení pro tyto rovnice. Sergej A. Abramov, Marko Petkovšek a Mark van Hoeij popsali algoritmy k nalezení polynomiálních, racionálních, hypergeometrických a d'Alembertianových řešení.
Definice
Nechat být pole charakteristické nuly (například ), polynomy pro , sekvence a neznámá sekvence. Rovnice
To lze také zapsat jako kde je lineární operátor opakování s polynomiálními koeficienty a je operátor směny, tj. .
Uzavřená řešení
Nechat nebo ekvivalentně být rovnicí rekurence s polynomiálními koeficienty. Existuje několik algoritmů, které počítají řešení této rovnice. Tyto algoritmy mohou vypočítat polynomiální, racionální, hypergeometrická a d'Alembertianova řešení. Řešení homogenní rovnice je dáno vztahem jádro operátora lineárního opakování: . Jako podprostor prostoru sekvencí má toto jádro základ.[1] Nechat být základem , pak formální částka pro libovolné konstanty se nazývá obecné řešení homogenního problému . Li je konkrétní řešení , tj. , pak je také řešením nehomogenního problému a nazývá se obecným řešením nehomogenního problému.
Polynomiální řešení
Na konci 80. let popsal Sergej A. Abramov algoritmus, který nalézá obecné polynomické řešení rekurenční rovnice, tj. s polynomickou pravou stranou. On (a o několik let později Marko Petkovšek ) poskytl stupeň vázaný na polynomiální řešení. Tímto způsobem lze problém jednoduše vyřešit zvážením a soustava lineárních rovnic.[2][3][4] V roce 1995 Abramov, Bronstein a Petkovšek ukázali, že polynomiální případ lze vyřešit efektivněji zvážením výkonová řada řešení rekurenční rovnice na konkrétní výkonové bázi (tj. ne na běžné bázi ).[5]
Ostatní algoritmy pro hledání obecnějších řešení (např. Racionální nebo hypergeometrická řešení) také spoléhají na algoritmy, které počítají polynomiální řešení.
Racionální řešení
V roce 1989 Sergej A. Abramov ukázal, že generál Racionální řešení, tj. , s polynomiální pravou stranou , lze nalézt pomocí pojmu univerzálního jmenovatele. Univerzálním jmenovatelem je polynom tak, aby se jmenovatel každého racionálního řešení rozdělil . Abramov ukázal, jak lze tento univerzální jmenovatel vypočítat pouze pomocí prvního a posledního polynomu koeficientu a . Nahrazení tohoto univerzálního jmenovatele neznámým jmenovatelem všechna racionální řešení lze najít výpočtem všech polynomiálních řešení transformované rovnice.[6]
Hypergeometrické řešení
Sekvence je nazýván hypergeometrický pokud je poměr dvou po sobě jdoucích členů racionální funkcí v , tj. . To je případ právě tehdy, když posloupnost je řešením rekurence rovnice prvního řádu s polynomiálními koeficienty. Sada hypergeometrických sekvencí není podprostorem prostoru sekvencí, protože není uzavřena při přidání.
V roce 1992 Marko Petkovšek dal algoritmus získat obecné hypergeometrické řešení rekurenční rovnice, kde je pravá strana je součet hypergeometrických sekvencí. Algoritmus využívá Gosper-Petkovšekovu normální formu racionální funkce. S touto specifickou reprezentací je opět dostačující uvažovat polynomiální řešení transformované rovnice.[3]
Odlišný a efektivnější přístup je způsoben Markem van Hoeijem. Vzhledem k kořenům prvního a posledního polynomu koeficientu a - zvané singularity - lze vytvořit řešení krok za krokem s využitím skutečnosti, že každá hypergeometrická posloupnost má reprezentaci formuláře
D'Alembertian řešení
Sekvence se nazývá d'Alembertian, pokud pro některé hypergeometrické sekvence a znamená, že kde označuje operátor rozdílu, tj. . To je případ, kdy a pouze tehdy, pokud existují operátory lineárního opakování prvního řádu s racionálními koeficienty takovými .[4]
1994 Abramov a Petkovšek popsali algoritmus, který počítá obecné d'Alembertianovo řešení rekurenční rovnice. Tento algoritmus počítá hypergeometrická řešení a rekurzivně snižuje pořadí rekurentní rovnice.[9]
Příklady
Podepsané permutační matice
Počet podepsané permutační matice velikosti lze popsat pomocí sekvence . Podepsaná permutační matice je čtvercová matice, která má v každém řádku a v každém sloupci přesně jednu nenulovou položku. Nenulové položky mohou být . Sekvence je určena rovnicí lineární rekurence s polynomiálními koeficienty
Zapojení
Počet involuce sady s prvků je dána rovnicí rekurence
Aplikace
Funkce se nazývá hypergeometrický, pokud kde označuje racionální funkce v a . Hypergeometrický součet je konečný součet tvaru kde je hypergeometrický. Zeilberger Kreativní algoritmus teleskopu může takový hypergeometrický součet transformovat do rekurenční rovnice s polynomiálními koeficienty. Tuto rovnici lze poté vyřešit, abychom získali například lineární kombinaci hypergeometrických řešení, která se nazývá uzavřená forma řešení .[4]
Reference
- ^ Pokud jsou sekvence považovány za rovnocenné, pokud jsou stejné téměř ve všech termínech, pak je tento základ konečný. Více o tom najdete v knize A = B od Petkovška, Wilfa a Zeilbergera.
- ^ Abramov, Sergei A. (1989). "Problémy v počítačové algebře, které souvisejí s hledáním polynomiálních řešení lineárních diferenciálních a rozdílových rovnic". Moskevská univerzita výpočetní matematika a kybernetika. 3.
- ^ A b Petkovšek, Marko (1992). "Hypergeometrická řešení lineárních rekurencí s polynomiálními koeficienty". Journal of Symbolic Computation. 14 (2–3): 243–264. doi:10.1016/0747-7171(92)90038-6. ISSN 0747-7171.
- ^ A b C d Petkovšek, Marko; Wilf, Herbert S .; Zeilberger, Doron (1996). A = B. K Peters. ISBN 978-1568810638. OCLC 33898705.
- ^ Abramov, Sergei A .; Bronstein, Manuel; Petkovšek, Marko (1995). O polynomiálních řešeních lineárních operátorových rovnic. ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation. ACM. str. 290–296. CiteSeerX 10.1.1.46.9373. doi:10.1145/220346.220384. ISBN 978-0897916998.
- ^ Abramov, Sergei A. (1989). "Racionální řešení lineárních diferenciálních a diferenčních rovnic s polynomiálními koeficienty". SSSR výpočetní matematika a matematická fyzika. 29 (6): 7–12. doi:10.1016 / s0041-5553 (89) 80002-3. ISSN 0041-5553.
- ^ van Hoeij, Mark (1999). "Konečné singularity a hypergeometrická řešení lineárních rekurentních rovnic". Journal of Pure and Applied Algebra. 139 (1–3): 109–131. doi:10.1016 / s0022-4049 (99) 00008-0. ISSN 0022-4049.
- ^ Cluzeau, Thomas; van Hoeij, Mark (2006). "Výpočet hypergeometrických řešení lineárních rekurentních rovnic". Použitelná algebra ve strojírenství, komunikaci a práci na počítači. 17 (2): 83–115. doi:10.1007 / s00200-005-0192-x. ISSN 0938-1279.
- ^ Abramov, Sergei A .; Petkovšek, Marko (1994). D'Alembertian řešení lineárních diferenciálních a diferenčních rovnic. ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation. ACM. 169–174. doi:10.1145/190347.190412. ISBN 978-0897916387.
- ^ „A000165 - OEIS“. oeis.org. Citováno 2018-07-02.