В математике , алгоритм Госпера в , из - за Билл Госпер , является процедурой нахождения суммы гипергеометрических терминов , которые сами гипергеометрическими термины. То есть: предположим, что имеется a (1) + ... + a ( n ) = S ( n ) - S (0), где S ( n ) - гипергеометрический терм (т. Е. S ( n + 1) / S ( n ) - рациональная функция от n ); тогда обязательно a ( n) сам по себе является гипергеометрическим термином, и, учитывая формулу для a ( n ), алгоритм Госпера находит это для S ( n ).
Схема алгоритма
Шаг 1. Найдите многочлен p такой, что, записав b ( n ) = a ( n ) / p ( n ), отношение b ( n ) / b ( n - 1) будет иметь вид q ( n ) / r ( n ), где q и r - многочлены, и никакой q ( n ) не имеет нетривиального множителя с r ( n + j ) для j = 0, 1, 2, .... (Это всегда возможно, независимо от того, суммируем ли ряд в замкнутой форме.)
Шаг 2: Найдите многочлен ƒ такой, что S ( n ) = q ( n + 1) / p ( n ) ƒ ( n ) a ( n ). Если ряд суммируется в замкнутом виде , то очевидно , рациональная функция ƒ с существует это свойство; фактически он всегда должен быть многочленом, и можно определить верхнюю границу его степени. Определение ƒ (или не находя , что нет такого ƒ ) тогда вопрос о решении системы линейных уравнений.
Связь с парами Вильфа-Цайльбергера
Алгоритм Госпера может быть использован для обнаружения пар Уилфа – Цайльбергера там , где они существуют. Предположим, что F ( n + 1, k ) - F ( n , k ) = G ( n , k + 1) - G ( n , k ), где F известно, а G - нет. Затем подайте a ( k ): = F ( n + 1, k ) - F ( n , k ) в алгоритм Госпера. (Рассматривайте это как функцию от k, коэффициенты которой являются функциями от n, а не чисел; все в алгоритме работает в этой настройке.) Если он успешно находит S ( k ) с помощью S ( k ) - S ( k - 1) = ( к ), то мы сделали: это требуется G . Если нет, то нет такого G .
Определенное против неопределенного суммирования
Алгоритм Госпера находит (где возможно) гипергеометрическую замкнутую форму для неопределенной суммы гипергеометрических членов. Может случиться так, что такой закрытой формы не существует, но сумма по всем n или некоторому конкретному набору значений n имеет закрытый вид. Этот вопрос имеет смысл только тогда, когда коэффициенты сами являются функциями некоторой другой переменной. Итак, предположим, что a (n, k) - гипергеометрический член как в n, так и в k : то есть a ( n , k ) / a ( n - 1, k ) и a ( n , k ) / a ( n , k - 1) являются рациональными функциями от n и k . Тогда алгоритм Zeilberger в и алгоритм Petkovšek в может быть использован , чтобы найти замкнутые формы для суммы по к о в ( п , к ).
История
Билл Госпер открыл этот алгоритм в 1970-х, когда работал над системой компьютерной алгебры Macsyma в SAIL и MIT .
дальнейшее чтение
- Петковшек, Марко ; Уилф, Герберт ; Зейлбергер, Дорон (1996). А = В . Домашняя страница книги "A = B" . AK Peters Ltd. ISBN 1-56881-063-6. Архивировано 11 июля 2019 года . Проверено 10 января 2020 . [1] [2] [3]
- Госпер-младший, Ральф Уильям «Билл» (январь 1978 г.) [1977-09-26]. «Процедура принятия решения для неопределенного гипергеометрического суммирования» (PDF) . Труды Национальной академии наук Соединенных Штатов Америки . Математика. Xerox, Исследовательский центр Пало-Альто, Пало-Альто, Калифорния, США. 75 (1): 40–42. Архивировано (PDF) из оригинала 12.04.2019 . Проверено 10 января 2020 .
алгоритм / тождества биномиальных коэффициентов / замкнутая форма / символьные вычисления / линейные повторения