Algorytm Gospera

W matematyce algorytm Gospera , dzięki Billowi Gosperowi , jest procedurą znajdowania sum wyrazów hipergeometrycznych , które same są wyrazami hipergeometrycznymi. To znaczy: załóżmy, że mamy a (1) + ... + a ( n ) = S ( n ) − S (0), gdzie S ( n ) jest wyrazem hipergeometrycznym (tj. S ( n + 1)/ S ( n ) jest a funkcja wymierna n ) ; wtedy z konieczności a ( n ) samo w sobie jest terminem hipergeometrycznym, a biorąc pod uwagę wzór na a ( n ), algorytm Gospera znajduje to dla S ( n ).

Zarys algorytmu

Krok 1: Znajdź wielomian p taki, że zapisując b ( n ) = a ( n )/ p ( n ), stosunek b ( n )/ b ( n − 1) ma postać q ( n )/ r ( n ) gdzie q i r są wielomianami i żadne q ( n ) nie ma nietrywialnego czynnika z r ( n + j ) dla j = 0, 1, 2, ... . (Jest to zawsze możliwe, niezależnie od tego, czy szereg można zsumować w formie zamkniętej).

Krok 2: Znajdź wielomian ƒ taki, że S ( n ) = q ( n + 1)/ p ( n ) ƒ ( n ) a ( n ). Jeśli szereg jest sumowalny w postaci zamkniętej, to oczywiście istnieje funkcja wymierna ƒ o tej własności; w rzeczywistości zawsze musi to być wielomian i można znaleźć górną granicę jego stopnia. Określenie ƒ (lub stwierdzenie, że nie ma takiego ƒ ) jest więc kwestią rozwiązania układu równań liniowych.

Związek z parami Wilfa – Zeilbergera

Algorytm Gospera można wykorzystać do odkrycia par Wilfa – Zeilbergera tam, gdzie one istnieją. Załóżmy, że F ( n + 1, k ) − F ( n , k ) = G ( n , k + 1) − G ( n , k ) gdzie F jest znane, ale G nie. Następnie podaj a ( k ) := F ( n + 1, k ) − F ( n , k ) do algorytmu Gospera. (Potraktuj to jako funkcję k, której współczynniki są funkcjami n, a nie liczbami; wszystko w algorytmie działa w tym ustawieniu.) Jeśli pomyślnie znajdzie S ( k ) z S ( k ) - S ( k - 1) = a ( k ), to koniec: to jest wymagane G . Jeśli nie, to nie ma takiego G.

Sumowanie określone kontra nieokreślone

Algorytm Gospera znajduje (tam, gdzie to możliwe) hipergeometryczną formę zamkniętą dla nieokreślonej sumy wyrazów hipergeometrycznych. Może się zdarzyć, że nie ma takiej postaci zamkniętej, ale suma po wszystkich n lub jakiś określony zbiór wartości n ma postać domkniętą. To pytanie ma sens tylko wtedy, gdy współczynniki same są funkcjami jakiejś innej zmiennej. Załóżmy więc, że a(n, k) jest wyrazem hipergeometrycznym zarówno w n, jak i k : to znaczy a ( n , k )/ a ( n − 1, k ) i a ( n , k )/ a ( n , k − 1) są funkcjami wymiernymi n i k . Wtedy algorytm Zeilbergera i algorytm Petkovška mogą być użyte do znalezienia form zamkniętych dla sumy po k z a ( n , k ).

Historia

Bill Gosper odkrył ten algorytm w latach 70-tych, pracując nad systemem algebry komputerowej Macsyma w SAIL i MIT .

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Gosper%27s_algorithm&oldid=1115169928 ”