Graeffes usuli - Graeffes method - Wikipedia

Yilda matematika, Greyff usuli yoki Dandelin-Lobacheskiy-Grafe usuli bu polinomning barcha ildizlarini topish algoritmi. Tomonidan mustaqil ravishda ishlab chiqilgan Germinal Per Dandelin 1826 yilda va Lobachevskiy 1834 yilda. 1837 yilda Karl Geynrix Graffe shuningdek, usulning asosiy g'oyasini kashf etdi.[1] Usul polinomning ildizlarini bir necha bor kvadratlarga ajratib ajratadi. Ildizlarning bu kvadratikasi bilvosita amalga oshiriladi, ya'ni faqat polinom koeffitsientlari ustida ishlaydi. Nihoyat, Vietening formulalari ildizlarini taxmin qilish maqsadida ishlatiladi.

Dandelin - Greyffe takrorlanishi

Ruxsat bering p(x) darajadagi polinom bo'ling n

Keyin

Ruxsat bering q(x) kvadratlarga ega bo'lgan polinom bo'ling uning ildizi sifatida,

Keyin yozishimiz mumkin:

q(x) endi polinom koeffitsientlari bo'yicha algebraik amallar bilan hisoblash mumkin p(x) yolg'iz. Keling:

u holda koeffitsientlar bog'liqdir

Greyffe, agar kishi ajralib tursa, deb kuzatdi p(x) uning toq va juft qismlariga:

keyin soddalashtirilgan algebraik ifodani oladi q(x):

Ushbu ibora faqat yarim darajadagi ikkita polinomni kvadratga kiritishni o'z ichiga oladi va shuning uchun usulning aksariyat qo'llanilishlarida qo'llaniladi.

Ushbu protsedurani bir necha marta takrorlash, ularning kattaligiga qarab ildizlarni ajratib turadi. Takrorlash k marta daraja polinomini beradi n:

ildizlari bilan

Agar asl polinomning ildizlari kattaligi qandaydir omil bilan ajratilgan bo'lsa , anavi, , keyin. ning ildizlari k- iteratsiya tez o'sib boruvchi omil bilan ajralib turadi

.

Klassik Greyff usuli

Keyingi Vetnam munosabatlari ishlatiladi

Agar ildizlar bo'lsa etarlicha ajratilgan, masalan, omil , , keyin takrorlanadigan kuchlar ildizlari omil bilan ajralib turadi , bu tezda juda katta bo'ladi.

Keyin takrorlanadigan polinomning koeffitsientlarini ularning etakchi muddati bilan taxmin qilish mumkin,

va hokazo,

nazarda tutgan

Va nihoyat, asl polinomning ildizlarining mutlaq qiymatlarini topish uchun logarifmalar qo'llaniladi. Faqatgina ushbu kattaliklar boshqa ildiz qidirish usullari uchun muhim boshlang'ich nuqtalarni yaratish uchun foydalidir.

Ushbu ildizlarning burchagini olish uchun ko'plab usullar taklif qilingan, eng sodda usuli (ehtimol murakkab) ildizning kvadrat ildizini ketma-ket hisoblashdir. , m dan tortib k 1 ga, va ikkala belgi variantining qaysi biri ildiz ekanligini tekshirish . Ning ildizlariga o'tishdan oldin uchun ildiz taxminiyligini aniqligini raqamli ravishda oshirish kerak bo'lishi mumkin , masalan tomonidan Nyuton usuli.

Graeffning usuli oddiy haqiqiy ildizlari bo'lgan polinomlar uchun eng yaxshi ishlaydi, ammo u murakkab ildizlari va koeffitsientlari bo'lgan polinomlarga va ko'pligi yuqori bo'lgan ildizlarga moslashtirilishi mumkin. Masalan, kuzatilgan[2] bu ildiz uchun ko'plik bilan d, kasrlar

moyil

uchun . Bu ildizlar to'plamining ko'plik tuzilishini baholashga imkon beradi.

Raqamli nuqtai nazardan, bu usul muammoli, chunki takrorlanadigan polinomlarning koeffitsientlari juda katta miqdordagi tartiblarni qamrab oladi, bu esa jiddiy sonli xatolarni nazarda tutadi. Bir soniya, ammo kichik tashvish shundaki, turli xil polinomlar bir xil Graeffe takrorlanishiga olib keladi.

Tangensial Greyff usuli

Ushbu usul raqamlarni qisqartirish bilan almashtiradi quvvat seriyasi sifatida ham tanilgan 1-darajali juft raqamlar. Bunga ramziy ma'noda "cheksiz algebraik" kiritish orqali erishiladi aniqlovchi xususiyat bilan . Keyin polinom ildizlari bor , vakolatlar bilan

Shunday qilib qiymati fraksiya sifatida osonlikcha olinadi

Cheksiz kichiklar bilan bunday hisoblash murakkab sonlar bilan hisoblashga o'xshash tarzda amalga oshiriladi. Agar kimdir tasodifiy tanlangan kompleks son bo'yicha murakkab koordinatalarni yoki dastlabki siljishni qabul qilsa, u holda polinomning barcha ildizlari aniq bo'ladi va natijada takrorlanish bilan tiklanadi.

Renormalizatsiya

Har bir polinomni domen va diapazonda kattalashtirish mumkin, natijada hosil bo'lgan polinomda birinchi va oxirgi koeffitsient bir o'lchamga ega bo'ladi. Agar ichki koeffitsientlarning kattaligi chegaralangan bo'lsa M, keyin Graeffe iteratsiyasining bir bosqichidan keyingi ichki koeffitsientlarning kattaligi bilan chegaralanadi . Keyin k birinchi bosqichlar chegarani oladi ichki koeffitsientlar uchun.

Kuchlarning o'sishi bilan chegarani engib o'tish uchun Malajovich-Zubelli koeffitsientlar va oraliq natijalarni kmasshtabli qutbli shaklda algoritmning uchinchi bosqichi

qayerda birlik uzunligining murakkab soni va ijobiy realdir. Quvvatni ajratish ko'rsatkichda mutlaq qiymatini pasaytiradi v tegishli dyadik ildizga. Dastlabki koeffitsientlarning kattaligi saqlanib qolganligi sababli, bu jarayon renormalizatsiya deb nomlandi.

Ushbu turdagi ikkita raqamni ko'paytirish to'g'ridan-to'g'ri, holbuki qo'shish faktorizatsiya qilinganidan keyin amalga oshiriladi , qayerda ikkala sonning kattasi sifatida tanlanadi, ya'ni . Shunday qilib

va bilan

Koeffitsientlar yakuniy bosqich k ning Graeffe takrorlanishining ba'zi bir sabablarga ko'ra katta qiymati k, juftliklar bilan ifodalanadi , . Nuqta to'plamining konveks konvertining burchaklarini aniqlash orqali ko'pburchak ildizlarining ko'pligini aniqlash mumkin. Ushbu qayta normalizatsiya qilishni teginish bilan takrorlash bilan konvertning burchaklaridagi koeffitsientlardan to'g'ridan-to'g'ri asl polinomning ildizlarini ajratib olish mumkin.

Shuningdek qarang

Adabiyotlar

  1. ^ Uy egasi, Alston Skott (1959). "Dandelin, Lobačevskiy yoki Graeffe". Amerika matematikasi oyligi. 66: 464–466. doi:10.2307/2310626. JSTOR  2310626.
  2. ^ Eng yaxshi, G.C. (1949). "Ildizlarni kvadratlashning Graeff usuli bo'yicha eslatmalar". Amerika matematikasi oyligi. 56 (2): 91–94. doi:10.2307/2306166. JSTOR  2306166.