В математике алгоритм Госпера , предложенный Биллом Госпером , представляет собой процедуру нахождения сумм гипергеометрических членов , которые сами являются гипергеометрическими членами. То есть: предположим, что есть 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 .
алгоритм / тождества биномиальных коэффициентов / закрытая форма / символьные вычисления / линейные рекурренты