Gorner usuli ( yoki Gorner sxemasi )



Download 1,11 Mb.
Sana20.07.2022
Hajmi1,11 Mb.
#831397
Bog'liq
Aliqulov Suhrob MI ALgo Gorner


Matematika va informatika fanlarida Gorner usuli ( yoki Gorner sxemasi ) polinomlarni baholash algoritmidir . Garchi Uilyam Jorj Xorner nomi bilan atalgan bo'lsa-da , bu usul ancha eskiroqdir, chunki u Xornerning o'zi tomonidan Jozef-Lui Lagranjga tegishliligi aytilgan bo’lsada, u Xitoy va Fors matematiklari tomonidan ko'p yuzlab yillar oldin kuzatish va hisob-kitoblarida uchragan bo’lishi mumkin. Kompyuterlar joriy etilgandan so'ng, bu algoritm polinomlar bilan samarali hisoblash uchun asosiy algoritmga bo'ldi.
Gorner sxemasi :
{\displaystyle {\begin{hizalangan}a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^ {n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x() a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{hizalangan}}}











Kamchiliklari
Horner qoidasining kamchiliklari shundaki, barcha operatsiyalar ketma- ket bog'liqdir , shuning uchun zamonaviy kompyuterlarda ko'rsatmalar darajasining parallelligidan foydalanish mumkin emas. Polinomni baholash samaradorligi muhim bo'lgan ko'pgina ilovalarda bir vaqtning o'zida ko'plab past tartibli polinomlar baholanadi (kompyuter grafikasidagi har bir piksel yoki ko'pburchak uchun yoki raqamli simulyatsiyadagi har bir katak kvadrat uchun), shuning uchun bir vaqtning o'zida parallelizmni topish shart, yagona polinomli baholash bunda ojizlik qiladi.
Samaradorligi
n darajali ko'phadning monomial shaklidan foydalangan holda baholash ko'pi bilan n ta qo'shishni va ( n2 + n )/2 ko'paytirishni talab qiladi, agar kuchlar takroriy ko'paytirish orqali hisoblansa va har bir monomial alohida baholansa. (Buni x ning kuchlarini takroriy baholash orqali n ta qoʻshimchaga va 2 n − 1 koʻpaytirishga qisqartirish mumkin .) Agar raqamli maʼlumotlar raqamlar (yoki bitlar) bilan ifodalangan boʻlsa, u holda sodda algoritm sondan taxminan 2 n marta saqlashni ham oʻz ichiga oladi. x bitlari (baholangan polinom taxminan x n kattalikka ega, va x n ning o'zini ham saqlash kerak ). Bundan farqli o'laroq, Horner usuli faqat n ta qo'shimcha va n ta ko'paytirishni talab qiladi va uning saqlash talablari x bitlari sonidan atigi n marta. Shu bilan bir qatorda, Horner usulini n ta birlashtirilgan ko'paytirish-qo'shish bilan hisoblash mumkin. Xorner usulini kn qoʻshish va koʻpaytirish bilan koʻphadning birinchi k hosilalarini baholash uchun ham kengaytirish mumkin.
Xorner usuli optimal hisoblanadi, ya'ni ixtiyoriy ko'phadni baholash uchun har qanday algoritm kamida shuncha amallardan foydalanishi kerak. Aleksandr Ostrowski 1954 yilda talab qilinadigan qo'shimchalar soni minimal ekanligini isbotladi. Viktor Pan 1966 yilda ko'paytirish soni minimal ekanligini isbotladi. Biroq, x matritsa bo'lsa, Horner usuli optimal emas.
Bu shuni ko'rsatadiki, ko'phad monomial shaklda baholanadi va vakillikning hech qanday oldindan shartiga yo'l qo'yilmaydi, bu polinom faqat bir marta baholansa mantiqiy bo'ladi. Biroq, agar oldindan shart qo'yishga ruxsat berilsa va polinom ko'p marta baholanishi kerak bo'lsa, unda tezroq algoritmlar mumkin . Ular ko'phadning tasvirini o'zgartirishni o'z ichiga oladi. Umuman olganda, n darajali ko'phadni faqat ⌊ n /2 ⌋ +2 ko'paytirish va n qo'shimchalar yordamida baholash mumkin.

Gorner sxemasi (algoritmi) dasturlashda:


Quyida biz Gorner sxemasini Python dasturlash tilida qanday yozilishi va qanday ishlashini ko’rib chiqamiz:
# Gorner sxemasi Pythonda

# gorner deb nomlangan funksiya yaratamiz:


def gorner(poly, n, x):
# funksiya qaytarishi kerak bo'lgan resultatga polinomialning
# #eng katta qiymatdagi koeffitsientni o'zlashtiramiz:
result = poly[0]

# Gorner algoritmmi orqali iteratsiyani bajaramiz:


for i in range(1, n):
result = result * x + poly[i]

return result
"""funksiyaga argument sifatida poli deb nomlangan
list turidagi massiv beriladi bu polinomialning koeffitsientlarini
ifodalaydi keyingi argument n polinomialning nechinchi darajali ekanligini
belgilaydi va so'ngi argument x polinomialning qaysi nuqtadagi qiymati
aniqlanishi zarur ekanligini bildiradi.
"""
# Funksiyani tekshirib ko'ramiz

# Funksiya quyidagicha


# 7x7+x6-5x5-2x3-6x2+2x-1 #
# x = 3
poly = [7, 1, -5, 0, -2, -6, 2, -1]
x = 2
n = len(poly)
# argumentlarni o'zlashtiramiz
print("Polinomialning qiymati:\t", gorner(poly, n, x))
Javob:
Polinomialning qiymati: 763
# Funksiyani tekshirib ko'ramiz

# Funksiya quyidagicha


# 7x7+x6-5x5-2x3-6x2+2x-1 #
# x = 3
poly = [7, 1, -5, 0, -2, -6, 2, -1]
x = 2
n = len(poly)
# argumentlarni o'zlashtiramiz
print("Polinomialning qiymati:\t", gorner(poly, n, x))

#Tekshirish uchun pythondagi arifmetik amallar


#yordamida polinomialni yaratib uning qiymatini hisoblab ko'ramiz
from math import pow
polinomial = 7*pow(x,7)+1*pow(x,6)-5*pow(x,5)-2*pow(x,3)-6*pow(x,2)+2*x-1
if polinomial==gorner(poly, n, x):
print(f"Polinomialning qo'lda hisoblangan qiymati:{polinomial}\n"
f"Gorner sxemasining qiymatiga {gorner(poly, n, x)} teng")
Javob:
Polinomialning qo'lda hisoblangan qiymati:763.0
Gorner sxemasining qiymatiga 763 teng
Download 1,11 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish