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

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

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

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

Степень ограничена

Пусть будет полем характеристики ноль и рекуррентным уравнением порядка с полиномиальными коэффициентами , полиномиальной правой частью и неизвестной полиномиальной последовательностью . Кроме того, обозначает степень полинома (с для нулевого полинома) и обозначает старший коэффициент полинома. Более того, пусть для , где обозначает падающий факториал и множество неотрицательных целых чисел. Тогда . Это называется границей степени для полиномиального решения . Эта граница была показана Абрамовым и Петковшеком. ^{[1] [2] [3] [4]} ${\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]}$ ${\displaystyle y(n)\in \mathbb {K} [n]}$ ${\textstyle \deg(p)}$ ${\textstyle p\in \mathbb {K} [n]}$ ${\textstyle \deg(0)=-\infty }$ ${\textstyle {\text{lc}}(p)}$ $${\displaystyle {\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}$

Алгоритм

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

Алгоритм polynomial_solutions имеет  входные данные: Линейное рекуррентное уравнение . Выходные данные: Общее полиномиальное решение , если таковые имеются, в противном случае false. ${\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}$ ${\textstyle y}$ для  повторить с неизвестными коэффициентами для Сравнить коэффициенты многочленов и получить возможные значения для если есть возможные значения для тогда вернуть общее решение иначе вернуть false конец если ${\textstyle i=0,\dots ,r}$   ${\textstyle q_{i}=\sum _{k=i}^{r}{\binom {k}{i}}p_{k}}$   ${\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}}$ ${\textstyle y_{j}\in \mathbb {K} }$ ${\textstyle j=0,\dots ,d}$ ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)}$ ${\textstyle f(n)}$ ${\textstyle y_{j},j=0,\dots ,d}$  ${\textstyle y_{j}}$   ${\textstyle y}$  

Пример

Применение формулы для степени ограничения к рекуррентному уравнению над дает . Следовательно, можно использовать анзац с квадратичным полиномом с . Подстановка этого анзаца в исходное рекуррентное уравнение приводит к Это эквивалентно следующей системе линейных уравнений с решением . Поэтому единственным полиномиальным решением является . $${\displaystyle (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} }$ $${\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}.}$$ $${\displaystyle {\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}$

Ссылки

1. Абрамов, Сергей А. (1989). «Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений». Московский университет вычислительной математики и кибернетики . 3 .
2. Petkovšek, Marko (1992). «Гипергеометрические решения линейных рекуррент с полиномиальными коэффициентами». Journal of Symbolic Computation . 14 (2–3): 243–264. doi : 10.1016/0747-7171(92)90038-6 . ISSN  0747-7171.
3. Абрамов, Сергей А.; Бронштейн, Мануэль; Петковшек, Марко (1995). "О полиномиальных решениях линейных операторных уравнений". Труды международного симпозиума 1995 года по символьным и алгебраическим вычислениям - ISSAC '95 . ACM. С. 290–296. CiteSeerX 10.1.1.46.9373 . doi :10.1145/220346.220384. ISBN  978-0897916998. S2CID  14963237.
4. Weixlbaumer, Christian (2001). Решения разностных уравнений с полиномиальными коэффициентами. Дипломная работа, Johannes Kepler Universität Linz
5. Петковшек, Марко; Уилф, Герберт С.; Зейлбергер, Дорон (1996). А=Б. АК Петерс. ISBN 978-1568810638. OCLC  33898705.