WikiDer > Алгоритм Петковшекса - Википедия

Petkovšeks algorithm - Wikipedia

Алгоритм Петковшека (также Гипер) это компьютерная алгебра алгоритм, который вычисляет основу гипергеометрические термины решение его ввода линейное рекуррентное уравнение с полиномиальными коэффициентами. Эквивалентно, он вычисляет правый множитель первого порядка линейного операторы разницы с полиномиальными коэффициентами. Этот алгоритм был разработан Марко Петковшек в своей кандидатской диссертации 1992 г.[1] Алгоритм реализован во всех основных системах компьютерной алгебры.

Представительство Госпер-Петковшек

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

и

  1. для каждого неотрицательного целого числа ,
  2. и
  3. .

Это представление называется нормальной формой Госпера-Петковшека. Эти полиномы можно вычислить явно. Эта конструкция представления является важной частью Алгоритм госпера.[2] Петковшек добавил условия 2 и 3 этого представления, что делает эту нормальную форму уникальной.[1]

Алгоритм

Используя представление Госпера-Петковшека, можно преобразовать исходное рекуррентное уравнение в рекуррентное уравнение для полиномиальной последовательности . Остальные многочлены можно взять в качестве монических множителей первого полинома коэффициентов соотв. последний коэффициент полинома сдвинут . потом должен выполнить определенные алгебраическое уравнение. Взяв все возможное конечное число троек и вычисляя соответствующие полиномиальное решение преобразованного рекуррентного уравнения дает гипергеометрическое решение, если оно существует.[1][3][4]

В следующем псевдокоде степень многочлена обозначается и коэффициент обозначается .

алгоритм Петковсек является    Вход: Линейное рекуррентное уравнение .    выход: Гипергеометрическое решение  если есть гипергеометрические решения. для каждого монический делитель  из  делать        для каждого монический делитель  из  делать            для каждого  делать                                для каждого корень  из  делать            Найдите ненулевое полиномиальное решение  из             если такое ненулевое решение  существуют тогда                                возвращаться ненулевое решение  из 

Если одно не заканчивается, если решение найдено, можно объединить все гипергеометрические решения, чтобы получить общее гипергеометрическое решение рекуррентного уравнения, то есть порождающую совокупность для ядра рекуррентного уравнения в линейной оболочке гипергеометрических последовательностей.[1]

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

Примеры

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

Количество матрицы перестановок со знаком размера можно описать последовательностью которое определяется рекуррентным уравнением

над . Принимая как монические делители соответственно получается . За соответствующее рекуррентное уравнение, которое решается в алгоритме Петковшека, имеет вид
Это рекуррентное уравнение имеет полиномиальное решение для произвольного . Следовательно и является гипергеометрическим решением. Фактически это (с точностью до константы) единственное гипергеометрическое решение и описывает количество матриц перестановок со знаком.[5]

Иррациональность

Учитывая сумму

приходящий из Аперидоказательство иррациональности , Zeilbergerалгоритм вычисляет линейное повторение

Учитывая это повторение, алгоритм не возвращает никакого гипергеометрического решения, что доказывает, что не упрощается до гипергеометрический термин.[3]

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

  1. ^ а б c d е Петковшек, Марко (1992). «Гипергеометрические решения линейных рекуррент с полиномиальными коэффициентами». Журнал символических вычислений. 14 (2–3): 243–264. Дои:10.1016/0747-7171(92)90038-6. ISSN 0747-7171.
  2. ^ Госпер, Р. Уильям (1978). «Процедура принятия решения для неопределенного гипергеометрического суммирования» (PDF). Proc. Natl. Акад. Sci. Соединенные Штаты Америки. 75 (1): 40–42. Дои:10.1073 / пнас.75.1.40. ЧВК 411178. PMID 16592483.
  3. ^ а б Петковшек, Марко; Wilf, Herbert S .; Зейлбергер, Дорон (1996). А = В. А. К. Питерс. ISBN 1568810636. OCLC 33898705.
  4. ^ Кауэрс, Мануэль; Пол, Питер (2011). Конкретный тетраэдр: символические суммы, рекуррентные уравнения, производящие функции, асимптотические оценки.. Вена: Спрингер. ISBN 9783709104453. OCLC 701369215.
  5. ^ "A000165 - OEIS". oeis.org. Получено 2018-07-02.