Алгоритм Госпера

В математике , алгоритм Госпера , предложенный Биллом Госпером , представляет собой процедуру нахождения сумм гипергеометрических термов которые сами являются гипергеометрическими термовами. То есть: предположим, что имеется 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 ). Если ряд суммируем в замкнутой форме, то, очевидно, существует рациональная функция ƒ с этим свойством; на самом деле он всегда должен быть полиномом, и можно найти верхнюю границу его степени. Определение ƒ не существует (или обнаружение того, что такого ƒ ) тогда является вопросом решения системы линейных уравнений. ^{[ 1 ]}

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

Алгоритм Госпера можно использовать для обнаружения пар Уилфа – Цейлбергера там, где они существуют. Предположим, что 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) = a ( k и есть искомый 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 . Тогда алгоритм Зейлбергера и алгоритм Петковшека можно использовать для нахождения замкнутых форм суммы по k числа a ( n , k ).

История

Билл Госпер открыл этот алгоритм в 1970-х годах, когда работал над системой компьютерной алгебры Macsyma в SAIL и MIT .

Примечания

^ Петковшек, Марко ; Уилф, Герберт ; Зейлбергер, Дорон (1996). А = Б. ООО "АК Питерс" ISBN 1-56881-063-6 . Архивировано из оригинала 11 июля 2019 г. Проверено 10 января 2020 г. [1] [2] [3]

Ссылки

Госпер-младший, Ральф Уильям «Билл» (январь 1978 г.) [1977-09-26]. «Процедура принятия решения для неопределенного гипергеометрического суммирования» (PDF) . Труды Национальной академии наук Соединенных Штатов Америки . Математика. 75 (1). Xerox, Исследовательский центр Пало-Альто, Пало-Альто, Калифорния, США: 40–42. Бибкод : 1978ПНАС...75...40Г . дои : 10.1073/pnas.75.1.40 . ПМК 411178 . ПМИД 16592483 . Архивировано (PDF) из оригинала 12 апреля 2019 г. Проверено 10 января 2020 г. алгоритм / тождества биномиальных коэффициентов / замкнутая форма / символьные вычисления / линейные рекурренты

[1] Петковшек, Марко ; Уилф, Герберт ; Зейлбергер, Дорон (1996). А = Б. ООО "АК Питерс" ISBN 1-56881-063-6 . Архивировано из оригинала 11 июля 2019 г. Проверено 10 января 2020 г. [1] [2] [3]

[ 1 ]