Gorner usuli ( yoki Gorner sxemasi )

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 ( n² + 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