Petkovšeks algoritmi - Petkovšeks algorithm - Wikipedia

Petkovšek algoritmi (shuningdek Giper) a kompyuter algebra asosini hisoblaydigan algoritm gipergeometrik atamalar uni kiritishning echimi polinom koeffitsientlari bilan chiziqli takrorlanish tenglamasi. Bunga teng ravishda, u birinchi darajali to'g'ri chiziqli omilni hisoblaydi farq operatorlari polinom koeffitsientlari bilan. Ushbu algoritm tomonidan ishlab chiqilgan Marko Petkovšek 1992 yil nomzodlik dissertatsiyasida.^[1] Algoritm barcha asosiy kompyuter algebra tizimlarida amalga oshiriladi.

Gosper-Petkovšek vakili

Ruxsat bering ${ textstyle mathbb {K}}$ bo'lishi a maydon ning xarakterli nol. Nolga teng bo'lmagan ketma-ketlik ${ textstyle y (n)}$ ketma-ket ikkita hadning nisbati bo'lsa, gipergeometrik deyiladi oqilona, ya'ni ${ textstyle y (n + 1) / y (n) in mathbb {K} (n)}$ . Petkovšek algoritmi asosiy tushuncha sifatida ushbu ratsional funktsiya o'ziga xos ko'rinishga ega, ya'ni Gosper-Petkovšek normal shakli. Ruxsat bering ${ textstyle r (n) in mathbb {K} [n]}$ nolga teng bo'lmagan ratsional funktsiya bo'lishi. Keyin monika mavjud polinomlar ${ textstyle a, b, c in mathbb {K} [n]}$ va ${ textstyle 0 neq z in mathbb {K}}$ shu kabi

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

va

${ textstyle gcd (a (n), b (n + k)) = 1}$ har qanday salbiy bo'lmagan butun son uchun ${ textstyle k in mathbb {N}}$ ,
${ textstyle gcd (a (n), c (n)) = 1}$ va
${ textstyle gcd (b (n), c (n + 1)) = 1}$ .

Ning bu vakili ${ textstyle r (n)}$ Gosper-Petkovšek normal shakli deb nomlanadi. Ushbu polinomlarni aniq hisoblash mumkin. Vakilning ushbu konstruktsiyasi uning muhim qismidir Gosper algoritmi.^[2] Petkovšek ushbu oddiy shaklni noyob qiladigan ushbu vakillikning 2. va 3. shartlarini qo'shdi.^[1]

Algoritm

Gosper-Petkovšek vakili yordamida asl takrorlanish tenglamasini polinom ketma-ketligi uchun takrorlanish tenglamasiga aylantirish mumkin. ${ textstyle c (n)}$ . Boshqa polinomlar ${ textstyle a (n), b (n)}$ birinchi koeffitsient polinomining monik omillari sifatida qabul qilinishi mumkin ${ textstyle p_ {0} (n)}$ resp. oxirgi koeffitsient polinom o'zgargan ${ textstyle p_ {r} (n-r + 1)}$ . Keyin ${ textstyle z}$ ma'lum bir narsani bajarishi kerak algebraik tenglama. Mumkin bo'lgan barcha uchta imkoniyatlardan foydalanish ${ textstyle (a (n), b (n), z)}$ va mos keladiganlarni hisoblash polinom eritmasi o'zgartirilgan takrorlanish tenglamasining ${ textstyle c (n)}$ agar mavjud bo'lsa, gipergeometrik eritma beradi.^[1]^[3]^[4]

Quyidagi psevdokodda polinomning darajasi ${ textstyle p (n) in mathbb {K} [n]}$ bilan belgilanadi ${ textstyle deg (p (n))}$ va koeffitsienti ${ textstyle n ^ {d}}$ bilan belgilanadi ${ textstyle { text {coeff}} (p (n), n ^ {d})}$ .

algoritm petkovsek bu    kiritish: Chiziqli takrorlanish tenglamasi  ${ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) , y (n + k) = 0, p_ {k} in mathbb {K} [n], p_ { 0}, p_ {r} neq 0}$ .    chiqish: Gipergeometrik eritma  ${ textstyle y}$  agar gipergeometrik eritmalar bo'lsa. har biriga monik bo'luvchi  ${ textstyle a (n)}$  ning  ${ textstyle p_ {0} (n)}$  qil        har biriga monik bo'luvchi  ${ textstyle b (n)}$  ning  ${ textstyle p_ {r} (n-r + 1)}$  qil            har biriga  ${ textstyle k = 0, dots, r}$  qil                 ${ 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, nuqta, r} deg ({ tilde {p}} _ {k} (n))}$         har biriga ildiz  ${ textstyle z}$  ning  ${ textstyle sum _ {k = 0} ^ {r} { text {coeff}} ({ tilde {p}} _ {k} (n), n ^ {d}) z ^ {k}}$  qil            Nolga teng bo'lmagan polinom echimini toping  ${ textstyle c (n)}$  ning  ${ textstyle sum _ {k = 0} ^ {r} z ^ {k} , { tilde {p}} _ {k} (n) , c (n + k) = 0}$             agar bunday nolga teng bo'lmagan echim  ${ textstyle c (n)}$  mavjud keyin                 ${ textstyle r (n) = z , a (n) / b (n) , c (n + 1) / c (n)}$                 qaytish nolga teng bo'lmagan echim  ${ textstyle y (n)}$  ning  ${ textstyle y (n + 1) = r (n) , y (n)}$

Agar echim topilsa bitmasa, barcha gipergeometrik echimlarni birlashtirib, takrorlanish tenglamasining umumiy gipergeometrik eritmasini, ya'ni gipergeometrik ketma-ketliklarning chiziqli oralig'ida takrorlanadigan tenglamaning yadrosi uchun hosil qiluvchi to'plamni olish mumkin.^[1]

Petkovšek bir hil bo'lmagan muammoni qanday hal qilish mumkinligini ham ko'rsatib berdi. U takrorlanish tenglamasining o'ng tomoni gipergeometrik ketma-ketliklar yig'indisi bo'lgan ishni ko'rib chiqdi. O'ng tomonning ma'lum gipergeometrik ketma-ketliklarini birlashtirgandan so'ng, ushbu guruhlarning har biri uchun ratsional echim uchun ma'lum bir takrorlanish tenglamasi echiladi. Ushbu ratsional echimlarni bir hil bo'lmagan tenglamaning ma'lum bir echimini olish uchun birlashtirish mumkin. Bir hil muammoning umumiy echimi bilan birgalikda bu bir hil bo'lmagan masalaning umumiy echimini beradi.^[1]

Misollar

Imzolangan almashtirish matritsalari

Soni imzolangan almashtirish matritsalari hajmi ${ textstyle n times n}$ ketma-ketligi bilan tavsiflanishi mumkin ${ textstyle y (n)}$ takrorlanish tenglamasi bilan belgilanadi

{ displaystyle 4 (n + 1) ^ {2} , y (n) +2 , y (n + 1) + (- 1) , y (n + 2) = 0}

ustida

{ textstyle mathbb {Q}}

. Qabul qilish

{ textstyle a (n) = n + 1, b (n) = 1}

ning monik bo'linuvchilari sifatida

{ textstyle p_ {0} (n) = 4 (n + 1) ^ {2}, p_ {2} (n) = - 1}

mos ravishda, bitta oladi

{ textstyle z = pm 2}

. Uchun

{ textstyle z = 2}

Petkovšek algoritmida echilgan tegishli takrorlanish tenglamasi

{ displaystyle 4 (n + 1) ^ {2} , c (n) +4 (n + 1) , c (n + 1) -4 (n + 1) (n + 2) , c () n + 2) = 0.}

Ushbu takrorlanish tenglamasi polinom echimiga ega

{ textstyle c (n) = c_ {0}}

o'zboshimchalik uchun

{ textstyle c_ {0} in mathbb {Q}}

. Shuning uchun

{ textstyle r (n) = 2 (n + 1)}

va

{ textstyle y (n) = 2 ^ {n} , n!}

gipergeometrik eritma hisoblanadi. Aslida bu (doimiygacha) yagona gipergeometrik eritma va imzolangan almashtirish matritsalari sonini tavsiflaydi.^[5]

Ning mantiqsizligi ${ displaystyle zeta (3)}$

Jami hisobga olingan holda

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

kelgan Aperi ning mantiqsizligini isboti ${ displaystyle zeta (3)}$ , Zaylberger algoritmi chiziqli takrorlanishni hisoblab chiqadi

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

Ushbu takrorlanishni hisobga olgan holda, algoritm biron bir gipergeometrik echimni qaytarmaydi, bu buni tasdiqlaydi ${ displaystyle a (n)}$ ga soddalashtirmaydi gipergeometrik atama.^[3]

Adabiyotlar

^ ^a ^b ^v ^d ^e Petkovšek, Marko (1992). "Polinom koeffitsientlari bilan chiziqli takrorlanishning gipergeometrik echimlari". Ramziy hisoblash jurnali. 14 (2–3): 243–264. doi:10.1016/0747-7171(92)90038-6. ISSN 0747-7171.
^ Gosper, R. Uilyam (1978). "Cheklanmagan gipergeometrik yig'indiga qaror qilish tartibi" (PDF). Proc. Natl. Akad. Ilmiy ish. AQSH. 75 (1): 40–42. doi:10.1073 / pnas.75.1.40. PMC 411178. PMID 16592483.
^ ^a ^b Petkovšek, Marko; Uilf, Gerbert S.; Zayberberger, Doron (1996). A = B. A K Peters. ISBN 1568810636. OCLC 33898705.
^ Kauers, Manuel; Paule, Piter (2011). Beton tetraedr: ramziy yig'indilar, takrorlanish tenglamalari, hosil qiluvchi funktsiyalar, asimptotik taxminlar. Wien: Springer. ISBN 9783709104453. OCLC 701369215.
^ "A000165 - OEIS". oeis.org. Olingan 2018-07-02.

[:0-1] v ^d ^e Petkovšek, Marko (1992). "Polinom koeffitsientlari bilan chiziqli takrorlanishning gipergeometrik echimlari". Ramziy hisoblash jurnali. 14 (2–3): 243–264. doi:10.1016/0747-7171(92)90038-6. ISSN 0747-7171.

[2] Gosper, R. Uilyam (1978). "Cheklanmagan gipergeometrik yig'indiga qaror qilish tartibi" (PDF). Proc. Natl. Akad. Ilmiy ish. AQSH. 75 (1): 40–42. doi:10.1073 / pnas.75.1.40. PMC 411178. PMID 16592483.

[:1-3] Petkovšek, Marko; Uilf, Gerbert S.; Zayberberger, Doron (1996). A = B. A K Peters. ISBN 1568810636. OCLC 33898705.

[4] Kauers, Manuel; Paule, Piter (2011). Beton tetraedr: ramziy yig'indilar, takrorlanish tenglamalari, hosil qiluvchi funktsiyalar, asimptotik taxminlar. Wien: Springer. ISBN 9783709104453. OCLC 701369215.

[5] "A000165 - OEIS". oeis.org. Olingan 2018-07-02.

[1]

[2]

[3]

[4]

[5]