3 o’zgaruvchili bosh mukammal formaga mos Voronoy sohasining 5 o’lchovli yoqlarini topish - Алгебра - Дипломные работы

Информация о документе

Цена	60000UZS
Размер	358.6KB
Покупки	0
Дата загрузки	28 Март 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Алгебра

Продавец

Rajabov Yorbek

Дата регистрации 19 Март 2026

0 Продаж

3 o’zgaruvchili bosh mukammal formaga mos Voronoy sohasining 5 o’lchovli yoqlarini topish

Купить

Mundarija.
Kirish………………………………………………………………………………………………………
1 Bob. Mukammal formalar nazariyasiga oid tushunchalar.
1.1. Musbat aniqlangan kvadratik formalar…………………………………………………
1.2. Mukammal formalar…………………………………………………………………………………
1.3. Mukammal formalarni izlash haqidagi Voronoy masalasi…………………..
2 Bob. mukammal forma Voronoy sohasining 5-o’lchovli yoqlari.
2.1. Mukammalashtirilgan Voronoy algoritmi……………………………………………….
2.2.
mukammal forma haqida ma’lumotlar……………………………………………….
2.3. mukammal forma Voronoy sohasining 5-o’lchovli yoqlari………………
Xulosa…………………………………………………………………………………………………….
Foydalanilgan adabiyotlar…………………………………………………………………………

1
Kirish.
Geometrik sonlar nazariyasining markaziy masalalardan bo’lgan
musbat aniqlangan mukammal formalar nazariyasidir.Mukammal formalar
nazariyasida aniq tayinlangan n lar uchun, barcha ekvivalent bo’lmagan
mukammal formalarni topish masalasi muhim masalalardan biridir.
Tayinlangan n larning o’sishi yoki har bir aniq mukammal formaning
arifmetik minimumini beruvchi nuqtalarni sonning kattaligiga qarab,
mukammal formalarni izlash (topish) ning Voronoy algoritmidan foydalanish
juda qiyinliklarga olib keldi.
Bitiruv malakaviy ishi, 3 o’zgaruvchili bosh mukammal formaga mos
Voronoy sohasining 5 o’lchovli yoqlarini topishga bag’ishlangan bo’lib kirish
qism, ikki bob, xulosa va foydalanilgan adabiyotlar ro’yxatidan iborat.
Bitiruv malakaviy ishining kirish qismida qaralayotgan mavzuning
dolzarbligi, maqsadi va vazifalari keltirilgan.
Bitiruv malakaviy ishida 1- bob 3 ta paragrafdan iborat bo’lib,
ularni quyidagicha ketma-ketlikda keltiramiz:
1.1da musbat aniqlangan kvadratik formalar n ta noma’lumlarni
kanonik ko’rinishga keltiriladi va kvadratik formalarni kanonik ko’rinishga
keltirishga oid misollar ishlandi. Kvadratik formalar musbat aniqlangan
kvadratik formalar, manfiy aniqlangan kvadratik formalar dan iborat.Bu
bitiruv malakaviy ishda faqat musbat aniqlangan kvadratik formalar
xususida fikr yuritiladi.
1.2da mukammal kvadratik formaning minimal matritsasi, musbat
aniqlangan kvadratik formaning koeffitsiyentlarini aniqlash,mukammal
kvadratik forma ta’rifi qayd etilgan.
2

1.3 da Ermit masalasining kelib chiqish, hamda Korkin-Zolotaryovning
limit formalariga ta’rif berilgan. Shuningdek bu paragrafda mukammal
formalarni izlash haqidagi Voronoy masalasi keltirib o’tilgan.
Bitiruv malakaviy ishining 2-bobi 3 ta paragrafdan iborat bo’lib ularni
quyidagicha ketma-ketlikda keltiramiz:
2.1 da mukammalashtirilgan Voronoy algoritmi kvadratik formalar
sistemasi yoqqa yotmasligi bilan ushbu yoqni aniqlash haqida o’rganiladi.
2.2 da
kvadratik formani musbat aniqlangan
kvadratik forma ekanligi haqidagi lemmani isbotlash ,
musbat aniqlangan
kvadratik formaning mukammal forma ekanligini isbotlashdan iborat.
2.3 da mukammal formaga mos Voronoy sohasining 5 o’lchovli yoqlari
haqida fikr yuritiladi.
Umuman olganda bitiruv malakaviy ishida qayd etilgan natijalarni
olishda algebra ,geometrik sonlar nazariyasi , mukammal formalar haqidagi
Voronoy algoritmli, mukammalashtirilgan Voronoy algoritmidan keng
foydalanildi.
Bitiruv malakaviy ishida qayd etilgan natijalar nazariy ahamiyatga ega
bo’lib, bu natijalardan 3-o’zgaruvchili mukammal formalarni Voronoy
atrofida topishda hamda 3-o’zgaruvchili ekvivalent bo’lmagan mukammal
formalarni topishda ham foydalanish mumkin.

Bitiruv malakaviy ishida quyidagi natijalar qayd etiladi:
1.
mukammal forma Voronoy sohasi aniqlandi.

2.
mukammal forma Voronoy sohasining
5-o’lchovli yoqlari toldi.
3
1.1. Musbat aniqlangan kvadratik formalar.
Agar n ta noma’lumning haqiqiy koeffitsiyentli kvadratik formasi n ta
musbat kvadratdan iborat normal ko’rinishga keltirilsa, ya’ni bu formaning rangi
ham inersiyasining musbat indeksi ham noma’lumlar soniga teng bo’lsa, bu forma
musbat aniqlangan deyiladi.
Quyida keltiriladigan teorema musbat aniqlangan formalarni, ularni normal
yoki kanonik ko’rinishga keltirib o’tirmasdan, tavsiflashga imkon beradi.
n ta x
1 ,x
2 …….x
n nona’lumning haqiqiy koeffitsiyent f kvadratik formasi hech
bo’lmaganda bittasi noldan faqli bo’lgan bu noma’lumlarning har qanday haqiqiy
qiymatlarida musbat qiymatlar qabul qilganda va faqat shundagina, bu forma
musbat aniqlangan bo’ladi.
Isboti. f forma musbat anqlangan bo’lsin, ya’ni ushbu normal ko’rinishga
keltiriladigan bo’lsin:
(1.1)
bu yerda
i=1,…,n (1.2)

va haqiqiy a
ij koeffitsiyentlardan tuzilgan determinant noldan faqli. Agar f ga
hech bo’lmaganda bittasi noldan farqli bo’lgan x
1, x
2 , . . . , x
n noma’lumlarning
ixtiyoriy haqiqiy qiymatlarini qo’ymoqchi bo’lsak, ularni dastlab (2 ) ga, so’ngra
4
esa barcha y
i lar uchun hosil qilingan qiymatlarni ( 1.1) ga qo’yish mumkin. (1.2 )
dan y
1, y
2 ………y
n lar uchun olingan qiymatlarning hammasi birdaniga nolga teng
bo’lmasligini qayd qilib qo’yaylik, chunki aks holda
i=1,…,n
chiziqli bir jinsli tenglamalar sistemasining determinanti noldan farqli bo’lsada, u
nol bo’lmagan yechimlarga ega ekanligini hosil qilar edik. y
1, y
2 ………y
n lar uchun
topilgan qiymatlarni ( 1.1) ga qo’yib, f formaning orasida nolga teng bo’lmaganlari
ham bor bo’lgan n ta haqiqiy sonning kvadratlari yig’indisiga teng bo’lgan
qiymatini hosil qilamiz; binobarin, bu qiymat qat’iy musbat bo’ladi.
Aksincha, f forma musbat aniqlangan bo’lmasin, ya’ni yo uning rangi yoki
inersiyasining musbat indeksi n dan kichik bo’lsin. Bu formaning (1.2) xosmas
chiziqli almashtirish yordamida keltiriladigan normal ko’rinishida yangi
noma’lumlardan hech bo’lmaganda bittasi, masalan, y
n yo butunlay yo’q yoki
minus ishora bilan turadi degan so’zdir. Bunday holda x
1 ,x
2 …….x
n noma’lumlar
uchun shunday haqiqiy qiymatlar tanlab olish mumkinki, noma’lumlarning bu
qiymatlarida f formaning qiymati nolga teng yoki, hatto manfiy bo’lishini
ko’rsatamiz. Masalan, x
1 ,x
2 …….x
n larning (1.2) dan

bo’lganda hosil bo’ladigan tenglamalar sistemasini Kramer qoidasi bo’yicha
yechganda hosil qilinadigan qiymatlari yuqorida tilga olingan qiymatlar bo’ladi
Darhaqiqat, x
1, x
2 , . . . , x
n larning bu qiymatlarida f forma: agar y
1 bu formaning
5
normal ko’rinishiga kirmasa, nolga, agar normal ko’rinishga manfiy ishora bilan
kirsa - 1 ga teng.
Hozir isbot qilingan teoremadan musbat aniqlangan kvadratik formalar
tatbiq qilinadigan hamma yerda foydalaniladi.Biroq bu teorema yordamida forma
koeffitsiyentlari bo’yicha uning musbat aniqlangan ekanligini tayinlash mumkin
emas. Bu maqsad uchun boshqa bir teorema xizmat qiladi Uni isbotlash va
ta’riflash uchun dastlab bitta yordamchi tushuncha kiritamiz, n ta noma’lumning
matritsasi bo’lgan f kvadratik formasi berilgan bo’lsin. Bu matritsaning
yuqori chap burchagiga joylashgan 1, 2 , . . . , n -tartibli minorlari, ya’ni
, ,…,
minorlar (bularning eng oxirgisi, ravshanki, A matritsaning determinanti bilan bir
xil) f formaning bosh minorlari deyiladi. Quyidagi teorema o`rinli: n ta
noma’lumning koeffitsiyentlari haqiqiy sonlardan iborat bo’lgan kvadratik

formasi uning bosh minorlari qat’iy musbat bo’’lganda va faqat shundagina,
musbat aniqlangan bo’ladi.
Isbot . n =1 bo’lganda teorema o’rinli, chunki buolda forma ax 2
ko’rinishga
ega va shuning uchun a >0 bo’lgandava faqat shundagina, musbat aniqlangan.
6
Shuning uchun teoremani n = 1 ta noma’lum uchun isbot qilingan deb faraz
qilib, uni n ta noma’lum uchun isbot qilamiz. Avval quyidagiga e’tibor beraylik:
koeffitsiyentlari haqiqy sonlardan iborat bo`lgan f kvadratik forma berilgan bulib,
uning koeffitsiyentlaridan tuzilgan matritsa n <4 bo’lsin. Agar f kvadratik forma
ustida haqiqy matritsasi Q bo’lgan xosmas chiziqli almashtirish bajarilayotgan
bo’lsa, u holda forma determinantining (ya’ni forma matritsasi determinantining)
ishorasi o’zgarmaydi.
Haqiqatdan ham almashtirishdan so’ng matritsasi Q`AQ bo’lgan kvadratik
formani hosil qilamiz, birok | Q` |=|A| bo’lgani uchun

ya’ni | A | determinant musbat songa ko’paytirilyapti.Endi ushbu kvadratik forma
berilgan bo`lsin:

Uni quyidagi kurinishda yozish mumkin:

(1.3)
bu yerda forma n -1 ta noma’lumning f formaning x 2
noma’lum kirmagan
hadlaridan tuzilgan kvadratik formasidir. Formaning bosh minorlari f formaning
7
oxirgisidan tashqari hamma bosh minorlari bilan bir xil ekanligi ravshan f forma
musbat aniqlangan bo’lsin. Bu holda forma ham musbat aniqlangan bo’ladi:agar
x
1 ,x
2 …….x
n noma’lumlarning forma qat’iy musbat bo’lmagan qiymat oladigan,
orasida nolga teng bo’lmaganlari ham bor bo’lgan qiymatlari mavjud bo’lganda
edi, u xolda qo’shimcha ravishda x
n =0 deb faraz qilib, x
1 ,x
2 …….x
n
noma’lumlarning qiymatlari orasida nolga teng bo’lmaganlari ham bor bo’lsa-da,
(1.3) ga ko’ra, f formaning ham qat’iy musbat bo’lmagan qiymatlarini hosil
qilgan bo’lar edik.
Shuning uchun induktiv farazga kura formaning hamma bosh minorlari,
ya’ni formaning, oxirgisidan tashqari, hamma minorlari qat’iy musbat. f
formaning oxirgi bosh minoriga, ya’ni A matritsaning determinantiga
kelsak, uning musbat ekanligi quyidagi mulohazalardan kelib chiqadi: f
forma musbat aniqlangan bulgani uchun, u xosmas chiziqli almashtirish
yordamida n ta musbat kvadratdan tuzilgan normal kurinishga keltiriladi. Bu
normal kurinishning determinanti sat’ny musbat, shuning uchun yutsoridagi izozga
kura f formaning determinanti ham musbat.Endi f formaning hamma bosh
minorlari qat’iy musbat bo’lsin. Bu yerdan formaning hamma bosh minorlari
musbat ekanligi, ya’ni induktiv faraz bo’yicha bu formaning musbat anitslangan
ekanligi kelib chitsadi. Binobarin, x
1 ,x
2 …….x
n noma’lumlarning shunday xosmas

chiziqli almashtirilishi mavjudki, u formani yangi x
1 ,x
2 …….x
n noma’lumlarning
n -1 ta musbat kvadratlari yig’indisi ko’rinishiga keltiradi. Bu chiziqli
almashtirishni, x
n =y
n deb faraz qilib, barcha x
1 ,x
2 …….x
n noma’lumlarni (xosmas)
chiziqli almashtirishgacha to’ldirish mumkin. (1.3) ga ko’ra f forma ko’rsatilgan
almashtirish orqali ushbu
8
f = (1.4)
ko’rinishga keltiriladi. b
in koeffitsiyentlarning aniq ifodalari biz uchun muhim
emas.

bo’lgani uchun
, i =1,2,…, n -1, z
n =y
n
xosmas chiziqli almashtirish f formani (1.4) ga ko’ra
(1.5)
kanonik ko’rinishga keltiradi.
f formaning musbat anitslangan ekanligini kursatish uchun s sonning musbat
ekanligini kursatish soldi. (5) tenglikning ung tomonida turgan formaning
determinanti s ga teng. Bi rots bu determinant musbat "bulishi kerak, chunki

(5!) tenglik ning ung tomoni f formadan ikkita xosmas chizitsli almashtirish
orsali {Osil silingan, f formaning determinanti esa bu formaning oxirgi bosh
minori sifatida musbat edi.
Teoremaning isboti tugadi.
9
Misollar 1. Ushbu
kvadratik forma musbat aniqlangan, chunki uning bosh minorlari musbat
,
2. Ushbu
kvadratik forma musbat aniklangan emas, chunki uning ikkinchi bosh mi
nori manfiy:

Musbat aniqlangan kvadratik formalarga o’xshash manfiy aniqlangan formalarni
ham, ya’ni normal ko’rinishlari noma’lumlarning faqat manfiy kvadratlaridangina
iborat xosmas kvadratik formalarni kiritish mumkinligini qayd qilib o`tamiz.
Normal ko`rinishlari bir xil ishorali kvadratlardan tuzilgan xos kvadratik formalar
ba’zan yarim aniqlangan formalar deyiladi. Nihoyat, normal ko’rinishlari

noma’lumlarning musbat kvadratlari bilan bir qatorda manfiy kvadratlardan ham
tuzilgan kvadratik formalar aniqlanmagan (aniqmas) deyiladi.
10
1.2 . Mukammal formalar.
Faraz qilaylik,
(1.2.1)
ixtiyoriy musbat aniqlangan kvadratik forma bo’lsin. (1.2.1) musbat
aniqlangan kvadratik formani m arifmetik minimumini beruvchi nuqtalarni
(1.2.2)
kabi belgilaymiz. Demak ,(1.2.2) nuqtalar sistemasi arifmetik minimum
nuqtalar beruvchi sistemasi. Bu nuqtalardan tuzilgan ushbu
Matritsa formaning minimal matritsa deyiladi. Bulardan quyidagi tenglikni

, (1.2.3)
hosil bo’ladi. Qaralayotgan
kvadratik forma musbat aniqlangan
kvadratik forma bo’lganligi uchun ushbu
,
Ikkita nuqtalar sistemasini bittasini olib qaraymiz. Yuqoridagi qilgan
farazimiz hamda arifmetik minimum ta’rifiga ko’ra quyidagi
tengsizlikka egamiz.
11

Tengsizlikka sistema
o’zgaruvchilarning butun
qiymatlari (2) nuqtalar sistemasida yotmasa ega bo’ladi.Bu sistemalardan
sistema ya’ni (0,0,…,0) nuqtalar kirmaydi. (3) tenglikni k indikslar
bo’yicha alohida- alohida yozsak ushbu tenglamalar

tenglamalar sistemasini (1) musbat aniqlangan kvadratik formaning
koeffitsiyentlarini aniqlashdagi tenglamalar sistemasi sifatida
qaraymiz. Bunday tenglamalar sistemasini yechishda ikki xil holatda bo’ladi.
1. Tenglamalar sistemasi cheksiz ko’p yechimga ega bo’ladi.
2. Tenglamalar sistemasi faqat yagona yechimga ega bo’ladi.
Ta’rif .Arifmetik minimum va arifmetik minimumni beradigan nuqtalar
to’plami bilan o’zaro bir qiymatni aniqlanadigan musbat aniqlangan kvadratik
forma mukammal kvadratik forma deyiladi.
Masalan,

kvadratik forma mukammal formadir. Haqiqatdan ham
formada
bo’lganligidan osongina uning musbat aniqlangan

12
kvadratik forma ekanligini ko’rish mumkin. Ya’ni Silvestr kriteriyasiga ko’ra
biz qarayotgan
kvadratik forma

musbat aniqlangan kvadratik forma ekanligi kelib chiqadi. Demak, qaralayotgan
kvadratik formaning barcha qiymatlari , ya’ni
da har doim qat’iy musbat ekanligi kelib chiqadi. Endi arifmetik

minimum ta’rifiga ko’ra
lar da qaraladi. Bundan
musbat
aniqlangan kvadratik formaning 0 dan farqli eng kichik musbat qiymati ya’ni
arifmetik minimumi
ekanligi,bu qiymatni esa ushbu±(0,1 )va ±(1,−1)
larda qabul qiladi.Bu sistemada faqat mubatlarni qa’bul qilamiz ,
ya’ni
(1,0) da φ
( 1,0 ) = 1 2
+0 2
+1 ∙
0
(0,1) da
da
ekanligi kelib chiqadi.
Endi qaralayotgan
musbat aniqlangan kvadratik forma uchun
arimetik minimum va arifmetik minimumni beruvchi nuqtalar
sistemasi orqali (3) tenglamalar sistemasini quyadagicha hosil
qilamiz:
S =1 da (1,0) ligidan
S =2 da (0,1) ligidan
S =3 da (1,-1) ligidan
Tengliklarni hosil qilamiz.Bu tengliklarni ushbu
13
Sistema kabi qarab

12
11
22
1
1
1
2
a
a
a

 
  

  
Topilgan bu koeffitsiyentlar qaralayotgan
musbat aniqlangan
kvadratik formaning koeffitsiyentlari bo ’ lib bir qiymatli aniqlangan . Bundan
mukammal forma ekanligi kelib chiqadi.
1.3.Mukammal formalarni izlash haqidagi Voronoy masalasi.
Korkin –Zolotaryovning limit formalari
(1.3.1)
n(n ≥ 2) o’zgaruvchili, haqiqiy koeffitsiyentli
Simmetrik matrissali,
14

11 12 1
21 22 2
1 2
, ,
, , ( ) .................
, ,
n
n
n n nn
a a l
a a a d d f
a a a
 




Kabi bo’lgan musbat aniqlangan kvadratik forma bo’lsin. Ixtiyoriy f musbat
aniqlangan kvadratik formani aniqlaydigan
koeffitsiyentlari yordamida
o’lchovli
Yevklit fazosida nuqtani
mos qo’yish mumkin. Bu moslik o’zaro bir qiymatli moslik bo’ladi,
ya’ni har bir kvadratik formaga
o’lchovli Yevklit fazosidagi
bitta nuqta va aksincha
Yevklit fazosidagi har bir nuqta bitta kvadratik
forma mos keladi.
Lemma. Barcha musbat aniqlangan kvadratik formalar koeffitsiyentlar
fazosi
Yevklit fazosida musbatlik konusi
ni hosil qiladi.
ISBOT .Haqiqatdan ham kvadratik formalar musbat aniqlangan
kvadratik formalar bo’lsa u holda;
1) va ( ) kvadratik formalar ham musbat aniqlangan for-
malar bo’ladi.
2) (1- ) kvadratik formalar ham musbat aniqlangan
kvadratik formalar bo’ladi.
musbat aniqlangan kvadratik formaning
nuqtalar bo’yicha olingan
(1.3.2)
15
Qiymatlarning aniq quyi chegarasi
musbat aniqlangan kvadratik for-

maning arifmetik minimum deyiladi.
(1.3.3)
Butun koordinatali hamda
tengliklarni bajaruvchi
Yevklid fazoning nuqtalari
musbat aniqlangan
kvadratik formaning arifmetik minimum beruvchi nuqtalari
bo’lsin.Musbat aniqlangan kvadratik forma m arifmetik minimumini
xossasiga asosan tabiiy ravishda
kabi
aniqlangan f musbat aniqlangan kvadratik formaning normallangan
arifmetik minimumni qarash mumkin. Bundan ixtiyoriy f musbat aniqlangan
kvadratik formaning normallangan arifmetik minimumi uchun
tenglik
bajariladi. Haqiqatdan ham

tenglik ixtiyoriy musbat aniqlangan kvadratik formanlar uchun o’rinli
bo’lishini ko’rsatadi.
Yuqorida aniqlangan f musbat aniqlangan kvadratik formaning
arifmetik minimumi musbatlik konusi da aniqlangan f formaning uzluksiz
funksiyasi bo’lsa
normallangan arifmetik minimum esa
da aniqlangan f formaning uzluksiz funksiyasidir.
Tarif . Agar
musbat aniqlangan kvadratik formani
musbat aniqlangan kvadratik formaga aylantiruvchi (o’tkazuvchi )
butun sonli unimodulyar chiziqli almashtirish mavjud
16

bo’lsa, u holda
musbat aniqlangan kvadratik formalar ekvivalent
deyiladi.
Xususiy holda agar
bo’lsa , unimodulyar chiziqli almashtirish f
formaning aftomorfizmi deb ataladi. Demak, agar almashtirish f
musbat aniqlangan kvadratik formaning avtomorfizmi bo’lsa,
o’rinli bo’ladi.
Ta’rif. f musbat aniqlangan kvadratik forma
funksiyaning lokal
maksimum nuqtasi bo’lsa, u holda f musbat aniqlangan kvadratik forma
limit (ekstrimal) forma deyiladi.
Yuqoridagi tushunchalardan n o’zgaruvchili ekvivalent bo’lmagan limit
formalarning soni chekliligidan aniq tayinlangan n lar uchun ekvivalent
bo’lmagan limit formalarni topish masalasi kelib chiqadi. Bu masala musbat
aniqlangan kvadratik formalarini arifmetik minimumlari haqidagi Ermit
masalasi deb yuritiladi.
Mukammal formalarni izlash haqidagi Voronoy masalasi.
Limit formalar ushbu asosiy xossaga ya’ni ixtiyoriy limit forma o’zining arifmetik
minimum va arifmetik minimumni beruvchi nuqtalari orqali bir qiymatli
aniqlanishidan Voronoy tomonidan quyidagi savolni qo’yishga sabab
bo’ladi. Agar limit formanining arifmetik minimum va arifmetik minimum
beruvchi nuqtalari bir qiymatli aiqlaydigan bo’lsa aksincha ixtiyoriy musbat
aniqlangan kvadratik formani uning arifmetik minimum va arifmetik
minimumini beruvchi nuqtalari bir qiymatli aniqlasa bu musbat aniqlangan
forma limit forma bo’ladimi yoki yo’qmi Voronoy ilmiy ishlarida arifmetik
minimum va arifmetik minimumni beruvchi nuqtalari bilan to’liq bir qiymatli
aniqlanadigan har qanday kvadratik formalar limit forma bo’lavermasligini
aniqlaydi va mukammal forma tushunchasini kiritadi.
17

Ta’rif.Agar minimum va arifmetik minimumni beruvchi nuqtalari bilan to’liq
aniqlangan f musbat aniqlangan kvadratik mukammal forma deyiladi.
Voronoy aniq tayinlangan n lar uchun ekvivalent bo’lmagan mukammal
formalarning soni chekli ekanligigini isbotlaydi. Bu esa aniq tayinlangan n lar
uchun mavjud bo’lgan barcha noekvivalent mukammal formalarni izlash
(topish) masalasiga asos bo’ladi.Ushbu masala mukammal formalarni
izlashning Voronoy masalasi deb nomlanadi.
18

2 Bob. mukammal forma Voronoy sohasining 5-o’lchovli
yoqla ri .
2.1 . Mukammalashtirilgan Voronoy algoritmi
Voronoy algoritmi.
Voronoy mukammal formalarni topish algoritmini, ya’ni Voronoy algoritmini
ishlab chiqadi. Voronoy algoritmiga asosan har bir f mukammal formaga

ko’rinishida ifodalanadigan barcha nomanfiy to’plamini mos qo’yadi. Bunda
, lar esa f formaning arifmetik minimum beruvchi nuqtalar
yordamida
aniqlanadigan chiziqli formalardir.
Bunday aniqlangan nomanfiy kvadratik formalar to’plamiga f formaning
Voronoy sohasi (oblasti) deyiladi va uni
kabi belgilanadi. - Voronoy
sohasi
Yevklid fazosida
noma ’ lumlarga nisbatan qandaydir bir jinsli
tengsizliklar yechimidan iborat bo ’ ladi , ya ’ ni
Kabi tengsizliklar sistemasidan iborat bo’ladi. mukammal forma bilan
qo’shni bo’lgan
mukammal formalarni quydagicha quriladi.
(1.3.4)

Bunda
19
Shu kabi hosil qilingan
mukammal formalar to’plamida
butun sonli unimodulyar chiziqli almashtirishlar
guruppasiga nisbatan ekvivalent bo’lmaganlarini ajratib mukammal
formaning
mukammal formalardan iborat to’plami hosil
bo’ladi. Bu to’plamga mukammal formaning unimodulyar chiziqli
almashtirishlar gruppasiga nisbatan Voronoy atrofi
deyiladi va
yoki kabi belgilanadi .
mukammal formaning Voronoy sohasini N-1-o’lchovli
yoqlari
tenglama bilan aniqlangan
hamda
formalar ushbu N-1o’lchovli yoqlariga
yotgan kvadratik formalar

kvadratik formalar esa
ga yotmagan kvadratik formalar bo’lsin. U
holda quyidagi tengliklar o’rinli bo’ladi.

(1.3.5)
(1.3.5) ga ko’ra quyidagiga ega bo’lamiz.
(1.3.6)
20
(1.3.7)
Lemma 1.
kvadratik formalar to’plami
yoqdagi
jami kvadratik formalar bo’lishi uchun ushbu
1) (1.3.6)tenglamalar sistemasiga rangi N-1 ga teng
2) Yechimlar to’plami
tengsizlikni qanoatlantirishi
zarur va yetarlidur.
V oronoy algoritmidagi
tenglikdagi bir xil larning oldidagi koefsintlarning tenglashtirib
noma’lumlarga bog’liq ushbu
(2.1.1)
tenglamalar sistemasini hosil qilamiz s=N bo’lgan holda (2.1.1)

tenglamalar sistemasini
(2.1.2)
kabi yagona yechimga ega bo’ladi . (2.1.2)dagi N ta tenglik
mukammal formaning Voronoy oblastining N-1 o’lchovli
yoqlarini to’liq aniqlaydi.
21
s>N bo’lgan holda (2.1.1) tenglamalar sistemasini
yechimi V=S-N ta parametirga bog’liq
(2.1.3)
ko’rinishga ega.Bunda chiziqli forma .
Lemma.2. kvadratik formalar f mukammal forma Voronoy
oblastining yoqiga yotmasligi uchun
va

keltirilgan munosabatarini koeffitsiyentlari har doim musbat bo’lishi zarur va
yetarli yoqning tenglamasi

bo’ladi. (1)va (2) lemmalarga ko’ra kvadratik formalar sistemasi
yoqqa yotmasligi bilan ushbu yoqni to’la aniqlaydi.Qisqacha aytganda bunday
sistemani ,,yoqlar’’ deb ataymiz.
22
2.2. mukammal forma haqida.
Korkin-Zolotoryov ilmiy asarlarida ushbu ko’rinishdagi
(2.2.1)
kvadratik forma o’rganildi.
Biz bu kvadratik formani mukammalashtirilgan Voronoy algoritmi yordamida
tahlil qilamiz.
Keltirilgan kvadratik formaning dastlab musbat aniqlangan kvadratik forma
ekanligi hamda mukammal forma ekanligini ko’rsatamiz.
Lemma.2.2.1. kvadratik forma musbat aniqlangan kvadratik formadir.
ISBOT. kvadratik formaning matritsasi

ekanligidan uning bosh minorlari
23
Ekanligidan uning musbat aniqlangan kvadratik forma ekanligi kelib
chiqadi. Demak , kvadratik forma musbat aniqlangan kvadratik forma bo’lgani
uchun hamda alohida o’zgaruvchilari kvadratlarining oldidagi koeffitsiyentlari birga
tengligidan arifmetik minimum ya’ni ekanligini aniqlaymiz. Arifmetik
minimum beruvchi nuqtalar
(1,0,0) ; (0,1,0) ; (0,0,1) ; (1,o,-1) ; (0,1,-1) ; (1,1,-1) (2.2.2)

ekanligini osongina tekshiramiz mumkin. Bu arifmetik minimum beruvchi
nuqtalarga ushbu
, (2.2.3)
chiziqli formalar mos keladi.
LEMMA.
musbat aniqlangan kvadratik forma mukammal formadir.
Isbot.3 o’zgaruvchili ixtiyoriy kvadratik formaning umumiy ko'rinishi

24
kabi bo’ladi. Bunday ko’rinishdagi kvadratik formaga ketma –ket
musbat
aniqlangan kvadratik formani arifmetik minimum va arifmetik minimum
beruvchi nuqtalarini qo’ysak, ya’ni
(1,0,0) :
(0,1,0) :
(0,0,1) :
(1,0,-1) :
(0,1,-1) :
(1,1,-1) :

tengliklardan noma’lumlarga nisbatan

chiziqli tenglamalar sistemasini hosil qilamiz. Bu chiziqli tenglamalar sistemasi
yagona
25

yechimga ega bo’ladi. Bu yechimlar
musbat aniqlangan kvadratik forma
koeffitsiyentlari bilan ustma-ust tushadi. Bundan esa
musbat aniqlangan
kvadratik forma arifmetik minimum va minimum beruvchi nuqtalari bilan bir
qiymatli aniqlanishi kelib chiqadi.
2.2.2.
mukammal formaga mos Voronoy sohasining
5 o’lchovli yoqlari.

Mukammalashtirilgan Voronoy algoritmiga ko’ra

bunda tenglikdagi o’xshash hadlarni
tenglashtirib noma’lum larni topib ularga nisbatan talab etilgan
shartni qo’llasak qaralayotgan mukammal formani Voronoy sohasi hosil
bo’ladi.
Bu tushunchani mukammal formaga qo’llaymiz.

lar mos ravishda (2.2.3) kabi chiziqli formadan iboratligidan
26

Qavslarni ochib o’xshash hadlani ixchamlab
27
t englikni hosil qilamiz.

Купить

Похожие документы
Yuzalarni hisoblashda aniq integraldan foydalanish
sodda ratsionaltenglamalar va ularning sistemalari
Kombinatorika elementlari
Kombinatorika masalalarining ehtimollar nazariyasi masalalarini yechishga tadbig‘i
Ko‘rsatkichli tenglamalar