Abramovův algoritmus - Abramovs algorithm - Wikipedia

V matematice, zejména v počítačová algebra, Abramovův algoritmus počítá vše Racionální řešení a lineární rekurenční rovnice s polynomiálními koeficienty. Algoritmus publikoval Sergej A. Abramov v roce 1989.^[1]^[2]

Univerzální jmenovatel

Hlavní koncept v Abramovově algoritmu je univerzální jmenovatel. Nechat ${ textstyle mathbb {K}}$ být pole z charakteristický nula. The disperze ${ textstyle operatorname {dis} (p, q)}$ dvou polynomů ${ textový styl p, q v mathbb {K} [n]}$ je definován jako

{ displaystyle operatorname {dis} (p, q) = max {k v mathbb {N} ,: , deg ( gcd (p (n), q (n + k))) geq 1 } pohár {- 1 },}

kde

{ textstyle mathbb {N}}

označuje množinu nezáporných celých čísel. Proto je rozptyl maximální

{ textstyle k in mathbb {N}}

takový, že polynom

{ textový styl}

a

{ textstyle k}

-krát posunutý polynom

{ displaystyle q}

mají společný faktor. to je

{ textstyle -1}

pokud takový a

{ textstyle k}

neexistuje. Disperzi lze vypočítat jako největší nezáporný celočíselný kořen výsledný

{ textstyle operatorname {res} _ {n} (p (n), q (n + k)) v mathbb {K} [k]}

.^[3]^[4] Nechat

{ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) , y (n + k) = f (n)}

být rovnice rekurence řádu

{ textstyle r}

s polynomiálními koeficienty

{ displaystyle p_ {k} in mathbb {K} [n]}

, polynomiální pravá strana

{ textstyle f in mathbb {K} [n]}

a řešení racionální sekvence

{ textový styl y (n) v mathbb {K} (n)}

. Je možné psát

{ textový styl y (n) = p (n) / q (n)}

pro dva relativně hlavní polynomy

{ textový styl p, q v mathbb {K} [n]}

. Nechat

{ textstyle D = operatorname {dis} (p_ {r} (n-r), p_ {0} (n))}

a

{ displaystyle u (n) = gcd ([p_ {0} (n + D)] ^ { podtržení {D + 1}}, [p_ {r} (nr)] ^ { podtržení {D + 1 }})}

kde

{ textstyle [p (n)] ^ { podtržení {k}} = p (n) p (n-1) cdots p (n-k + 1)}

označuje klesající faktoriál funkce. Pak

{ textstyle q (n)}

rozděluje

{ textstyle u (n)}

. Takže polynom

{ textstyle u (n)}

lze použít jako jmenovatel pro všechna racionální řešení

{ textový y (n)}

a proto se tomu říká univerzální jmenovatel.^[5]

Algoritmus

Znovu ${ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) , y (n + k) = f (n)}$ být rekurenční rovnice s polynomiálními koeficienty a ${ textstyle u (n)}$ univerzální jmenovatel. Po střídání ${ textový styl y (n) = z (n) / u (n)}$ pro neznámý polynom ${ textstyle z (n) v mathbb {K} [n]}$ a nastavení ${ textstyle ell (n) = operatorname {lcm} (u (n), tečky, u (n + r))}$ rovnice rekurence je ekvivalentní s

{ displaystyle sum _ {k = 0} ^ {r} p_ {k} (n) { frac {z (n + k)} {u (n + k)}} ell (n) = f ( n) ell (n).}

Jako

{ textový styl u (n + k)}

zrušit toto je lineární rekurenční rovnice s polynomiálními koeficienty, kterou lze vyřešit pro neznámé polynomické řešení

{ textstyle z (n)}

. Existují algoritmy k nalezení polynomiálních řešení. Řešení pro

{ textstyle z (n)}

pak lze znovu použít k výpočtu racionálních řešení

{ textový styl y (n) = z (n) / u (n)}

. ^[2]

algoritmus racionální_řešení je    vstup: Rovnice lineární rekurence  ${ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) , y (n + k) = f (n), p_ {k}, f in mathbb {K} [ n], p_ {0}, p_ {r} neq 0}$ .    výstup: Obecné racionální řešení  ${ textový styl}$  pokud existují nějaká řešení, jinak falešná.  ${ textstyle D = operatorname {disp} (p_ {r} (n-r), p_ {0} (n))}$      ${ textstyle u (n) = gcd ([p_ {0} (n + D)] ^ { podtržení {D + 1}}, [p_ {r} (nr)] ^ { podtržení {D + 1 }})}$      ${ textstyle ell (n) = operatorname {lcm} (u (n), tečky, u (n + r))}$     Řešit  ${ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) { frac {z (n + k)} {u (n + k)}} ell (n) = f ( n) ell (n)}$  pro obecné polynomické řešení  ${ textstyle z (n)}$     -li řešení  ${ textstyle z (n)}$  existuje pak        vrátit se obecné řešení  ${ textový styl y (n) = z (n) / u (n)}$     jiný        vrátit se Nepravdivé skončit, pokud

Příklad

Homogenní rekurenční rovnice řádu ${ textový styl 1}$

{ displaystyle (n-1) , y (n) + (- n-1) , y (n + 1) = 0}

přes

{ textstyle mathbb {Q}}

má racionální řešení. Lze jej vypočítat zvážením disperze

{ displaystyle D = operatorname {dis} (p_ {1} (n-1), p_ {0} (n)) = operatorname {disp} (-n, n-1) = 1.}

Tím se získá následující univerzální jmenovatel:

{ displaystyle u (n) = gcd ([p_ {0} (n + 1)] ^ { podtržení {2}}, [p_ {r} (n-1)] ^ { podtržení {2}} ) = (n-1) n}

a

{ displaystyle ell (n) = operatorname {lcm} (u (n), u (n + 1)) = (n-1) n (n + 1).}

Vynásobení původní rovnice opakování s

{ textstyle ell (n)}

a nahrazovat

{ textový styl y (n) = z (n) / u (n)}

vede k

{ Displaystyle (n-1) (n + 1) , z (n) + (- n-1) (n-1) , z (n + 1) = 0.}

Tato rovnice má polynomické řešení

{ textstyle z (n) = c}

pro libovolnou konstantu

{ textstyle c in mathbb {Q}}

. Použitím

{ textový styl y (n) = z (n) / u (n)}

obecné racionální řešení je

{ displaystyle y (n) = { frac {c} {(n-1) n}}}

pro libovolné

{ textstyle c in mathbb {Q}}

.

Reference

^ 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.
^ ^A ^b Abramov, Sergei A. (1995). Racionální řešení rovnic lineárního rozdílu a q-rozdílu s polynomiálními koeficienty. ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation. str. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998.
^ Muž, Yiu-Kwong; Wright, Francis J. (1994). Rychlý výpočet polynomiálního rozptylu a jeho aplikace na neurčitý součet. ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387.
^ Gerhard, Jürgen (2005). Modulární algoritmy v symbolickém součtu a symbolické integraci. Přednášky z informatiky. 3218. doi:10.1007 / b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.
^ Chen, William Y. C .; Paule, Peter; Saad, Husam L. (2007). "Konvergující k Gosperovu algoritmu". arXiv:0711.3386 [matematika ].

Matematika WikiProject na Wikidata

[1] 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.

[Abramov_1995-2] A ^b Abramov, Sergei A. (1995). Racionální řešení rovnic lineárního rozdílu a q-rozdílu s polynomiálními koeficienty. ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation. str. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998.

[3] Muž, Yiu-Kwong; Wright, Francis J. (1994). Rychlý výpočet polynomiálního rozptylu a jeho aplikace na neurčitý součet. ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387.

[4] Gerhard, Jürgen (2005). Modulární algoritmy v symbolickém součtu a symbolické integraci. Přednášky z informatiky. 3218. doi:10.1007 / b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.

[5] Chen, William Y. C .; Paule, Peter; Saad, Husam L. (2007). "Konvergující k Gosperovu algoritmu". arXiv:0711.3386 [matematika ].

[1]

[2]

[3]

[4]

[5]