Алгоритм Абрамова - Abramov's algorithm

В математике, особенно в компьютерной алгебре , алгоритм Абрамова вычисляет все рациональные решения линейного рекуррентного уравнения с полиномиальными коэффициентами . Алгоритм был опубликован Сергеем А. Абрамовым в 1989 году.

Универсальный знаменатель

Основное понятие в алгоритме Абрамова - универсальный знаменатель. Пусть быть полем из характеристического нуля. Дисперсию двух многочленов , определяется как

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

Алгоритм

Позвольте снова быть

рекуррентным уравнением с полиномиальными коэффициентами и универсальным знаменателем. После замены неизвестного полинома и задания рекуррентного уравнения эквивалентно
В качестве отмены это линейное рекуррентное уравнение с полиномиальными коэффициентами, которое может быть решено для неизвестного полиномиального решения . Существуют
алгоритмы поиска полиномиальных решений . Затем решения для можно снова использовать для вычисления рациональных решений .
algorithm rational_solutions is
    input: Linear recurrence equation .
    output: The general rational solution  if there are any solutions, otherwise false.

    
    
    
    Solve  for general polynomial solution 
    if solution  exists then
        return general solution 
    else
        return false
    end if

пример

Однородное рекуррентное уравнение порядка

более имеет рациональное решение. Его можно вычислить, рассматривая дисперсию
Это дает следующий универсальный знаменатель:
и
Умножение исходного рекуррентного уравнения на и подстановка приводит к
Это уравнение имеет полиномиальное решение для произвольной постоянной . Использование общего рационального решения
для произвольного .

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

  1. Абрамов, Сергей А. (1989). «Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами». Вычислительная математика и математическая физика СССР . 29 (6): 7–12. DOI : 10.1016 / s0041-5553 (89) 80002-3 . ISSN   0041-5553 .
  2. ^ a b Абрамов, Сергей А. (1995). Рациональные решения линейных разностных и q-разностных уравнений с полиномиальными коэффициентами . ISSAC '95 Труды Международного симпозиума 1995 года по символьным и алгебраическим вычислениям . С. 285–289. DOI : 10.1145 / 220346.220383 . ISBN   978-0897916998 .
  3. Ман, Ю-Квонг; Райт, Фрэнсис Дж. (1994). Быстрое вычисление полиномиальной дисперсии и его применение к неопределенному суммированию . ISSAC '94 Труды Международного симпозиума по символьным и алгебраическим вычислениям . С. 175–180. DOI : 10.1145 / 190347.190413 . ISBN   978-0897916387 .
  4. ^ Герхард, Юрген (2005). Модульные алгоритмы в символьном суммировании и символьном интегрировании . Конспект лекций по информатике . 3218 . DOI : 10.1007 / b104035 . ISBN   978-3-540-24061-7 . ISSN   0302-9743 .
  5. ^ Чен, Уильям YC; Пол, Питер; Саад, Хусам Л. (2007). «Сходясь к алгоритму Госпера». Arxiv : 0711.3386 [ math.CA ].
Викиданные-logo.svg WikiProject Mathematics на Викиданных Викиданные-logo.svg