Laguerres usuli - Laguerres method - Wikipedia

Yilda raqamli tahlil, Laguerning usuli a ildiz topish algoritmi moslashtirilgan polinomlar. Boshqacha qilib aytganda, tenglamani raqamli echishda Laguer usulidan foydalanish mumkin p(x) = 0 berilgan polinom uchun p(x). Ushbu usulning eng foydali xususiyatlaridan biri shundaki, bu keng miqyosli empirik tadqiqotlardan tortib, "ishonchli-olov" uslubiga juda yaqin, ya'ni deyarli har doim unga yaqinlashishi kafolatlangan. biroz polinomning ildizi, qanday bo'lishidan qat'iy nazar, qanday taxmin qilinmasin. Biroq, uchun kompyuter hisoblash, yanada samarali usullar ma'lum, ular yordamida barcha ildizlarni topish kafolatlanadi (qarang) Ildizlarni topish algoritmi § Ko'p polinomlarning ildizlari ) yoki barcha haqiqiy ildizlar (qarang Haqiqiy ildizni ajratish ).

Ushbu usul sharafiga nomlangan Edmond Laguer, frantsuz matematikasi.

Ta'rif

Polinomning bitta ildizini topish uchun Laguer usulining algoritmi p(x) daraja n bu:

• Dastlabki taxminni tanlang x₀
• Uchun k = 0, 1, 2, …
  • Agar ${ displaystyle p (x_ {k})}$ juda kichik, pastadirdan chiqing
  • Hisoblang ${ displaystyle G = { frac {p '(x_ {k})} {p (x_ {k})}}}$
  • Hisoblang ${ displaystyle H = G ^ {2} - { frac {p '' (x_ {k})} {p (x_ {k})}}}$
  • Hisoblang ${ displaystyle a = { frac {n} {G pm { sqrt {(n-1) (nH-G ^ {2})}}}}}}$, bu erda qochish uchun belgi tanlanib, mutloq kattaroq kattaroq qiymatni berish kerak ahamiyatini yo'qotish iteratsiya davom etganda.
  • O'rnatish ${ displaystyle x_ {k + 1} = x_ {k} -a}$
• Gacha takrorlang a etarlicha kichik bo'lsa yoki takrorlashning maksimal soniga erishilgan bo'lsa.

Agar ildiz topilgan bo'lsa, tegishli chiziqli omilni olib tashlash mumkin p. Ushbu deflyatsiya pog'onasi polinom darajasini bir marta kamaytiradi, natijada barcha ildizlar uchun yaqinlashishlar bo'ladi p topish mumkin. Shunga qaramay, deflyatsiya taxminan aniq omillardan sezilarli farq qiladigan taxminiy omillarga olib kelishi mumkinligiga e'tibor bering. Ushbu xato, agar ildizlar kattalashib borayotgan tartibda topilgan bo'lsa.

Hosil qilish

The algebraning asosiy teoremasi har bir narsani ta'kidlaydi ndaraja polinom ${ displaystyle p}$ shaklida yozilishi mumkin

${ displaystyle p (x) = C (x-x_ {1}) (x-x_ {2}) cdots (x-x_ {n}),}$

shu kabi ${ displaystyle x_ {k}}$ qayerda ${ displaystyle (k = 1,2, ..., n)}$ polinomning ildizlari. Agar biz olsak tabiiy logaritma ikkala tomonning ham, biz buni topish

${ displaystyle ln | p (x) | = ln | C | + ln | x-x_ {1} | + ln | x-x_ {2} | + cdots + ln | x-x_ { n} |.}$

Tovarni quyidagicha belgilang

${ displaystyle G = { frac {d} {dx}} ln | p (x) | = { frac {1} {x-x_ {1}}} + { frac {1} {x-x_ {2}}} + cdots + { frac {1} {x-x_ {n}}},}$

va inkor qilingan ikkinchi hosila

${ displaystyle H = - { frac {d ^ {2}} {dx ^ {2}}} ln | p (x) | = { frac {1} {(x-x_ {1}) ^ { 2}}} + { frac {1} {(x-x_ {2}) ^ {2}}} + cdots + { frac {1} {(x-x_ {n}) ^ {2}} }.}$

Keyin biz Acton deb atagan narsani "taxminlarning keskin to'plami" ga aylantiramiz, chunki biz izlayotgan ildiz shunday deyiladi: ${ displaystyle x_ {1}}$ bizning taxminimizdan ma'lum masofa ${ displaystyle x}$va boshqa barcha ildizlar bir oz masofada to'plangan. Agar biz ushbu masofalarni belgilasak

${ displaystyle a = x-x_ {1} ,}$

va

${ displaystyle b = x-x_ {i}, quad i = 2,3, ldots, n}$

keyin bizning tenglamamiz ${ displaystyle G}$ sifatida yozilishi mumkin

${ displaystyle G = { frac {1} {a}} + { frac {n-1} {b}}}$

va uchun ifoda ${ displaystyle H}$ bo'ladi

${ displaystyle H = { frac {1} {a ^ {2}}} + { frac {n-1} {b ^ {2}}}.}$

Ushbu tenglamalarni echish ${ displaystyle a}$, biz buni topamiz

${ displaystyle a = { frac {n} {G pm { sqrt {(n-1) (nH-G ^ {2})}}}}}}$,

Bu erda maxrajning mutloq kattaroq qiymatini hosil qilish uchun yoki unga teng keladigan kompleks sonning kvadrat ildizi tanlanadi:

${ displaystyle operator nomi {Re} , ({ overline {G}} { sqrt {(n-1) (nH-G ^ {2})}} ,)> 0}$,

qayerda Qayta murakkab sonning haqiqiy qismini bildiradi va G ning murakkab konjugati hisoblanadi G; yoki

${ displaystyle a = { frac {p (x)} {p '(x)}} cdot left ({ frac {1} {n}} + { frac {n-1} {n}} , { sqrt {1 - { frac {n} {n-1}} , { frac {p (x) p '' (x)} {p '(x) ^ {2}}}} } o'ng) ^ {- 1}}$,

bu erda manfiy bo'lmagan haqiqiy qismga ega bo'lish uchun murakkab sonning kvadrat ildizi tanlanadi.

Ning kichik qiymatlari uchun p(x) ushbu formula uchinchi tartib ofsetidan farq qiladi Halley usuli ning xatosi bilan O(p(x)³), shuning uchun ildizga yaqin konvergentsiya ham kubik bo'ladi.

E'tibor bering, hatto "taxminlarning keskin to'plami" ba'zi bir polinomlar uchun ishlamasa ham p(x), p(x) tegishli polinomga aylantirilishi mumkin r buning uchun taxminlar to'g'ri, masalan. kelib chiqishini mos keladigan murakkab songa almashtirish orqali w, berib q(x) = p(x − w), agar kerak bo'lsa aniq ildizlarga aniq kattaliklarni berish (agar ba'zi bir ildizlar murakkab konjugat bo'lsa) va keyin olish r dan q(x) ichida ishlatiladigan ildiz kvadratini o'zgartirishni qayta-qayta qo'llash orqali Greyff usuli kichikroq ildizlarni eng katta ildizdan sezilarli darajada kichikroq qilish uchun etarli vaqt (va shuning uchun taqqoslaganda klasterli); Graeffe uslubidagi taxminiy ildiz keyin Laguerre usuli uchun yangi iteratsiyani boshlash uchun ishlatilishi mumkin. r. Taxminan ildiz p(x) keyin to'g'ridan-to'g'ri buning uchun olinishi mumkin r.

Agar biz atamalar yanada kuchli taxmin qilsak G ildizlarga mos keladi x_men, men = 2, 3, …, n ildizga mos keladigan atama bilan taqqoslaganda juda oz x₁, bu olib keladi Nyuton usuli.

Xususiyatlari

X ^ 4 + 2 * x ^ 3 + 3 * x ^ 2 + 4 * x + 1 polinomlari uchun Laguer usulining tortishish zonalari

Agar x polinomning oddiy ildizi p(x), keyin Laguerning usuli yaqinlashadi kub shaklida har doim dastlabki taxmin x₀ ildizga etarlicha yaqin x. Boshqa tomondan, agar x a bir nechta ildiz u holda yaqinlashish faqat chiziqli bo'ladi. Bu takrorlanishning har bir bosqichida polinom va uning birinchi va ikkinchi hosilalari uchun qiymatlarni hisoblash penyasi bilan olinadi.

Laguer uslubining asosiy afzalligi shundaki, uning deyarli yaqinlashishi kafolatlangan biroz polinomning ildizi boshlang'ich taxminiy tanlangan joydan qat'iy nazar. Bu kabi boshqa usullardan farq qiladi Nyuton-Raphson usuli bu noto'g'ri tanlangan dastlabki taxminlar uchun birlashtirilmasligi mumkin. Hisoblashda kvadrat ildiz olinishi sababli u hatto polinomning murakkab ildiziga yaqinlashishi mumkin a yuqorida manfiy raqam bo'lishi mumkin. Bu usul qo'llanilayotgan dasturga qarab bu ustunlik yoki majburiyat deb hisoblanishi mumkin. Ampirik dalillar shuni ko'rsatdiki, konvergentsiya qobiliyatsizligi juda kam uchraydi va bu umumiy maqsadli polinom ildizini topish algoritmi uchun yaxshi nomzodga aylanadi. Biroq, algoritmning juda cheklangan nazariy tushunchasini hisobga olgan holda, ko'plab raqamli tahlilchilar uni shunday ishlatishga ikkilanadilar va yaxshi tushunilgan usullarni afzal ko'rishadi. Jenkins – Traub algoritmi, buning uchun yanada qat'iy nazariya ishlab chiqilgan. Shunga qaramay, algoritmni boshqa "ishonchli" usullar bilan taqqoslaganda juda oddiy, ularni qo'lda yoki avtomatik kompyuter mavjud bo'lmaganda cho'ntak kalkulyatori yordamida ishlatish oson. Usulning birlashish tezligi shuni anglatadiki, yuqori aniqlikka erishish uchun kamdan-kam takrorlashni hisoblash juda kamdan-kam talab qilinadi.

Adabiyotlar

• Acton, Forman S. (1970). Ishlaydigan raqamli usullar. Harper va Row. ISBN  0-88385-450-3.
• Goedecker, S. (1994). "Polinomlarning ildizlarini topish algoritmlari to'g'risida eslatma". SIAM J. Sci. Hisoblash. 15 (5): 1059–1063. doi:10.1137/0915064.
• Mekwi, Vankere R. (2001). "Polinomlarning ildizlari uchun takroriy usullar". Magistrlik dissertatsiyasi, Oksford universiteti. Arxivlandi asl nusxasi 2012-12-23 kunlari.
• Pan, V. Y. (1997). "Polinom tenglamasini echish: ba'zi tarix va yaqin taraqqiyot". SIAM Rev.. 39 (2): 187–220. doi:10.1137 / S0036144595288554.
• Press, WH; Teukolskiy, SA; Vetterling, WT; Flannery, BP (2007). "9.5.3-bo'lim. Laguerning usuli". Raqamli retseptlar: Ilmiy hisoblash san'ati (3-nashr). Nyu-York: Kembrij universiteti matbuoti. ISBN  978-0-521-88068-8.
• Ralston, Entoni; Rabinovits, Filipp (1978). Raqamli tahlil bo'yicha birinchi kurs. McGraw-Hill. ISBN  0-07-051158-6.