2.4-§ Muvozanatga intilish
orqali vaznli grafga mos Markov operatorini belgilaymiz. Biz bu operatorni ni ga akslantiruvchi chiziqli operator sifatida qaraymiz. Bu operator Laplas operatori b ilan ayniyat bilan belgilangan.
Bundan esa operatorning barcha xos qiymatlari ko’rinishda bo’ladi, bu yerda soni operatorining xos qiymati bo’lib, va operatorlar bir xil xos qiymatga ega.
Belgilash olamiz. Bunda lar operatorning barcha xos qiymatlari bo’lib, ular karraligi bilan hisoblanganda o’sish tartibida tartiblangan. 2.3- teoremaga ko’ra quyidagilar o’rinlidir:
soni sodda xos qiymat bo’lib, unga mos xos funksiya o’zgarmas funksiyadir.
2.;
3. agar graf ikki qismdan iborat bo’lmasa u holda bo’ladi.
Quyidagicha yozib olamiz:
Agar graf ikki qismdan iborat bo’lsa, u holda soni sodda xos qiymat bo’lishi keyinroq isbotlanadi.
bo’lgani uchun simmetrik operatorlarning umumiy nazariyasiga ko’ra tengsizlik o’rinli bo’ladi.
Navbatdagi tasdiqda, operatorlar kompozitsiyadan foydalanib, ixtiyoriy
natural soni uchun operatorning darajasini qaraymiz.
Tasdiq. Istalgan funksiya va ixtiyoriy natural soni uchun
tenglik o’rinlidir. Bu yerda qadamdagi o’tkazish funksiyasi.
Isboti. bo’lganda tenglik Markov operatori ta’rifiga keladi. Induksiya usulidan foydalanamiz. Tasdiqni uchun o’rinli deb faraz qilib uchun isbotlaymiz:
Bu esa tasdiq isbotini yakunlaydi.
Navbatdagi teorema asosiy natijalardan biridir. Biz bunda
Belgilashdan foydalanamiz.
2.4- teorema. Faraz qilaylik, chekli, bog’langan, vaznli graf va uning Markov yadrosi bo’lsin. Ixtiyoriy funksiya uchun
deb olamiz. U holda ixtiyoriy natural soni uchun
Tengsizlik o’rinlidir,bu yerda
Xuddi shuningdek, agar ikki qismdan iborat bo’lmagan graf bo’lsa, u holda
Ya’ni da ketma - ketlik ga intiladi.
(2.7) baxolash ketma- ketlikning o’zgarmasga intilish tezligini beradi, agar deb olinsa, bu bo’yicha eksponensial kamayuvchidir.
soniga Markov operatorining spektral radiusi deyiladi. Haqiqatan ham , operatorning xos qiymatlari orqali uni quyidagicha yozish mumkin:
ekvivalent ravishda, soni
Munosabat bajariladigan eng kichik sonni beradi, chunki operatorning
1 dan farqli xos qiymatlari kesmada yotadi.
2.4 - teoremaning isboti. Agar ikki qismdan iborat bo’lgan graf bo’lsa, u holda 2.3 - teoremaga ko’ra
Munosabatlar o’rinli bo’ladi, bundan esa kelib chiqadi. Shu sababli da bo’ladiva(2.7)-tengsizlik (2.9) ni beradi. (2.7)-tengsizlikni isbotlash uchun operator xos funksiyalaridan ortonormal bazisni tanlaymiz, bunda
har qanday funksiya bazis bo’yicha quyidagicha
Yoyilmaga ega, bunda Parseval tengligiga ko’ra
Tenglik o’rinlidir. Quyidagi tengliklar o’rinli
Shunga ko’ra bo’yicha induksiyani qo’llab
ni hosil qilamiz. Ikkinchi tomondan biror o’zgarmas uchun ga egamiz. Bu o’zgarmas normallashtirish sharti yordamida aniqlanish mumkin, ya’ni
shu sababli , Malumki
va
Demak, bundan
hosil bo’ladi. Parseval tengligiga ko’ra
Isbotni boshlashdan oldin ta’kidlaganimizdek operatorning
bo’lgandagi barcha xos qiymatlari kesmada yotadi, shu sababli . Bundan tashqari
Ekanligini hisobga olib
ni hosil qilamiz. Bu esa o’z navbatida teorema isbotini yakunlaydi.
2.5 tasdiq. Faraz qilaylik ikki qismdan iborat bo’lmagan, chekli , bog’langan graf bo’lib, unga mos tasodifiy yurish bo’lsin. uchni fiksirlab, ning taqsimot funksiyasini qaraymiz:
U holda
Bo’ladi, bu yerda
Bundan taashqari,
baxolash o’rinlidir.
(2.11) baxolashdan istalgan uchun
bo’lishi kelib chiqadi.
Isboti. Graf ikki qismdan iborat bo’lmagani uchun bo’ladi. Shu sababli (2.10) munosabat (2.11) yoki (2.12) baxolashdan kelib chiqadi. (2.11) ni isbotlash uchun ushbu
taqsimot funksiyani qaraymiz va
ekanligini eslatib o’tamiz. Ma’lumki,
U holda 2.4- teoremada deb olib
ga ega bo’lamiz.Bunday tanlangan funksiya uchun
va
tengliklar o’rinlidir,bunga ko’ra
bo’lib (2.10) ning to’g’ri ekanligini ta’minlaydi. Tasdiq isbotlandi.
Agar (2.9) ga ekvivalent bo’lgan (2.10) bajarilsa, u holda tasodifiy yurishga ergodik deyiladi. Yuqorida biz ko’rdikki, chekli bog’langan , ikki qismdan iborat bo’lmagan grafdagi tasodifiy yurish ergodikdir. Agar bo’lsa u holda mazkur tasdiq o’rinli bo’lmasligini ko’rsatamiz. Faqatgina ikki qismdan iborat graflarda bo’lishi mumkin. Agar 2 soni operator uchun xos qiymat bo’lib, unga mos xos funksiya bo’lsa, u holda funksiya operatorning -1 xos qiymatiga mos xos funksiyasi bo’ladi, ya’ni U holda ga ega bo’lamiz. Shu sababli da ketma- ketlik biror funksiyaga ham yaqinlashmaydi.
Ikki qismdan iborat bo’lmagan graf holida taqsimot funksiyalar ketma-ketligining muvozanat o’lchoviga yaqinlashish (intilish) tezligi bilan aniqlanadi, bu yerda
Berilgan kichik ε>0 soni uchun aralash vaqtini shartdan aniqlaymiz. Bundan
kelib chiqadi.
Bu va lar bilan (2.12) dan
ni hosil qilamiz.Bunda ε soni
shartdan tanlanadi, bu esa
ga ekvivalentdir.
Katta graflarga doir ko’plab misollarda soni 0 ga, soni esa 2 ga juda yaqin bo’ladi. Quyida [0;2] kesmada xos qiymatlar belgilangan:
Bu holda biz
va
ga ega bo’lamiz, shu sababli
bo’ladi.
Navbatdagi tasdiq ba’zi maxsus hollarda operator spektori haqida qo’shimcha ma’lumot beradi.
2.6- teorema. Faraz qilaylik, chekli, bog’langan, vaznli graf bo’lib, bo’lsin.
a) quyidagitengsizlik o’rinli:
Bundan tashqari
Agar qo’shimcha ravishda da tugun bo’lmasa, u holda
:
va
b) Agar sodda vaznli to’la graf bo’lsa, u holda,
Agar to’la graf bo’lmasa, u holda
3) Agar ikki qismdan iborat va soni ham operatorning xos qiymati bo’lsa u holda soni ham operatorning xos qiymatlari bo’lib, ularning karraliklari ustma – ust tushadi. Xususiy holda, 2 soni operatorning sodda xos qiymati bo’ladi.
Sodda vaznli graf to’la bo’lishi uchun bo’lishi zarur va yetarlidir.Bundan tashqari graf ikki qismdan iborat bo’lishi uchun bo’lishi zarur va yetarli.
Isboti. a) Faraz qilaylik sistema operator xos funksiyalaridan tashkil topgan dagi ortonormal bazis bo’lib bo’lsin. bazisda operatorning matritsasi
dioganal ko’rinishida bo’ladi.
ekanligini hisobga olgan holda
ga ega bo’lamiz.
Ta’kidlash lozimki, soni ba’zisning tanlanishidan bog’liq emas. Boshqa bazisni quyidagicha tanlaymiz: ning barcha qirralarini kabi nomerlaymiz, va funksiyalarni qaraymiz, bu yerda lar ga ba’zisni tashkil qiladi. Bu ba’zisda ∈ funksiyaning komponentlari qiymatlarga tengdir. operatorni qayta yozib olamiz
Bu bazisda operatorga mos matritsa dioganalida soni, va da soni turadi. Bunga ko’ra
(2.19) bilan taqqoslab (2.15) ning isbotini hosil qilamiz. soni ta sondan iborat to’plamning eng kichik soni bo’lgani uchun (2.15) dan (2.16) ni kelib chiqadi.
Agar grafda tugunlar bo’lmasa, u holda va (2.20) dan (2.17) kelib chiqadi. soni to’plamning eng katta element ekanligidan (2.18) ni hosil qilamiz.
b) xos qiymatga mos keluvchi ta chiziqli bog’lanmagan xos funksiyalarni qurishimiz zarur. Yuqoridagi kabi deb olamiz va uchun quyidagi ta funksiyalarni qaraymiz.
Ushbu
Tenglik o’rinlidir. Agar bo’lsa u holda va
Yig’indida ga teng qo’shiluvchi faqat bitta bo’ladi, bu bo’lganda boshqa hamma hollarda nolga teng bo’ladi. Ushbu sababli
Agar bo’lsa, u holda va
Yig’indida 1 ga teng had faqat bir marta bo’lganda qatnashadi; shunga ko’ra
Agar bo’lsa u holda bo’lib
Yig’indida -1 va 1 ga teng hadlar mavjud bo’lib, qolgan hadlar nolga tengdir, shu sababli
bo’ladi. Demak, ekan. sistema chiziqli bog’lanmagan bo’lganligi uchun soni karrali xos qiymat bo’lishini ko’rish mumkin. Bu esa isbotni yakunlaydi.
c) variatsion prinsipga ko’ra
bo’lib shart xos qiymatga mos xos funksiya o’zgarmas ekanligidan paydo bo’ladi. ekanligini isbotlash uchun bo’ladigan
funksiya qurish yetarlidir.
Tasdiq. ni fiksirlaymiz va indikator funksiyani qaraymiz. U holda
Ma’lumki,
Va Grin formulasiga ko’ra
bu esa ekanligini bildiradi, shuni takidlash lozimki, tugunlar bo’lmagan holda tenglikni hosil qilamiz.
Bundan tashqari, istalgan o’zgarmas soni uchun o’rinlidir.
2-tasdiq.Faraz qilaylik lar dagi ikkita funksiya bo’lib
holda o’rinlidir.
tashuvchilar o’zaro kesishmaydigan va bog’lanmaganbo’lsin, ya’ni va ekanligidan va kelib chiqadi. U holda
Ko’rinib turibdiki, ekanligini isbotlaymiz. Haqiqatan ham, agar bo’lsa, u holda bo’ladi. Agar bo’lsa u holda bo’ladi. Bundan esa istalgan uchun va bo’lishi kelib chiqadi. Shu sababli
va demak Ushbu
ayniyatlardan foydalanib.
va
larni hosil qilamiz. Farazimizga ko’ra
va
tengliklar o’rinli, bundan esa
kelib chiqadi.
Endi bo’ladigan funksiyani ko’ramiz. Graf to’la bo’lmagani uchun ikkita turli va uchlar topilib, bo’ladi. Quyidagi ko’rinishdagi funksiyani qaraymiz:
bu yerda va keofisientlar shartdan tanlanadi. Masalan, va hamda va funksiyalarning tashuvchilari turli va bog’lanmagan bo’lgani uchun yengsizlikni hosil qilamiz. Bu esa isbotni yakunlaydi.
d) Markov operatorining α xos qiymati operatorning λ xos qiymati bilan tenglik orqali bog’langandir. Shu sababli tasdiq quyidagi tasdiqqa ekvivalentdir: agar α sonioperatorning xos qiymati bo’lsa, u holda -α soni ham operatorning xos qiymati bo’lib, ularning karraliklari ustma – ust tushadi. Haqiqatan ham ekanligidan kelib chiqadi.
larning shunday bo’linmasiki, munosabat va lar faqat ga yoki ga qarashli bo’lgandagina bajariladi. operatorning α xos qiymatiga mos bo’lgan xos funksiya uchun
funksiyani qaraymiz. funksiya operatorning xos qiymatiga mos xos funksiya bo’lishini isbotlaymiz. Barcha lar uchun
ga ega bo’lamiz va xuddi shuningdek barcha lar uchun
ga ega bo’lamiz.
Shunday qilib son operatorning xos qiymati bo’lib, unga mos xos funksiya ga teng ekan.
Faraz qilaylik soni operator uchun karrali, soni esa karrali xos qiymati bo’lsin. ekanligini isbotlaymiz. α xos qiymatga mos keluvchi chiziqli bog’lanmagan xos funksiya mavjud. (2.21) formuladan foydalanib xos qiymatga mos keluvchi xos funksiyalar quramiz, ular chiziqli bog’lanmagandir. Shu sababli tengsizlik o’rinli. bo’lganligi uchun xuddi shu usul bilan ekanligini hosil qilamiz. Demak ekan.
soni operatorning sodda xos qiymati bo’lganligi uchun 2 soni operator uchun sodda xos qiymat bo’ladi. Isbotdan ko’rinib turibdiki,2 xos qiymatga mos xos funksiya quyidagicha bo’ladi:
bu yerda ixtiyoriy nolmas o’zgarmas. Shu bilan isbot yakunlandi.
|
