Jenkins – Traub algoritmi - Jenkins–Traub algorithm - Wikipedia

The Jenkins - Polinom nollari uchun traub algoritmi tomonidan 1970 yilda nashr etilgan tezkor global yaqinlashuvchi iterativ usul Maykl A. Jenkins va Jozef F. Traub. Ular ikkita variantni berishdi, biri murakkab koeffitsientli umumiy polinomlar uchun, odatda "CPOLY" algoritmi deb nomlanadi va haqiqiy koeffitsientli polinomlarning maxsus ishi uchun yanada murakkab variant, odatda "RPOLY" algoritmi. Ikkinchisi "qora qutidagi polinomlarning ildiz topuvchilarida amaldagi standart" dir.[1]

Ushbu maqolada murakkab variant tasvirlangan. Polinom berilgan P,

murakkab koeffitsientlar bilan u ga yaqinlashuvlarni hisoblab chiqadi n nollar ning P(z), bir vaqtning o'zida kattalashib borayotgan kattalikdagi tartibda. Har bir ildiz hisoblangandan so'ng, uning chiziqli koeffitsienti polinomdan olib tashlanadi. Buni ishlatish deflyatsiya har bir ildizning faqat bir marta hisoblanishini va barcha ildizlarning topilishini kafolatlaydi.

Haqiqiy variant bir xil naqshga amal qiladi, lekin bir vaqtning o'zida ikkita ildizni, ikkita haqiqiy ildizni yoki juft juft murakkab ildizlarni hisoblab chiqadi. Murakkab arifmetikadan qochib, haqiqiy variant murakkab variantga qaraganda tezroq (4 marta) bo'lishi mumkin. Jenkins-Traub algoritmi ushbu turdagi usullar uchun nazariya va dasturiy ta'minot bo'yicha katta tadqiqotlarni rag'batlantirdi.

Umumiy nuqtai

Jenkins-Traub algoritmi a ning barcha ildizlarini hisoblab chiqadi polinom murakkab koeffitsientlar bilan. Algoritm polinomni juda katta yoki juda kichik ildizlarning paydo bo'lishini tekshirishdan boshlaydi. Agar kerak bo'lsa, koeffitsientlar o'zgaruvchining kattalashtirilishi bilan o'chiriladi. Algoritmda tegishli ildizlar birma-bir va odatda kattalashib borayotgan hajmda topilgan. Har bir ildiz topilgandan so'ng, polinom tegishli chiziqli omilni ajratish yo'li bilan o'chiriladi. Darhaqiqat, polinomni chiziqli omilga aylantirish va qolgan deflyatsiyalangan polinomni allaqachon ildiz topish protsedurasining natijasidir. Ildizlarni aniqlash protsedurasi uchta variantga to'g'ri keladi, ular teskari quvvatni takrorlash. Jenkins va Traub.[2]Ta'rifni Ralston va Rabinovits[3] p. 383. Algoritm ruhi jihatidan Traub tomonidan o'rganilgan ikki bosqichli algoritmga o'xshaydi.[4]

Ildizlarni aniqlash tartibi

Joriy polinomdan boshlang P(X) daraja n, ning eng kichik ildizi P (x) hisoblab chiqilgan. Shu maqsadda, deb nomlangan ketma-ketlik H polinomlar tuzilgan. Ushbu polinomlar barcha darajalardir n - 1 va koeffitsientiga yaqinlashishi kerak P(X) qolgan barcha ildizlarni o'z ichiga olgan. Ning ketma-ketligi H polinomlar ikki xil variantda uchraydi, bu g'ayritabiiy variant, bu oson nazariy tushunchalarga imkon beradi va koeffitsientlarni son jihatdan oqilona diapazonda ushlab turadigan polinomlar.

Ning qurilishi H polinomlar murakkab sonlar ketma-ketligiga bog'liq smenalar deb nomlangan. Ushbu siljishlarning o'zlari, hech bo'lmaganda uchinchi bosqichda, avvalgisiga bog'liq H polinomlar. The H polinomlar yashirin rekursiyaning echimi sifatida aniqlanadi

va

Ushbu yashirin tenglamani to'g'ridan-to'g'ri hal qilish

bu erda polinom bo'linishi aniq.

Algoritmik ravishda, masalan, Horner sxemasi yoki Ruffini qoidasi da koʻphadlarni baholash va bir vaqtning o'zida takliflarni oling. Olingan takliflar bilan p(X) va h(X) oraliq natijalar sifatida keyingi H polinom quyidagicha olinadi

Eng yuqori darajadagi koeffitsient olinganligi sababli P (X), ning etakchi koeffitsienti bu . Agar bu normalizatsiya qilingan bo'lsa H polinom

Birinchi bosqich: smenasiz ishlash jarayoni

Uchun o'rnatilgan . Odatda M = 5 gacha o'rtacha darajadagi polinomlar uchun tanlanadi n = 50. Ushbu bosqich faqat nazariy mulohazalardan zarur emas, balki amalda foydalidir. Bu ta'kidlaydi H eng kichik ildiz kofaktorini (chiziqli omilni) polinomlar.

Ikkinchi bosqich: belgilangan smenali jarayon

Ushbu bosqich uchun siljish polinomning eng kichik ildiziga yaqin nuqtalar sifatida aniqlanadi. U ichki ildiz radiusi bilan aylana ustida tasodifiy joylashgan bo'lib, u o'z navbatida tenglamaning ijobiy echimi sifatida baholanadi

Chap tomoni qavariq funktsiya bo'lib, monotonik ravishda noldan cheksizgacha ko'payganligi sababli, bu tenglamani echish oson, masalan Nyuton usuli.

Endi tanlang ushbu radius doirasida. Polinomlarning ketma-ketligi , , belgilangan siljish qiymati bilan hosil bo'ladi . Ushbu takrorlash paytida ildiz uchun joriy taxminiylik

kuzatiladi. Agar shartlar bo'lsa, ikkinchi bosqich muvaffaqiyatli yakunlanadi

va

bir vaqtning o'zida uchrashiladi. Agar bir necha marta takrorlangandan keyin muvaffaqiyat bo'lmasa, doiradagi boshqa tasodifiy nuqta sinab ko'riladi. Odatda o'rtacha darajadagi polinomlar uchun bir nechta 9 takrorlash qo'llaniladi, bir nechta muvaffaqiyatsizliklar uchun ikki baravar strategiya mavjud.

Uchinchi bosqich: o'zgaruvchan siljish jarayoni

The endi o'zgaruvchan siljishlar yordamida hosil qilinadi tomonidan ishlab chiqarilgan

ikkinchi bosqichning so'nggi ildiz bahosi bo'lish va

qayerda normallashtirilgan H polinom, ya'ni etakchi koeffitsientiga bo'linadi.

Agar uchinchi bosqichdagi qadam kattaligi nolga etarlicha tez tushmasa, ikkinchi bosqich boshqa tasodifiy nuqta yordamida qayta boshlanadi. Agar bu kichik miqdordagi qayta boshlashdan keyin muvaffaqiyatsiz bo'lsa, ikkinchi bosqichdagi qadamlar soni ikki baravar oshiriladi.

Yaqinlashish

Buni taqdim etish mumkin L etarlicha katta tanlangan, sλ har doim ning ildiziga yaqinlashadi P.

Algoritm ildizlarning har qanday taqsimoti uchun birlashadi, lekin ko'pburchakning barcha ildizlarini topa olmaydi. Bundan tashqari, konvergentsiya nisbatan bir oz tezroq kvadratik yaqinlik Nyuton-Raphson iteratsiyasida, ammo har qadamda kamida ikki baravar ko'p operatsiyalardan foydalaniladi.

Algoritmga nima kuch beradi?

Bilan solishtiring Nyuton-Raphson takrorlanishi

Takrorlash berilganni ishlatadi P va . Aksincha, Jenkins-Traubning uchinchi bosqichi

aniq Nyuton - Raphson takrorlanishidir ratsional funktsiyalar. Aniqrog'i, Nyuton-Rafson ratsional funktsiyalar ketma-ketligi bo'yicha bajarilmoqda

Uchun etarlicha katta,

birinchi darajali polinomga kerakli darajada yaqin

qayerda ning nollaridan biri . Garchi 3-bosqich aniq Nyuton-Rafson iteratsiyasi bo'lsa ham, differentsiatsiya amalga oshirilmaydi.

Tahlili H polinomlar

Ruxsat bering ning ildizi bo'ling P(X). Lagranj omillari P (X) bu ildizlarning kofaktorlari,

Agar barcha ildizlar har xil bo'lsa, unda Lagranj omillari ko'pi bilan darajadagi polinomlar makonining asosini tashkil etadi n - 1. Rekursiya protsedurasini tahlil qilish natijasida quyidagilar aniqlanadi H polinomlar koordinatali tasvirga ega

Har bir Lagranj koeffitsienti etakchi koeffitsientga ega 1, shuning uchun H polinomlarining etakchi koeffitsienti koeffitsientlar yig'indisidir. Normallashtirilgan H polinomlari shundaydir

Yaqinlashish buyurtmalari

Agar shart bo'lsa deyarli barcha takrorlanishlar uchun amal qiladi, normallashtirilgan H polinomlari hech bo'lmaganda geometrik tomonga yaqinlashadi .

Shart bo'yicha

kimdir uchun asimptotik taxminlarni oladi

  • 1-bosqich:
  • 2-bosqich uchun, agar s ga yaqin :
    va
  • va 3 bosqich uchun:
    va
ning kvadratikdan yuqori konvergentsiya tartibini keltirib chiqaradi , qayerda bo'ladi oltin nisbat.

Interversion quvvatni teskari takrorlash sifatida

Jenkins-Traub kompleks algoritmining barcha bosqichlari maxsus matritsaning o'ziga xos qiymatlarini aniqlashning chiziqli algebra masalasi sifatida ifodalanishi mumkin. Ushbu matritsa - chiziqli xaritaning koordinatali tasviri n-daraja polinomlarining o‘lchov fazosi n - 1 yoki undan kam. Ushbu xaritaning asosiy g'oyasi faktorizatsiyani talqin qilishdir

ildiz bilan va qolgan darajadagi omil n - 1 o'zgaruvchiga ko'paytirish uchun xos vektor tenglamasi sifatida Xkeyin bo'linuvchi bilan qoldiq hisoblash P(X),

Bu maksimal darajadagi polinomlarni xaritada aks ettiradi n - ko'pi bilan 1 darajadan polinomlarga n - 1. Ushbu xaritaning o'ziga xos qiymatlari ildizlari P(X), chunki xususiy vektor tenglamasi o'qiladi

shuni anglatadiki , anavi, ning chiziqli omilidir P(X). Monomial asosda chiziqli xarita bilan ifodalanadi sherik matritsasi polinomning P, kabi

natijada olingan koeffitsient matritsasi

Ushbu matritsaga teskari quvvatni takrorlash algoritmning uchta bosqichida siljishsiz, doimiy siljish va Rayleyning umumlashtirilgan siljishining uchta variantida qo'llaniladi. Matritsa operatsiyalari bilan emas, balki polinom arifmetikasida chiziqli algebra amallarini bajarish samaraliroq, ammo teskari kuch takrorlanishining xususiyatlari bir xil bo'lib qoladi.

Haqiqiy koeffitsientlar

Jenkins-Traub algoritmi ilgari tasvirlangan murakkab koeffitsientli polinomlar uchun ishlaydi. Xuddi shu mualliflar, shuningdek, haqiqiy koeffitsientli polinomlar uchun uch bosqichli algoritmni yaratdilar. Jenkins va Traubga qarang Kvadratik takrorlash yordamida haqiqiy polinomlar uchun uch bosqichli algoritm.[5] Algoritm haqiqiy arifmetikada to'liq ishlaydigan chiziqli yoki kvadratik omilni topadi. Agar murakkab va haqiqiy algoritmlar bir xil haqiqiy polinomga qo'llanilsa, haqiqiy algoritm to'rt baravar tezroq. Haqiqiy algoritm har doim birlashadi va yaqinlashish tezligi ikkinchi darajadan katta.

Ko'chirilgan QR algoritmi bilan aloqa

Matritsaning o'ziga xos qiymatlarini hisoblash uchun o'zgargan QR algoritmi bilan ajablanarli bog'liqlik mavjud. Dekker va Traubga qarang Ermit matritsalari uchun o'zgargan QR algoritmi.[6] Shunga qaramay, siljishlarni birinchi darajali polinomga yaqinlashadigan ratsional funktsiyalar ketma-ketligi bo'yicha Nyuton-Rafson iteratsiyasi sifatida qarash mumkin.

Dasturiy ta'minot va sinov

Jenkins-Traub algoritmi uchun dastur Jenkins va Traub sifatida nashr etildi Algoritm 419: Kompleks polinomning nollari.[7] Haqiqiy algoritm uchun dastur Jenkins sifatida nashr etilgan Algoritm 493: Haqiqiy polinomning nollari.[8]

Usullar ko'plab odamlar tomonidan keng sinovdan o'tgan. Bashorat qilinganidek, ular nollarning barcha taqsimotlari uchun kvadratik yaqinlashuvdan tezroq zavqlanishadi.

Biroq, quyidagi misolda ko'rsatilgandek aniqlikni yo'qotishiga olib keladigan polinomlar mavjud. Polinomning barcha nollari har xil radiusli ikki yarim aylanada yotadi. Uilkinson barqaror deflyatsiya uchun avval kichikroq nollarni hisoblash zarurligini tavsiya qiladi. Ikkinchi bosqich siljishlari birinchi yarim kichik doiradagi nollar topilishi uchun tanlanadi. Deflyatsiyadan so'ng yarim doiradagi nollar bilan polinom, agar daraja katta bo'lsa, shartli emasligi ma'lum; qarang Uilkinson,[9] p. 64. Asl polinom 60 daraja edi va qattiq deflyatsiya beqarorligiga duch keldi.

Adabiyotlar

  1. ^ Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P. (2007), Raqamli retseptlar: Ilmiy hisoblash san'ati, 3-nashr, Kembrij universiteti matbuoti, 470-bet.
  2. ^ Jenkins, M. A. va Traub, J. F. (1970), Uch bosqichli o'zgaruvchilar - polinom nollari uchun siljish takrorlanishi va uning umumiy Rayleyt takrorlanishiga aloqasi, Raqam. Matematika. 14, 252-263.
  3. ^ Ralston, A. va Rabinovits, P. (1978), Raqamli tahlil bo'yicha birinchi kurs, 2-nashr, McGraw-Hill, Nyu-York.
  4. ^ Traub, J. F. (1966), Polinom tenglamalarini yechish uchun global konvergent takrorlash funktsiyalari sinfi, Matematik. Komp., 20 (93), 113-138.
  5. ^ Jenkins, M. A. va Traub, J. F. (1970), Kvadratik takrorlash yordamida haqiqiy polinomlar uchun uch bosqichli algoritm, SIAM J. Numer. Anal., 7 (4), 545-566.
  6. ^ Dekker, T. J. va Traub, J. F. (1971), Ermit matritsalari uchun o'zgargan QR algoritmi, Lin. Algebra Appl., 4 (2), 137-154.
  7. ^ Jenkins, M. A. va Traub, J. F. (1972), Algoritm 419: Kompleks polinomning nollari, Qo'mondon ACM, 15, 97–99.
  8. ^ Jenkins, M. A. (1975), Algoritm 493: Haqiqiy polinomning nollari, ACM TOMS, 1, 178-189.
  9. ^ Uilkinson, J. H. (1963), Algebraik jarayonlardagi yaxlitlashdagi xatolar, Prentis Xoll, Englevud Cliffs, N.J.

Tashqi havolalar