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}}}$ неизвестная последовательность. Уравнение

{ Displaystyle сумма _ {к = 0} ^ {г} р_ {к} (п) , у (п + к) = е (п)}

называется линейным рекуррентным уравнением с полиномиальными коэффициентами (все рекуррентные уравнения в этой статье имеют именно такой вид). Если

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

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

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

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

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

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

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

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

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

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

{ 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 (п)}

обозначает Гамма-функция и

{ textstyle { overline { mathbb {K}}}}

то алгебраическое замыкание поля

{ textstyle mathbb {K}}

. Тогда

{ textstyle xi _ {1}, точки, 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)}

по алгоритму Абрамова. Рассматривая все возможности, получаем общее решение рекуррентного уравнения.^[7]^[8]

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

Последовательность ${ 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}$ .^[4]

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

Примеры

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

Количество матрицы перестановок со знаком размера ${ 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 ^ {п} п!}

описывает количество матриц перестановок со знаком.^[10]

Инволюции

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

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

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

Приложения

Функция ${ 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 (п, к)}$ гипергеометрический. Zeilberger Творческий алгоритм телескопирования может преобразовать такую гипергеометрическую сумму в рекуррентное уравнение с полиномиальными коэффициентами. Затем это уравнение может быть решено, чтобы получить, например, линейную комбинацию гипергеометрических решений, которая называется решением замкнутой формы ${ textstyle f}$ .^[4]

использованная литература

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

[1] Если последовательности считаются равными, если они равны почти во всех членах, то этот базис конечен. Подробнее об этом можно прочитать в книге Петковшека, Вильфа и Цайльбергера A = B.

[2] Абрамов, Сергей А. (1989). «Проблемы компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений». Московский университет Вычислительная математика и кибернетика. 3.

[Petkovšek_1992-3] а ^б Петковшек, Марко (1992). «Гипергеометрические решения линейных рекуррент с полиномиальными коэффициентами». Журнал символических вычислений. 14 (2–3): 243–264. Дои:10.1016/0747-7171(92)90038-6. ISSN 0747-7171.

[Petkovšek_1996-4] а ^б ^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. Дои:10.1145/220346.220384. ISBN 978-0897916998.

[6] Абрамов, Сергей А. (1989). «Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами». Вычислительная математика и математическая физика СССР. 29 (6): 7–12. Дои:10.1016 / с0041-5553 (89) 80002-3. ISSN 0041-5553.

[7] Ван Хойдж, Марк (1999). «Конечные особенности и гипергеометрические решения линейных рекуррентных уравнений». Журнал чистой и прикладной алгебры. 139 (1–3): 109–131. Дои:10.1016 / с0022-4049 (99) 00008-0. ISSN 0022-4049.

[8] Клюзо, Томас; ван Хойдж, Марк (2006). «Вычисление гипергеометрических решений линейных рекуррентных уравнений». Применимая алгебра в инженерии, коммуникации и вычислениях. 17 (2): 83–115. Дои:10.1007 / s00200-005-0192-x. ISSN 0938-1279.

[9] Абрамов, Сергей А .; Петковшек, Марко (1994). Решения Даламбера линейных дифференциальных и разностных уравнений. ISSAC '94 Труды Международного симпозиума по символьным и алгебраическим вычислениям. ACM. С. 169–174. Дои:10.1145/190347.190412. ISBN 978-0897916387.

[10] "A000165 - OEIS". oeis.org. Получено 2018-07-02.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]