Алгоритм Петковшека

Алгоритм Петковшека (также Hyper ) — это алгоритм компьютерной алгебры , который вычисляет базис решения гипергеометрических членов входного линейного рекуррентного уравнения с полиномиальными коэффициентами . Эквивалентно, он вычисляет правый фактор первого порядка линейных разностных операторов с полиномиальными коэффициентами. Этот алгоритм был разработан Марко Петковшеком в его докторской диссертации 1992 года. ^{[ 1 ]} Алгоритм реализован во всех основных системах компьютерной алгебры.

Представительство Госпера-Петковшека

Позволять ${\textstyle \mathbb {K} }$ — поле характеристики нулевой . Ненулевая последовательность ${\textstyle y(n)}$ называется гипергеометрическим, если отношение двух последовательных членов рационально , т.е. ${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$ . Алгоритм Петковшека использует в качестве ключевой концепции, что эта рациональная функция имеет определенное представление, а именно нормальную форму Госпера-Петковшека . Позволять ${\textstyle r(n)\in \mathbb {K} [n]}$ быть ненулевой рациональной функцией. Тогда существуют монические многочлены ${\textstyle a,b,c\in \mathbb {K} [n]}$ и ${\textstyle 0\neq z\in \mathbb {K} }$ такой, что

$r(n)=z{\frac {a(n)}{b(n)}}{\frac {c(n+1)}{c(n)}}$

и

${\textstyle \gcd(a(n),b(n+k))=1}$ для каждого неотрицательного целого числа ${\textstyle k\in \mathbb {N} }$ ,
${\textstyle \gcd(a(n),c(n))=1}$ и
${\textstyle \gcd(b(n),c(n+1))=1}$ .

Это представление ${\textstyle r(n)}$ называется нормальной формой Госпера-Петковшека. Эти полиномы можно вычислить явно. Эта конструкция представления является существенной частью алгоритма Госпера . ^{[ 2 ]} Петковшек добавил условия 2 и 3 этого представления, что делает эту нормальную форму уникальной. ^{[ 1 ]}

Алгоритм

Используя представление Госпера-Петковшека, можно преобразовать исходное рекуррентное уравнение в рекуррентное уравнение для полиномиальной последовательности. ${\textstyle c(n)}$ . Остальные полиномы ${\textstyle a(n),b(n)}$ можно принять в качестве монических множителей первого коэффициента многочлена ${\textstyle p_{0}(n)}$ соотв. последний полином коэффициента сдвинут ${\textstyle p_{r}(n-r+1)}$ . Затем ${\textstyle z}$ должно удовлетворять определенному алгебраическому уравнению . Взяв все возможные конечное число троек ${\textstyle (a(n),b(n),z)}$ и вычисление соответствующего полиномиального решения преобразованного рекуррентного уравнения ${\textstyle c(n)}$ дает гипергеометрическое решение, если оно существует. ^{[ 1 ]}^{[ 3 ]}^{[ 4 ]}

В следующем псевдокоде степень многочлена ${\textstyle p(n)\in \mathbb {K} [n]}$ обозначается ${\textstyle \deg(p(n))}$ и коэффициент ${\textstyle n^{d}}$ обозначается ${\textstyle {\text{coeff}}(p(n),n^{d})}$ .

algorithm petkovsek is
    input: Linear recurrence equation  ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=0,p_{k}\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$ .
    output: A hypergeometric solution  ${\textstyle y}$  if there are any hypergeometric solutions.

    for each monic divisor  ${\textstyle a(n)}$  of  ${\textstyle p_{0}(n)}$  do
        for each monic divisor  ${\textstyle b(n)}$  of  ${\textstyle p_{r}(n-r+1)}$  do
            for each  ${\textstyle k=0,\dots ,r}$  do
                 ${\textstyle {\tilde {p}}_{k}(n)=p_{k}(n)\prod _{j=0}^{k-1}a(n+j)\prod _{i=k}^{r-1}b(n+i)}$ 
         ${\textstyle d=\max _{k=0,\dots ,r}\deg({\tilde {p}}_{k}(n))}$ 
        for each root  ${\textstyle z}$  of  ${\textstyle \sum _{k=0}^{r}{\text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}}$  do
            Find non-zero polynomial solution  ${\textstyle c(n)}$  of  ${\textstyle \sum _{k=0}^{r}z^{k}\,{\tilde {p}}_{k}(n)\,c(n+k)=0}$ 
            if such a non-zero solution  ${\textstyle c(n)}$  exists then
                 ${\textstyle r(n)=z\,a(n)/b(n)\,c(n+1)/c(n)}$ 
                return a non-zero solution  ${\textstyle y(n)}$  of  ${\textstyle y(n+1)=r(n)\,y(n)}$

Если одно не заканчивается, если решение найдено, можно объединить все гипергеометрические решения, чтобы получить общее гипергеометрическое решение рекуррентного уравнения, т.е. порождающий набор для ядра рекуррентного уравнения в линейной оболочке гипергеометрических последовательностей. ^{[ 1 ]}

Петковшек также показал, как можно решить неоднородную задачу. Он рассмотрел случай, когда правая часть рекуррентного уравнения представляет собой сумму гипергеометрических последовательностей. После группировки определенных гипергеометрических последовательностей правой части для каждой из этих групп решается определенное рекуррентное уравнение для рационального решения. Эти рациональные решения можно объединить, чтобы получить частное решение неоднородного уравнения. Вместе с общим решением однородной задачи это дает общее решение неоднородной задачи. ^{[ 1 ]}

Примеры

Знаковые матрицы перестановок

Количество матриц перестановок со знаком размера ${\textstyle n\times n}$ можно описать последовательностью ${\textstyle y(n)}$ которое определяется рекуррентным уравнением $4(n+1)^{2}\,y(n)+2\,y(n+1)+(-1)\,y(n+2)=0$ над ${\textstyle \mathbb {Q} }$ . принимая ${\textstyle a(n)=n+1,b(n)=1}$ как монические делители ${\textstyle p_{0}(n)=4(n+1)^{2},p_{2}(n)=-1}$ соответственно, получается ${\textstyle z=\pm 2}$ . Для ${\textstyle z=2}$ соответствующее рекуррентное уравнение, которое решается в алгоритме Петковшека, имеет вид $4(n+1)^{2}\,c(n)+4(n+1)\,c(n+1)-4(n+1)(n+2)\,c(n+2)=0.$ Это рекуррентное уравнение имеет полиномиальное решение ${\textstyle c(n)=c_{0}}$ для произвольного ${\textstyle c_{0}\in \mathbb {Q} }$ . Следовательно ${\textstyle r(n)=2(n+1)}$ и ${\textstyle y(n)=2^{n}\,n!}$ является гипергеометрическим решением. Фактически это (с точностью до константы) единственное гипергеометрическое решение, описывающее количество матриц перестановок со знаком. ^{[ 5 ]}

Иррациональность $\zeta (3)$

Учитывая сумму

a(n)=\sum _{k=0}^{n}{{\binom {n}{k}}^{2}{\binom {n+k}{k}}^{2}},

исходя из доказательства Апери иррациональности $\zeta (3)$ , алгоритм Зейлбергера вычисляет линейную рекуррентность

(n+2)^{3}\,a(n+2)-(17n^{2}+51n+39)(2n+3)\,a(n+1)+(n+1)^{3}\,a(n)=0.

Учитывая такое повторение, алгоритм не возвращает ни одного гипергеометрического решения, что доказывает, что $a(n)$ не упрощается до гипергеометрического термина . ^{[ 3 ]}

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Петковшек, Марко (1992). «Гипергеометрические решения линейных рекуррентностей с полиномиальными коэффициентами» . Журнал символических вычислений . 14 (2–3): 243–264. дои : 10.1016/0747-7171(92)90038-6 . ISSN 0747-7171 .
^ Госпер, Р. Уильям (1978). «Процедура решения неопределенного гипергеометрического суммирования» . Учеб. Натл. акад. наук. США . 75 (1): 40–42. дои : 10.1073/pnas.75.1.40 . ПМК 411178 . ПМИД 16592483 . S2CID 26361864 .
^ Jump up to: ^а ^б Петковшек, Марко; Уилф, Герберт С.; Зейлбергер, Дорон (1996). А=Б . АК Петерс. ISBN 1568810636 . OCLC 33898705 .
^ Кауэрс, Мануэль; Пол, Питер (2011). Конкретный тетраэдр: символьные суммы, рекуррентные уравнения, производящие функции, асимптотические оценки . Вена: Спрингер. ISBN 9783709104453 . OCLC 701369215 .
^ «А000165-ОЭИС» . oeis.org . Проверено 2 июля 2018 г.

[:0-1] Jump up to: ^а ^б ^с ^д ^и Петковшек, Марко (1992). «Гипергеометрические решения линейных рекуррентностей с полиномиальными коэффициентами» . Журнал символических вычислений . 14 (2–3): 243–264. дои : 10.1016/0747-7171(92)90038-6 . ISSN 0747-7171 .

[2] Госпер, Р. Уильям (1978). «Процедура решения неопределенного гипергеометрического суммирования» . Учеб. Натл. акад. наук. США . 75 (1): 40–42. дои : 10.1073/pnas.75.1.40 . ПМК 411178 . ПМИД 16592483 . S2CID 26361864 .

[:1-3] Jump up to: ^а ^б Петковшек, Марко; Уилф, Герберт С.; Зейлбергер, Дорон (1996). А=Б . АК Петерс. ISBN 1568810636 . OCLC 33898705 .

[4] Кауэрс, Мануэль; Пол, Питер (2011). Конкретный тетраэдр: символьные суммы, рекуррентные уравнения, производящие функции, асимптотические оценки . Вена: Спрингер. ISBN 9783709104453 . OCLC 701369215 .

[5] «А000165-ОЭИС» . oeis.org . Проверено 2 июля 2018 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]