Полиномиальные решения P-рекурсивных уравнений - Polynomial solutions of P-recursive equations

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

В 1995 году Абрамов, Бронштейн и Петковшек показали, что полиномиальный случай может быть решен более эффективно, рассматривая решение рекуррентного уравнения в виде степенного ряда в конкретном степенном базисе (т.е. не в обычном базисе ).

Другие алгоритмы, которые вычисляют рациональные или гипергеометрические решения линейного рекуррентного уравнения с полиномиальными коэффициентами, также используют алгоритмы, которые вычисляют полиномиальные решения.

Градус

Пусть быть полем нулевой характеристики и в рекуррентном уравнении порядка с полиномиальными коэффициентами , полиномиальной правых и неизвестной полиномиальной последовательности . Кроме того, обозначает степень многочлена (с для нулевого многочлена) и обозначает старший коэффициент многочлена. Кроме того, пусть

для где обозначает падающий факториал и набор неотрицательных целых чисел. Тогда . Это называется степенью полиномиального решения . Эту границу показали Абрамов и Петковшек.

Алгоритм

Алгоритм состоит из двух шагов. На первом этапе вычисляется граница степени . На втором этапе составляется анзац с многочленом этой степени с произвольными коэффициентами, который вставляется в рекуррентное уравнение. Затем сравниваются разные мощности и составляется и решается система линейных уравнений для коэффициентов . Это называется

методом неопределенных коэффициентов . Алгоритм возвращает общее полиномиальное решение рекуррентного уравнения.
algorithm polynomial_solutions is
    input: Linear recurrence equation .
    output: The general polynomial solution  if there are any solutions, otherwise false.

    for  do
        
    repeat
    
    
    
    
     with unknown coefficients  for 
    Compare coefficients of polynomials  and  to get possible values for 
    if there are possible values for  then
        return general solution 
    else
        return false
    end if

Пример

Применяя формулу оценки степени к рекуррентному уравнению

над урожайностью . Следовательно, можно использовать анзац с квадратичным многочленом с . Подстановка этого анзаца в исходное рекуррентное уравнение приводит к
Это эквивалентно следующей системе линейных уравнений
с раствором . Следовательно, единственным полиномиальным решением является .

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

  1. ^ a b Абрамов, Сергей А. (1989). «Проблемы компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений». Московский университет "Вычислительная математика и кибернетика" . 3 .
  2. ^ a b Петковшек, Марко (1992). «Гипергеометрические решения линейных возвращений с полиномиальными коэффициентами» . Журнал символических вычислений . 14 (2–3): 243–264. DOI : 10.1016 / 0747-7171 (92) 90038-6 . ISSN  0747-7171 .
  3. ^ а б Абрамов, Сергей А .; Бронштейн, Мануэль; Петковшек, Марко (1995). О полиномиальных решениях линейных операторных уравнений . ISSAC '95 Труды Международного симпозиума 1995 года по символьным и алгебраическим вычислениям . ACM. С. 290–296. CiteSeerX  10.1.1.46.9373 . DOI : 10.1145 / 220346.220384 . ISBN 978-0897916998.
  4. ^ Weixlbaumer, Кристиан (2001). Решения разностных уравнений с полиномиальными коэффициентами . Дипломная работа, Университет Иоганна Кеплера в Линце
  5. ^ Петковшек, Марко; Wilf, Herbert S .; Зейлбергер, Дорон (1996). А = В . А.К. Петерс. ISBN 978-1568810638. OCLC  33898705 .