Полиномиальные решения P-рекурсивных уравнений

В математике P-рекурсивное уравнение можно решить для полиномиальных решений . Сергей Абрамов в 1989 году и Марко Петковшек в 1992 году описали алгоритм , который находит все полиномиальные решения этих рекуррентных уравнений с полиномиальными коэффициентами. Алгоритм вычисляет степень, ограничивающую решение, на первом этапе. На втором этапе используется анзац для полинома этой степени и неизвестные коэффициенты вычисляются с помощью системы линейных уравнений . В этой статье описывается этот алгоритм.

В 1995 году Абрамов, Бронштейн и Петковшек показали, что полиномиальный случай может быть решен более эффективно, если рассматривать решение рекуррентного уравнения степенным рядом в определенном степенном базисе (т.е. не в обычном базисе). ${\textstyle (x^{n})_{n\in \mathbb {N} }}$).

Другие алгоритмы, вычисляющие рациональные или гипергеометрические решения линейного рекуррентного уравнения с полиномиальными коэффициентами, также используют алгоритмы, вычисляющие полиномиальные решения.

Степень привязана

Позволять ${\textstyle \mathbb {K} }$ — поле нулевой характеристики и ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ рекуррентное уравнение порядка ${\textstyle r}$ с полиномиальными коэффициентами ${\textstyle p_{k}\in \mathbb {K} [n]}$, полиномиальная правая часть ${\textstyle f\in \mathbb {K} [n]}$ и неизвестная полиномиальная последовательность $y(n)\in \mathbb {K} [n]$. Более того ${\textstyle \deg(p)}$ обозначает степень многочлена ${\textstyle p\in \mathbb {K} [n]}$ (с ${\textstyle \deg(0)=-\infty }$ для нулевого полинома) и ${\textstyle {\text{lc}}(p)}$ обозначает старший коэффициент многочлена. Более того, пусть $${\begin{aligned}q_{i}&=\sum _{k=i}^{r}{\binom {k}{i}}p_{k},&b&=\max _{i=0,\dots ,r}(\deg(q_{i})-i),\\\alpha (n)&=\sum _{i=0,\dots ,r \atop \deg(q_{i})-i=b}{\text{lc}}(q_{i})n^{\underline {i}},&d_{\alpha }&=\max\{n\in \mathbb {N} \,:\,\alpha (n)=0\}\cup \{-\infty \}\end{aligned}}$$для ${\textstyle i=0,\dots ,r}$ где ${\textstyle n^{\underline {i}}=n(n-1)\cdots (n-i+1)}$ обозначает падающий факториал и ${\textstyle \mathbb {N} }$ множество неотрицательных целых чисел. Затем ${\textstyle \deg(y)\leq \max\{\deg(f)-b,-b-1,d_{\alpha }\}}$. Это называется оценкой степени полиномиального решения. ${\textstyle y}$. Эту границу показали Абрамов и Петковшек.

Алгоритм

Алгоритм состоит из двух шагов. На первом этапе граница степени вычисляется . На втором этапе анзац с полиномом ${\textstyle y}$ этой степени с произвольными коэффициентами в ${\textstyle \mathbb {K} }$ составляется и подставляется в рекуррентное уравнение. Затем сравниваются различные степени и формируется система линейных уравнений для коэффициентов ${\textstyle y}$ устанавливается и решается. Это называется методом неопределенных коэффициентов . Алгоритм возвращает общее полиномиальное решение рекуррентного уравнения.

algorithm polynomial_solutions is
    input: Linear recurrence equation ${\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}$.
    output: The general polynomial solution ${\textstyle y}$ if there are any solutions, otherwise false.

    for ${\textstyle i=0,\dots ,r}$ do
        ${\textstyle q_{i}=\sum _{k=i}^{r}{\binom {k}{i}}p_{k}}$
    repeat
    ${\textstyle b=\max _{i=0,\dots ,r}(\deg(q_{i})-i)}$
    ${\textstyle \alpha (n)=\sum _{i=0,\dots ,r \atop \deg(q_{i})-i=b}{\text{lc}}(q_{i})n^{\underline {i}}}$
    ${\textstyle d_{\alpha }=\max\{n\in \mathbb {N} \,:\,\alpha (n)=0\}\cup \{-\infty \}}$
    ${\textstyle d=\max\{\deg(f)-b,-b-1,d_{\alpha }\}}$
    ${\textstyle y(n)=\sum _{j=0}^{d}y_{j}n^{j}}$ with unknown coefficients ${\textstyle y_{j}\in \mathbb {K} }$ for ${\textstyle j=0,\dots ,d}$
    Compare coefficients of polynomials ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)}$ and ${\textstyle f(n)}$ to get possible values for ${\textstyle y_{j},j=0,\dots ,d}$
    if there are possible values for ${\textstyle y_{j}}$ then
        return general solution ${\textstyle y}$
    else
        return false
    end if

Пример

Применение формулы оценки степени к рекуррентному уравнению $$(n^{2}-2)\,y(n)+(-n^{2}+2n)\,y(n+1)=2n,$$над ${\textstyle \mathbb {Q} }$ урожайность ${\textstyle \deg(y)\leq 2}$. Следовательно, можно использовать анзац с квадратичным многочленом ${\textstyle y(n)=y_{2}n^{2}+y_{1}n+y_{0}}$ с ${\textstyle y_{0},y_{1},y_{2}\in \mathbb {Q} }$. Подстановка этого анзаца в исходное рекуррентное уравнение приводит к $$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}.$$Это эквивалентно следующей системе линейных уравнений $${\begin{aligned}{\begin{pmatrix}0&1&1\\2&0&2\\-2&0&0\end{pmatrix}}{\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}0\\2\\0\end{pmatrix}}\end{aligned}}$$с решением ${\textstyle y_{0}=0,y_{1}=-1,y_{2}=1}$. Следовательно, единственным полиномиальным решением является ${\textstyle y(n)=n^{2}-n}$.