Основное понятие в алгоритме Абрамова - универсальный знаменатель. Пусть быть полем из характеристического нуля. Дисперсию двух многочленов , определяется как
где обозначает множество неотрицательных целых чисел. Следовательно, дисперсия является максимальной , так что полином и полином, сдвинутый во времени, имеют общий множитель. Это если такого не существует. Дисперсия может быть вычислена как наибольший целым неотрицательным корень из результирующих . Пусть - рекуррентное уравнение порядка с полиномиальными коэффициентами , полиномиальной правой частью и решением рациональной последовательности . Можно написать для двух относительно простых многочленов . Пусть и
где обозначает падающий факториал функции. Потом делит . Таким образом, многочлен можно использовать в качестве знаменателя для всех рациональных решений и, следовательно, он называется универсальным знаменателем.
В качестве отмены это линейное рекуррентное уравнение с полиномиальными коэффициентами, которое может быть решено для неизвестного полиномиального решения . Существуют алгоритмы поиска полиномиальных решений . Затем решения для можно снова использовать для вычисления рациональных решений .
algorithm rational_solutions isinput: Linear recurrence equation .
output: The general rational solution if there are any solutions, otherwise false.
Solve for general polynomial solution if solution exists thenreturn general solution elsereturn false
end if
пример
Однородное рекуррентное уравнение порядка
более имеет рациональное решение. Его можно вычислить, рассматривая дисперсию
Это дает следующий универсальный знаменатель:
и
Умножение исходного рекуррентного уравнения на и подстановка приводит к
Это уравнение имеет полиномиальное решение для произвольной постоянной . Использование общего рационального решения
для произвольного .
Рекомендации
↑
Абрамов, Сергей А. (1989). «Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами». Вычислительная математика и математическая физика СССР . 29 (6): 7–12. DOI : 10.1016 / s0041-5553 (89) 80002-3 . ISSN 0041-5553 .
↑ Ман, Ю-Квонг; Райт, Фрэнсис Дж. (1994). Быстрое вычисление полиномиальной дисперсии и его применение к неопределенному суммированию . ISSAC '94 Труды Международного симпозиума по символьным и алгебраическим вычислениям . С. 175–180. DOI : 10.1145 / 190347.190413 . ISBN 978-0897916387 .