Petkovšeks algoritmi - Petkovšeks algorithm

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 bo'lishi a maydon ning xarakterli nol. Nolga teng bo'lmagan ketma-ketlik ketma-ket ikkita hadning nisbati bo'lsa, gipergeometrik deyiladi oqilona, ya'ni . Petkovšek algoritmi asosiy tushuncha sifatida ushbu ratsional funktsiya o'ziga xos ko'rinishga ega, ya'ni Gosper-Petkovšek normal shakli. Ruxsat bering nolga teng bo'lmagan ratsional funktsiya bo'lishi. Keyin monika mavjud polinomlar va shu kabi

va

  1. har qanday salbiy bo'lmagan butun son uchun ,
  2. va
  3. .

Ning bu vakili 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. . Boshqa polinomlar birinchi koeffitsient polinomining monik omillari sifatida qabul qilinishi mumkin resp. oxirgi koeffitsient polinom o'zgargan . Keyin ma'lum bir narsani bajarishi kerak algebraik tenglama. Mumkin bo'lgan barcha uchta imkoniyatlardan foydalanish va mos keladiganlarni hisoblash polinom eritmasi o'zgartirilgan takrorlanish tenglamasining agar mavjud bo'lsa, gipergeometrik eritma beradi.[1][3][4]

Quyidagi psevdokodda polinomning darajasi bilan belgilanadi va koeffitsienti bilan belgilanadi .

algoritm petkovsek bu    kiritish: Chiziqli takrorlanish tenglamasi .    chiqish: Gipergeometrik eritma  agar gipergeometrik eritmalar bo'lsa. har biriga monik bo'luvchi  ning  qil        har biriga monik bo'luvchi  ning  qil            har biriga  qil                                har biriga ildiz  ning  qil            Nolga teng bo'lmagan polinom echimini toping  ning             agar bunday nolga teng bo'lmagan echim  mavjud keyin                                qaytish nolga teng bo'lmagan echim  ning 

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 ketma-ketligi bilan tavsiflanishi mumkin takrorlanish tenglamasi bilan belgilanadi

ustida . Qabul qilish ning monik bo'linuvchilari sifatida mos ravishda, bitta oladi . Uchun Petkovšek algoritmida echilgan tegishli takrorlanish tenglamasi
Ushbu takrorlanish tenglamasi polinom echimiga ega o'zboshimchalik uchun . Shuning uchun va gipergeometrik eritma hisoblanadi. Aslida bu (doimiygacha) yagona gipergeometrik eritma va imzolangan almashtirish matritsalari sonini tavsiflaydi.[5]

Ning mantiqsizligi

Jami hisobga olingan holda

kelgan Aperi ning mantiqsizligini isboti , Zaylberger algoritmi chiziqli takrorlanishni hisoblab chiqadi

Ushbu takrorlanishni hisobga olgan holda, algoritm biron bir gipergeometrik echimni qaytarmaydi, bu buni tasdiqlaydi ga soddalashtirmaydi gipergeometrik atama.[3]

Adabiyotlar

  1. ^ 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.
  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.
  3. ^ a b 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.