Полиномиальные решения P-рекурсивных уравнений - Polynomial solutions of P-recursive equations
В математике P-рекурсивное уравнение может быть решено для полиномиальных решений . Сергей А. Абрамов в 1989 г. и Марко Петковшек в 1992 г. описали алгоритм, который находит все полиномиальные решения этих рекуррентных уравнений с полиномиальными коэффициентами. Алгоритм вычисляет степень решения на первом этапе. На втором этапе используется анзац для полинома этой степени, и неизвестные коэффициенты вычисляются с помощью системы линейных уравнений . Эта статья описывает этот алгоритм.
В 1995 году Абрамов, Бронштейн и Петковшек показали, что полиномиальный случай может быть решен более эффективно, рассматривая решение рекуррентного уравнения в виде степенного ряда в конкретном степенном базисе (т.е. не в обычном базисе ).
Другие алгоритмы, которые вычисляют рациональные или гипергеометрические решения линейного рекуррентного уравнения с полиномиальными коэффициентами, также используют алгоритмы, которые вычисляют полиномиальные решения.
Пусть быть полем нулевой характеристики и в рекуррентном уравнении порядка с полиномиальными коэффициентами , полиномиальной правых и неизвестной полиномиальной последовательности . Кроме того, обозначает степень многочлена (с для нулевого многочлена) и обозначает старший коэффициент многочлена. Кроме того, пусть
для где обозначает падающий факториал и набор неотрицательных целых чисел. Тогда . Это называется степенью полиномиального решения . Эту границу показали Абрамов и Петковшек.
Алгоритм
Алгоритм состоит из двух шагов. На первом этапе вычисляется граница степени . На втором этапе составляется анзац с многочленом этой степени с произвольными коэффициентами, который вставляется в рекуррентное уравнение. Затем сравниваются разные мощности и составляется и решается система линейных уравнений для коэффициентов . Это называется
методом неопределенных коэффициентов . Алгоритм возвращает общее полиномиальное решение рекуррентного уравнения.
algorithm polynomial_solutions isinput: Linear recurrence equation .
output: The general polynomial solution if there are any solutions, otherwise false.
fordorepeat with unknown coefficients for
Compare coefficients of polynomials and to get possible values for if there are possible values for thenreturn general solution elsereturn false
end if
Пример
Применяя формулу оценки степени к рекуррентному уравнению
над урожайностью . Следовательно, можно использовать анзац с квадратичным многочленом с . Подстановка этого анзаца в исходное рекуррентное уравнение приводит к
Это эквивалентно следующей системе линейных уравнений
с раствором . Следовательно, единственным полиномиальным решением является .
Рекомендации
^ a b
Абрамов, Сергей А. (1989). «Проблемы компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений». Московский университет "Вычислительная математика и кибернетика" . 3 .
^ а б Абрамов, Сергей А .; Бронштейн, Мануэль; Петковшек, Марко (1995). О полиномиальных решениях линейных операторных уравнений . ISSAC '95 Труды Международного симпозиума 1995 года по символьным и алгебраическим вычислениям . ACM. С. 290–296. CiteSeerX 10.1.1.46.9373 . DOI : 10.1145 / 220346.220384 . ISBN978-0897916998.