P-рекурсивное уравнение

Линейное рекуррентное уравнение

В математике P-рекурсивное уравнение — это линейное уравнение последовательностей , где последовательности коэффициентов могут быть представлены в виде полиномов . P-рекурсивные уравнения — это линейные рекуррентные уравнения (или линейные рекуррентные соотношения или линейные разностные уравнения) с полиномиальными коэффициентами. Эти уравнения играют важную роль в различных областях математики, в частности в комбинаторике . Последовательности, которые являются решениями этих уравнений, называются голономными , P-рекурсивными или D-конечными.

С конца 1980-х годов были разработаны первые алгоритмы для поиска решений этих уравнений. Сергей А. Абрамов, Марко Петковшек и Марк ван Хой описали алгоритмы для поиска полиномиальных, рациональных, гипергеометрических и даламбертовых решений.

Определение

Пусть — поле нулевой характеристики (например , ), полиномы для , последовательность и неизвестная последовательность. Уравнение называется линейным рекуррентным уравнением с полиномиальными коэффициентами (все рекуррентные уравнения в этой статье имеют такой вид). Если и оба отличны от нуля, то называется порядком уравнения. Если равно нулю, уравнение называется однородным, в противном случае — неоднородным. ${\textstyle \mathbb {K} }$ ${\textstyle \mathbb {K} =\mathbb {Q} }$ ${\textstyle p_{k}(n)\in \mathbb {K} [n]}$ ${\textstyle k=0,\dots ,r}$ ${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$ ${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$ $${\displaystyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$$ ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\textstyle r}$ ${\textstyle f}$

Это также можно записать как, где — линейный рекуррентный оператор с полиномиальными коэффициентами, а — оператор сдвига, т.е. . ${\textstyle Ly=f}$ ${\textstyle L=\sum _{k=0}^{r}p_{k}N^{k}}$ ${\textstyle N}$ ${\textstyle N\,y(n)=y(n+1)}$

Решения закрытой формы

Пусть или эквивалентно — рекуррентное уравнение с полиномиальными коэффициентами. Существует несколько алгоритмов, которые вычисляют решения этого уравнения. Эти алгоритмы могут вычислять полиномиальные, рациональные, гипергеометрические и даламберовские решения. Решение однородного уравнения задается ядром линейного рекуррентного оператора: . Как подпространство пространства последовательностей это ядро ​​имеет базис . ^[1] Пусть — базис , тогда формальная сумма для произвольных констант называется общим решением однородной задачи . Если — частное решение , т. е . , то — также решение неоднородной задачи и называется общим решением неоднородной задачи. ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ ${\textstyle Ly=f}$ ${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$ ${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$ ${\textstyle \ker L}$ ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}}$ ${\textstyle c_{1},\dots ,c_{m}\in \mathbb {K} }$ ${\textstyle Ly=0}$ ${\textstyle {\tilde {y}}}$ ${\textstyle Ly=f}$ ${\textstyle L{\tilde {y}}=f}$ ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}+{\tilde {y}}}$

Полиномиальные решения

В конце 1980-х годов Сергей А. Абрамов описал алгоритм, который находит общее полиномиальное решение рекуррентного уравнения, т. е . с полиномиальной правой частью . Он (и несколько лет спустя Марко Петковшек ) дал оценку степени для полиномиальных решений. Таким образом, задача может быть просто решена путем рассмотрения системы линейных уравнений . ^{[2] [3] [4]} В 1995 году Абрамов, Бронштейн и Петковшек показали, что полиномиальный случай может быть решен более эффективно путем рассмотрения решения рекуррентного уравнения в виде степенного ряда в определенном степенном базисе (т. е. не в обычном базисе ). ^[5] ${\textstyle y(n)\in \mathbb {K} [n]}$ ${\textstyle f(n)\in \mathbb {K} [n]}$ ${\textstyle (x^{n})_{n\in \mathbb {N} }}$

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

Рациональные решения

В 1989 году Сергей А. Абрамов показал, что общее рациональное решение, т. е . , с полиномиальной правой частью , может быть найдено с помощью понятия универсального знаменателя. Универсальный знаменатель — это многочлен, такой что знаменатель каждого рационального решения делит . Абрамов показал, как этот универсальный знаменатель может быть вычислен с использованием только первого и последнего коэффициента многочлена и . Подстановка этого универсального знаменателя вместо неизвестного знаменателя всех рациональных решений может быть найдена путем вычисления всех полиномиальных решений преобразованного уравнения. ^[6] ${\textstyle y(n)\in \mathbb {K} (n)}$ ${\textstyle f(n)\in \mathbb {K} [n]}$ ${\textstyle u}$ ${\textstyle u}$ ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\displaystyle y}$

Гипергеометрическое решение

Последовательность называется гипергеометрической, если отношение двух последовательных членов является рациональной функцией в , т.е. . Это имеет место тогда и только тогда, когда последовательность является решением рекуррентного уравнения первого порядка с полиномиальными коэффициентами. Множество гипергеометрических последовательностей не является подпространством пространства последовательностей, поскольку оно не замкнуто относительно сложения. ${\textstyle y(n)}$ ${\displaystyle n}$ ${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$

В 1992 году Марко Петковшек дал алгоритм для получения общего гипергеометрического решения рекуррентного уравнения, где правая часть является суммой гипергеометрических последовательностей. Алгоритм использует нормальную форму Госпера-Петковшека рациональной функции. С этим конкретным представлением снова достаточно рассмотреть полиномиальные решения преобразованного уравнения. ^[3] ${\displaystyle f}$

Другой и более эффективный подход принадлежит Марку ван Хёйю. Рассматривая корни первого и последнего коэффициента полинома и – называемые сингулярностями – можно построить решение шаг за шагом, используя тот факт, что каждая гипергеометрическая последовательность имеет представление формы для некоторых с для и . Здесь обозначает гамма-функцию и алгебраическое замыкание поля . Тогда должны быть сингулярностями уравнения (т.е. корнями или ). Кроме того, можно вычислить границы для показателей степеней . Для фиксированных значений можно сделать анзац, который дает кандидатов для . Для конкретного можно снова сделать анзац, чтобы получить рациональную функцию с помощью алгоритма Абрамова. Рассматривая все возможности, получаем общее решение рекуррентного уравнения. ^{[7] [8]} ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\textstyle y(n)}$ $${\displaystyle y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$ ${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$ ${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$ ${\textstyle i\neq j}$ ${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$ ${\textstyle \Gamma (n)}$ ${\textstyle {\overline {\mathbb {K} }}}$ ${\textstyle \mathbb {K} }$ ${\textstyle \xi _{1},\dots ,\xi _{s}}$ ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\textstyle e_{i}}$ ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$ ${\textstyle z}$ ${\textstyle z}$ ${\textstyle r(n)}$

Решения Даламбера

Последовательность называется даламбертовой, если для некоторых гипергеометрических последовательностей и означает, что где обозначает оператор разности, т.е. Это имеет место тогда и только тогда, когда существуют линейные рекуррентные операторы первого порядка с рациональными коэффициентами, такие, что . ^[4] ${\displaystyle y}$ ${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$ ${\textstyle h_{1},\dots ,h_{k}}$ ${\textstyle y=\sum x}$ ${\textstyle \Delta y=x}$ ${\textstyle \Delta }$ ${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$ ${\textstyle L_{1},\dots ,L_{k}}$ ${\textstyle L_{k}\cdots L_{1}y=0}$

1994 Абрамов и Петковшек описали алгоритм, который вычисляет общее решение Даламбера рекуррентного уравнения. Этот алгоритм вычисляет гипергеометрические решения и рекурсивно уменьшает порядок рекуррентного уравнения. ^[9]

Примеры

Матрицы перестановок со знаком

Число знаковых матриц перестановки размера можно описать последовательностью . Знаковая матрица перестановки — это квадратная матрица, которая имеет ровно один ненулевой элемент в каждой строке и в каждом столбце. Ненулевыми элементами могут быть . Последовательность определяется линейным рекуррентным уравнением с полиномиальными коэффициентами и начальными значениями . Применяя алгоритм для поиска гипергеометрических решений, можно найти общее гипергеометрическое решение для некоторой константы . Также учитывая начальные значения, последовательность описывает число знаковых матриц перестановки. ^[10] ${\displaystyle n\times n}$ ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$ ${\textstyle \pm 1}$ $${\displaystyle y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$ ${\textstyle y(0)=1,y(1)=2}$ $${\displaystyle y(n)=c\,2^{n}n!}$$ ${\textstyle c}$ ${\textstyle y(n)=2^{n}n!}$

Инволюции

Число инволюций множества с элементами задается рекуррентным уравнением. Применяя, например, алгоритм Петковшека, можно увидеть, что для этого рекуррентного уравнения не существует полиномиального, рационального или гипергеометрического решения. ^[4] ${\textstyle y(n)}$ ${\textstyle n}$ $${\displaystyle y(n)=(n-1)\,y(n-2)+y(n-1).}$$

Приложения

Функция называется гипергеометрической, если где обозначает рациональные функции в и . Гипергеометрическая сумма — это конечная сумма вида, где является гипергеометрической. Творческий телескопический алгоритм Зейльбергера может преобразовать такую ​​гипергеометрическую сумму в рекуррентное уравнение с полиномиальными коэффициентами. Затем это уравнение можно решить, чтобы получить, например, линейную комбинацию гипергеометрических решений, которая называется решением в замкнутой форме . ^[4] ${\textstyle F(n,k)}$ ${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$ ${\textstyle \mathbb {K} (n,k)}$ ${\textstyle n}$ ${\textstyle k}$ ${\textstyle f(n)=\sum _{k}F(n,k)}$ ${\textstyle F(n,k)}$ ${\textstyle f}$

Ссылки

1. Если последовательности считаются равными, если они равны почти во всех членах, то этот базис конечен. Подробнее об этом можно прочитать в книге A=B Петковшека, Вильфа и Зейлбергера.
2. Абрамов, Сергей А. (1989). «Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений». Московский университет вычислительной математики и кибернетики . 3 .
3. Petkovšek, Marko (1992). «Гипергеометрические решения линейных рекуррент с полиномиальными коэффициентами». Journal of Symbolic Computation . 14 (2–3): 243–264. doi :10.1016/0747-7171(92)90038-6. ISSN  0747-7171.
4. Петковшек, Марко; Уилф, Герберт С.; Зейлбергер, Дорон (1996). А=Б. АК Петерс. ISBN 978-1568810638. OCLC  33898705.
5. Абрамов, Сергей А.; Бронштейн, Мануэль; Петковшек, Марко (1995). "О полиномиальных решениях линейных операторных уравнений". Труды международного симпозиума 1995 года по символьным и алгебраическим вычислениям - ISSAC '95 . ACM. С. 290–296. CiteSeerX 10.1.1.46.9373 . doi :10.1145/220346.220384. ISBN  978-0897916998. S2CID  14963237.
6. Абрамов, Сергей А. (1989). «Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами». Журнал вычислительной математики и математической физики СССР . 29 (6): 7–12. doi :10.1016/s0041-5553(89)80002-3. ISSN  0041-5553.
7. Ван Хой, Марк (1999). «Конечные сингулярности и гипергеометрические решения линейных рекуррентных уравнений». Журнал чистой и прикладной алгебры . 139 (1–3): 109–131. doi :10.1016/s0022-4049(99)00008-0. ISSN  0022-4049.
8. Cluzeau, Thomas; van Hoeij, Mark (2006). «Вычисление гипергеометрических решений линейных рекуррентных уравнений». Прикладная алгебра в машиностроении, связи и вычислениях . 17 (2): 83–115. doi :10.1007/s00200-005-0192-x. ISSN  0938-1279. S2CID  7496623.
9. Абрамов, Сергей А.; Петковшек, Марко (1994). "Д'Аламберовы решения линейных дифференциальных и разностных уравнений". Труды международного симпозиума по символьным и алгебраическим вычислениям - ISSAC '94 . ACM. стр. 169–174. doi :10.1145/190347.190412. ISBN 978-0897916387. S2CID  2802734.
10. "A000165 - OEIS". oeis.org . Получено 2018-07-02 .