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

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

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

Определение

Пусть будет поле характеристики нуль (например ), многочлены для , последовательность и неизвестная последовательность. Уравнение${\ textstyle \ mathbb {K}}$${\ textstyle \ mathbb {K} = \ mathbb {Q}}$${\ textstyle p_ {k} (n) \ in \ mathbb {K} [n]}$${\ textstyle к = 0, \ точки, г}$${\ textstyle f \ in \ mathbb {K} ^ {\ mathbb {N}}}$${\ textstyle y \ in \ mathbb {K} ^ {\ mathbb {N}}}$

называется линейным рекуррентным уравнением с полиномиальными коэффициентами (все рекуррентные уравнения в этой статье имеют именно такой вид). Если и оба отличны от нуля, то это называется порядком уравнения. Если равен нулю, уравнение называется однородным, в противном случае - неоднородным. ${\ textstyle p_ {0}}$${\ textstyle p_ {r}}$${\ textstyle r}$${\ textstyle f}$

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

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

Пусть или, что то же самое, рекуррентное уравнение с полиномиальными коэффициентами. Существует несколько алгоритмов, которые вычисляют решения этого уравнения. Эти алгоритмы могут вычислять полиномиальные, рациональные, гипергеометрические и даламбертовские решения. Решение однородного уравнения дается ядром линейного оператора повторения: . Как подпространство пространства последовательностей это ядро ​​имеет базис . Пусть - базис , тогда формальная сумма для произвольных постоянных называется общим решением однородной задачи . Если - частное решение , т. Е. Также является решением неоднородной задачи и называется общим решением неоднородной задачи. ${\ textstyle \ сумма _ {к = 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)}, \ точки, 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 {\ тильда {y}}}$${\ textstyle Ly = f}$${\ textstyle L {\ тильда {y}} = f}$${\ textstyle c_ {1} y ^ {(1)} + \ dots + c_ {m} y ^ {(m)} + {\ тильда {y}}}$

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

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

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

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

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

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

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

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

Другой и более эффективный подход разработан Марком ван Хойджем. Рассматривая корни первого и последнего полинома коэффициентов и - так называемые особенности - можно шаг за шагом построить решение, используя тот факт, что каждая гипергеометрическая последовательность имеет представление вида${\ textstyle p_ {0}}$${\ textstyle p_ {r}}$${\ textstyle у (п)}$

для некоторых с for и . Здесь обозначает гамма - функцию и на алгебраическое замыкание поля . Тогда должны быть особенности уравнения (т.е. корни или ). Кроме того, можно вычислить оценки показателей . Для фиксированных значений можно составить анзац, который дает кандидатов . Для конкретного можно снова составить анзац, чтобы получить рациональную функцию по алгоритму Абрамова. Рассматривая все возможности, получаем общее решение рекуррентного уравнения. ${\ 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 (п)}$${\ 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)}$

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

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

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

Примеры

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

Число матриц перестановки со знаком размера может быть описано

последовательностью . Матрица перестановки со знаком - это квадратная матрица, которая имеет ровно одну ненулевую запись в каждой строке и в каждом столбце. Ненулевые записи могут быть . Последовательность определяется линейным рекуррентным уравнением с полиномиальными коэффициентами${\ Displaystyle п \ раз п}$ ${\ textstyle у (п) \ в \ mathbb {Q} ^ {\ mathbb {N}}}$${\ textstyle \ pm 1}$

$${\ Displaystyle у (п) = 4 (п-1) ^ {2} \, у (п-2) +2 \, у (п-1)}$$

и начальные значения . Применяя алгоритм для поиска гипергеометрических решений, можно найти общее гипергеометрическое решение${\ textstyle y (0) = 1, y (1) = 2}$

$${\ Displaystyle у (п) = с \, 2 ^ {п} п!}$$

для некоторой константы . Также с учетом начальных значений последовательность описывает количество матриц перестановки со знаком. ${\ textstyle c}$${\ textstyle у (п) = 2 ^ {п} п!}$

Инволюции

Число инволюций множества с элементами задается рекуррентным уравнением${\ textstyle у (п)}$${\ textstyle n}$

$${\ Displaystyle у (п) = (п-1) \, у (п-2) + у (п-1).}$$

Применяя, например , алгоритм Петковшека, можно увидеть, что для этого рекуррентного уравнения не существует полиномиального, рационального или гипергеометрического решения.

Приложения

Функция называется гипергеометрической, если где обозначает рациональные функции в и . Гипергеометрическая сумма - это конечная сумма вида где гипергеометрическая.

Zeilberger «s творческий алгоритм телескопического может превратить такую гипергеометрическую сумму в рекуррентном уравнение с полиномиальными коэффициентами. Это уравнение затем может быть решено, чтобы получить, например, линейную комбинацию гипергеометрических решений, которая называется решением замкнутой формы . ${\ textstyle F (п, к)}$${\ textstyle F (n, k + 1) / F (n, k), F (n + 1, k) / F (n, k) \ in \ mathbb {K} (n, k)}$${\ textstyle \ mathbb {K} (п, к)}$${\ textstyle n}$${\ textstyle k}$${\ textstyle f (n) = \ сумма _ {k} F (n, k)}$${\ textstyle F (п, к)}$${\ textstyle f}$

Рекомендации

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