Algorytm Abramowa

W matematyce, zwłaszcza w algebrze komputerowej , algorytm Abramowa oblicza wszystkie racjonalne rozwiązania liniowego równania rekurencyjnego ze współczynnikami wielomianowymi . Algorytm został opublikowany przez Siergieja A. Abramowa w 1989 roku.

Uniwersalny mianownik

Główną koncepcją algorytmu Abramowa jest uniwersalny mianownik. Niech $\textstyle \mathbb {K}}$ { będzie polem charakterystycznym zero. Dyspersja ${\ textstyle \ operatorname {dis} (p, q)}$ dwóch wielomianów $n] }$ ∈ jest zdefiniowany jako

$${\ Displaystyle \ operatorname {dis} ( p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{ -1\},}$$

gdzie ${\textstyle \mathbb {N}}$ oznacza zbiór nieujemnych liczb całkowitych. $}$ dyspersja jest maksymalna $\$ , że ​​wielomian ma $k \ in \ mathbb {N$$textstyle$ wspólny czynnik. To jest ${\ textstyle -1}$$.$ jeśli takie nie istnieje Dyspersję można obliczyć jako największy nieujemny pierwiastek całkowity z wynikowego ${\ textstyle \ operatorname {res} _ {n} ( p(n),q(n+k))\in \mathbb {K} [k]}$ . Niech ${\ textstyle \ suma _ {k = 0} ^ {r} p_ {k} (n) \, y (n + k ) = f (n)}$ być równaniem powtarzalności rzędu ${\ textstyle r}$ ze współczynnikami wielomianu ${\ Displaystyle p_ {k} \ in \ mathbb {K} [n]}$ , wielomian w prawo -strona strony ${\ textstyle f \ in \ mathbb {K} [n]}$ i racjonalne rozwiązanie ciągu ${\ textstyle y (n) \ in \ mathbb {K } (n)}$ . Można napisać ${\ textstyle y (n) = p (n) / q (n)}$ dla dwóch względnie pierwszych wielomianów ${\ textstyle p, q \ w \ mathbb {K} [n]}$ . Niech ${\ textstyle D = \ operatorname {dis} (p_ {r} (nr), p_ {0} (n))}$ i

$${\ Displaystyle u (n) = \ gcd ([p_ {0} (n+D)]^{\podkreślenie {D+1}},[p_{r}(nr)]^{\podkreślenie {D+1}})}$$

gdzie ${\ textstyle [p (n)] ^ {\ podkreślenie {k}} = p (n )p(n-1)\cdots p(n-k+1)}$ oznacza opadającą silnię funkcji. q ${\ textstyle q (n)}$ dzieli ${\ textstyle u (n)$ . Tak więc wielomian $może$ mianownik dla wszystkich racjonalnych rozwiązań $nazywany$ .

Algorytm

∑ ${\ textstyle \ suma _ {k = 0} ^ {r} p_ {k} (n) \, y (n$$rekurencyjnym$ będzie równaniem ze współczynnikami wielomianu uniwersalnym mianownikiem Po podstawieniu nieznanego wielomianu ${\ textstyle y (n) = z (n)/u (n)}$$[$${\ textstyle$$_ {lcm} (u(n),\kropki ,u(n+r))}$ i równanie powtarzalności jest równoważne

$${\ Displaystyle \ suma _ {k = 0} ^ {r} p_ {k} (n) {\ Frac {z (n + k)} {u (n + k)}} \ ell (n) = f ( n)\ell (n).}$$

Ponieważ anuluje się $,$$n)}$ to równanie rekurencji liniowej ze współczynnikami wielomianu, które można rozwiązać dla nieznanego rozwiązania wielomianu. . Istnieją algorytmy do znajdowania rozwiązań wielomianowych . Rozwiązania dla $u$${\ textstyle y (n) = z$ racjonalnych rozwiązań .

    
    
    
    
        
    
         algorytm  racjonalne_rozwiązania  jest  wprowadzany:  liniowe równanie rekurencji ${\ textstyle \ suma _ {k=0}^{r}p_{k}(n)\,y(n+k)=f(n),p_{k},f\in \mathbb {K} [n],p_{0 },p_{r}\neq 0}$ .  wyjście:  Ogólne racjonalne rozwiązanie, $jeśli$ jakieś rozwiązania, w przeciwnym razie fałsz. ${\ textstyle D = \ operatorname {disp} (p_ {r} (nr), p_ {0} (n))}$${\ textstyle u (n) = \ gcd ([p_ {0} (n + D )] ^ {\podkreślenie {D+1}},[p_{r}(nr)]^{\podkreślenie {D+1}})}$${\ textstyle \ ell (n) = \ operatorname {lcm} (u (n), \ kropki, u (n + r))}$ Rozwiąż ${\ textstyle \ suma _ {k = 0} ^ {r} p_ {k} (n) {\ Frac {z ( n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)}$ dla ogólnego rozwiązania wielomianu ${\textstyle z(n)}$ jeśli  rozwiązanie ${\ textstyle z (n)}$ istnieje  , a następnie  zwróć  rozwiązanie ogólne ${\ textstyle y (n) = z (n)/u (n)}$ w przeciwnym razie  zwróć  fałsz  koniec, jeśli 

Przykład

Jednorodne równanie rekurencyjne rzędu ${\ textstyle 1}$

$${\ Displaystyle (n-1) \, y (n) + (- n-1) \, y (n + 1)=0}$$

przez ${\textstyle \mathbb {Q}}$ ma racjonalne rozwiązanie. Można to obliczyć, biorąc pod uwagę dyspersję

$${\ Displaystyle D = \ operatorname {dis} (p_ {1} (n- 1),p_{0}(n))=\nazwa_operatora {disp} (-n,n-1)=1.}$$

Daje to następujący uniwersalny mianownik:

$${\ Displaystyle u (n) = \ gcd ([p_ {0}(n+1)]^{\podkreślenie {2}},[p_{r}(n-1)]^{\podkreślenie {2}})=(n-1)n}$$

I

$${\ Displaystyle \ ell (n) = \ nazwa operatora {lcm} (u (n), u (n + 1)) = (n-1) n (n + 1).}$$

$\ ell (n)}$${\ textstyle y (n) = z (n)/u ( n)}$ i podstawienie ( prowadzi do

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

To równanie ma rozwiązanie wielomianowe dla dowolnej stałej $}$$= c$ z (n Używając ogólnego racjonalnego rozwiązania jest ${\ textstyle y (n) = z (n)/u (n)}$

$${\ Displaystyle y (n) = {\ Frac {c} {(n-1) n}}}$$

dla dowolnego ${\ textstyle c \ in \ mathbb {Q}}$ .

WikiProject Matematyka na Wikidanych