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