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

Gospers algorithm - Wikipedia

В математика, Алгоритм госпера, из-за Билл Госпер, это процедура нахождения сумм гипергеометрические термины которые сами по себе являются гипергеометрическими терминами. То есть: предположим, есть а(1) + ... + а(п) = S(п) − S(0), где S(п) является гипергеометрическим членом (т. е. S(п + 1)/S(п) это рациональная функция из п); тогда обязательно а(п) сам по себе является гипергеометрическим членом, и учитывая формулу для а(п) Алгоритм Госпера находит, что для S(п).

Схема алгоритма

Шаг 1. Найдите многочлен п так что, писать б(п) = а(п)/п(п), Соотношение б(п)/б(п - 1) имеет вид q(п)/р(п) куда q и р являются многочленами и нет q(п) имеет нетривиальный множитель с р(п + j) за j = 0, 1, 2, .... (Это всегда возможно, независимо от того, суммируем ли ряд в замкнутой форме.)

Шаг 2. Найдите многочлен ƒ такой, что S(п) = q(п + 1)/п(п) ƒ(п) а(п). Если ряд суммируем в замкнутой форме, то, очевидно, рациональная функция ƒ с этим свойством существует; на самом деле он всегда должен быть многочленом, и можно определить верхнюю границу его степени. Определение ƒ (или обнаружив, что такого ƒ) тогда является вопросом решения системы линейных уравнений.

Связь с парами Вильфа-Цайльбергера

Алгоритм Госпера может быть использован для обнаружения Пары Вильфа-Цайльбергера, где они существуют. Предположим, что F(п + 1, k) − F(п, k) = грамм(п, k + 1) − грамм(п, k) куда F известно, но грамм не является. Затем накормите а(k) := F(п + 1, k) − F(п, k) в алгоритм Госпера. (Рассматривайте это как функцию от k, коэффициенты которой являются функциями от n, а не чисел; все в алгоритме работает в этой настройке.) Если он успешно находит S(k) с S(k) − S(k − 1) = а(k), то готово: это требуемый грамм. Если нет, то такого нет грамм.

Определенное и неопределенное суммирование

Алгоритм Госпера находит (где возможно) гипергеометрическую замкнутую форму для неопределенный сумма гипергеометрических членов. Может случиться так, что такой закрытой формы нет, но сумма больше все п, или некоторый конкретный набор значений n, имеет замкнутую форму. Этот вопрос имеет смысл только тогда, когда коэффициенты сами являются функциями какой-то другой переменной. Итак, предположим, что a (n, k) - гипергеометрический член в обоих п и k: то есть, а(п, k)/а(п − 1,k) и а(п, k)/а(п, k - 1) являются рациональными функциями п и k. потом Алгоритм Зейльбергера и Алгоритм Петковшека можно использовать для поиска закрытых форм на сумму более k из а(п, k).

История

Билл Госпер открыл этот алгоритм в 1970-х, работая над Macsyma система компьютерной алгебры в ПЛЫТЬ и Массачусетский технологический институт.

дальнейшее чтение

  • Петковшек, Марко; Уилф, Герберт; Зейлбергер, Дорон (1996). А = В. Домашняя страница книги "A = B". A K Peters Ltd. ISBN 1-56881-063-6. В архиве из оригинала на 2019-07-11. Получено 2020-01-10. [1] [2] [3]
  • Госпер младший, Ральф Уильям «Билл» (Январь 1978 г.) [1977-09-26]. «Процедура принятия решения для неопределенного гипергеометрического суммирования» (PDF). Труды Национальной академии наук Соединенных Штатов Америки. Математика. Xerox, Исследовательский центр Пало-Альто, Пало-Альто, Калифорния, США. 75 (1): 40–42. В архиве (PDF) из оригинала на 2019-04-12. Получено 2020-01-10. алгоритм / тождества биномиальных коэффициентов / замкнутая форма / символьные вычисления / линейные повторения