Rozwiązania wielomianowe równań P-rekurencyjnych

W matematyce równanie P-rekurencyjne można rozwiązać dla rozwiązań wielomianowych . Siergiej A. Abramov w 1989 i Marko Petkovšek w 1992 opisali algorytm , który znajduje wszystkie wielomianowe rozwiązania tych równań rekurencyjnych ze współczynnikami wielomianów. Algorytm oblicza stopień związany z rozwiązaniem w pierwszym kroku. W drugim kroku ansatz dla wielomianu tego stopnia i oblicza nieznane współczynniki za pomocą układu równań liniowych . W tym artykule opisano ten algorytm.

$. {n})_{n\w \mathbb {N}}})$ rozwiązać wydajniej, rozważając szeregów potęgowych równania określonej podstawie potęgowej ( .

Inne algorytmy obliczające racjonalne lub hipergeometryczne rozwiązania liniowego równania rekurencyjnego ze współczynnikami wielomianowymi również wykorzystują algorytmy obliczające rozwiązania wielomianowe.

Stopień związany

Niech ${\textstyle \mathbb {K}}$ będzie polem charakterystycznym zero i ${\ textstyle \ suma _ {k = 0} ^ {r} p_ {k} (n) \, y (n + k) = f (n)}$ równanie rekurencyjne rzędu ${\ textstyle r}$ ze współczynnikami wielomianu ${\ textstyle p_ {k} \ in \ mathbb {K} [n]}$ , wielomian po prawej stronie ${\ textstyle f \ in \ mathbb {K} [n]}$ i nieznana sekwencja wielomianów ${\ Displaystyle y (n) \ w \ mathbb {K} [n]}$ . Ponadto ${\ textstyle \ deg (p)}$ oznacza stopień wielomianu ${\ textstyle p \ in \ mathbb {K} [n]}$ (z ${\ textstyle \ deg (0) = - \ infty}$ dla wielomianu zerowego) i ${\ textstyle {\text{lc}}(p)}$ oznacza wiodący współczynnik wielomianu. Ponadto niech

$${\ Displaystyle {\ rozpocząć {wyrównane} q_ {i} & = \ suma _ {k = i} ^ {r} {\ binom {k} {i}} p_ {k}, & b & = \ max _ {i = 0,\kropki ,r}(\deg(q_{i})-i),\\\alpha (n)&=\sum _{i=0,\dots ,r \na szczycie \deg(q_{i} )-i=b}{\text{lc}}(q_{i})n^{\podkreślenie {i}},&d_{\alpha }&=\max\{n\in \mathbb {N} \, :\,\alpha (n)=0\}\cup \{-\infty \}\end{aligned}}}$$

dla ${\ textstyle i = 0, \ kropki, r}$ gdzie $(n-i+1)}$${\ textstyle n ^ {\ podkreślenie {i}} =n(n-1)\$$cdots$ oznacza opadającą i zbiór nieujemnych liczb całkowitych. Wtedy ${\ Textstyle \ stopień (y) \ równoważnik \ max \ {\ stopień (f) -b, -b-1, d_ {\ alfa} \}}$ . Nazywa się to ograniczeniem stopnia dla rozwiązania wielomianowego ${\ textstyle y}$ . Tę granicę pokazali Abramov i Petkovšek.

Algorytm

Algorytm składa się z dwóch kroków. W pierwszym kroku obliczana jest granica stopnia . W drugim etapie $tworzony$ z wielomianem tego stopnia z dowolnymi współczynnikami w $jest$ i podłączany do równania rekurencyjnego ustawia i rozwiązuje układ równań liniowych dla współczynników ${\ textstyle y} .$ Nazywa się to metodą nieokreślonych współczynników . Algorytm zwraca ogólne wielomianowe rozwiązanie równania rekurencyjnego.

     algorytm  polynomial_solutions  jest  wprowadzany:  liniowe równanie rekurencji ${\ 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}$  
        
    
     .  wynik:  Ogólne rozwiązanie wielomianu, $istnieją$ jakieś rozwiązania, w przeciwnym razie fałsz.  dla ${\ textstyle i = 0, \ kropki, r}$ zrobić ${\ textstyle q_ {i} = \ suma _ {k = i} ^{r}{\binom {k}{i}}p_{k}}$ powtórz 
    ${\ textstyle b = \ max _ {i = 0, \ kropki, r} (\ stopień (q_ {i}) -i)}$
    
    ${\textstyle \alpha (n)=\sum _{i=0,\kropki ,r \na górze \deg(q_{i})-i=b}{\text{lc}}(q_{i})n ^ {\ podkreślenie {i}}}$${\ textstyle d_ {\ alfa} = \ max \ {n \ w \ mathbb {N} \,:\,\alpha (n)=0\}\kielich \{-\infty \}}$
    ${\ textstyle d = \ max \ {\ stopień (f) - b, - b - 1, d _ {\ alfa} \}}$${\ textstyle y dla$ j $_$ _ ${\textstyle j=0,\kropki ,d}$ Porównaj współczynniki wielomianów 
     
        ${\ textstyle \ suma _ {k = 0} ^ {r} p_ {k} (n) \, y (n + k)} i fa$ ( $textstyle f (n)}$ , aby uzyskać możliwe wartości dla ${\ textstyle y_ {j}, j = 0, \ kropki, d},$ jeśli  istnieją możliwe wartości dla ${\ textstyle y_ {j }}$ następnie  zwróć  ogólne rozwiązanie 
    
        ${\textstyle y}$ else  zwraca  fałszywe  zakończenie if 

Przykład

Stosowanie wzoru na stopień związany z równaniem rekurencyjnym

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

nad ${\ textstyle \ mathbb {Q}}$ daje ${\ textstyle \ deg (y) \ równoważnik 2}$ . Stąd można użyć ansatz z wielomianem kwadratowym ${\ textstyle y (n) = y_ {2} n ^ {2} + y_ {1} n + y_ {0}}$ gdzie ${\ textstyle y_ {0}, y_ {1}, y_ {2} \ w \ mathbb {Q}}$ . Podłączenie tego ansatz do pierwotnego równania rekurencyjnego prowadzi do

$${\ Displaystyle 2n = (n ^ {2}-2) \, y (n) + (- n ^ {2} + 2n) \, y (n + 1) = (y_ {1} + y_ {2} )\,n^{2}+(2y_{0}+2y_{2})\,n-2y_{0}.}$$

Jest to równoważne z następującym układem równań liniowych

$${\ Displaystyle {\ rozpocząć {wyrównane}} {\ rozpocząć {pmatrix} 0 i 1 i 1 \\ 2 i 0 i 2 \\ - 2 i 0 i 0 \ koniec {pmatrix}}} {\ begin{pmatrix}y_{0}\\y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}0\\2\\0\end{pmatrix}}\end{wyrównane }}}$$

z rozwiązaniem ${\ textstyle y_ {0} = 0, y_ {1} = - 1, y_ {2} = 1}$ . Dlatego jedynym rozwiązaniem wielomianowym jest ${\ textstyle y (n) = n ^ {2} -n}$ .