3-Mavzu: Bir o’zgaruvchili funksiyalarning minimumni topishning to’g’ri usullari
Download 185.64 Kb. Pdf ko'rish
|
3-MAVZU
- Bu sahifa navigatsiya:
- 1. Saylab olish usuli
- 3. Oltin kesma usuli.
|
3-Mavzu: Bir o’zgaruvchili funksiyalarning minimumni topishning to’g’ri usullari. Berilgan 𝑦 = 𝑓(𝑥) funksiyasining minimum yoki maxsimum nuqtalarini qidirishning ko’p sonli xar xil usullari bor. Bunday usullar hisoblash formulasiga bog’liq bir necha guruhlarga ajratiladi. Agarda hisoblash usilining formulasiga faqatgina funksiyaning qiymatlari ishtirok etsa bunday usullar minimum masalasini yechishning to’g’ri yoki no’linchi tartibli usullari deyiladi. Agarda usulning hisoblash formulasini tuzish uchun funksiyaning 1-tartibli usullar deyiladi. Shu tartibda agarda hisoblash formulasi tuzishga 1 va 2 tartibli xosilalarning qiymatlari qatnashsa bunday usullar 2-tartibli usullar deyiladi va hakozo. Agarda berilgan 𝑓(𝑥) funksiyasining xosilalarni hisoblash qiyin bo’lmasa bunday hollarda yuqori tartibli usullardan foudalangan maqul bo’ladi. Sababi nunday usullar hisoblash formulalari ancha qiyin bo’lsa ham berilgan masalaning yechimini kerakli aniqlik bilan hisoblashga mumkinchilik beradi. Bu yerda hisoblash amaliyotida qo’llaniladigan minimum 𝑓(𝑥), 𝑥𝜖[𝑎, 𝑏] (1) Bu masalani yechishga imkoniyat beradigan to’g’ri usullarining bir guruhi bilan tanishamiz:
𝑓(𝑥) 𝜖 𝑄[𝑎, 𝑏] ya’ni unimodal funksiyalarning minimum nuqtalarni hisoblash uchun qo’llaniladi. Usulning ma’nosi quyidagidan iborat. Usulning ma’nosi 𝑥𝜖[𝑎, 𝑏] kesmada teng o’lchamli tor yasaladi ω 𝒏 = {a = x 0
1
2
n−1
n = b} Ya’ni: 𝑥 𝑖+1 − 𝑥 𝑖 = ℎ = 𝑐𝑜𝑛𝑠𝑡, 𝑖 = 0, 𝑛 − 1 ̅̅̅̅̅̅̅̅̅̅, 𝑥 0 + 𝑖ℎ = 𝑎 + 𝑖ℎ, 𝑖 = 0, 𝑛 ̅̅̅̅̅
ℎ = 𝑏−𝑎
𝑛 , 𝑛 > 0 butun son. Shundan so’ng 𝑥 𝑖 𝜖[𝑎, 𝑏], 𝑖 = 0, 𝑛 ̅̅̅̅̅ nuqtada 𝑓(𝑥 𝑖 ), 𝑖 = 0, 𝑛 ̅̅̅̅̅ funksiyalarning qiymatlari hisoblanadi. 𝑥 𝑖
𝑥 0
𝑥 1
𝑥 2
… 𝑥 𝑛−1 𝑥 𝑛 𝑓(𝑥
𝑖 ) 𝑓(𝑥 𝑖 ) 𝑓(𝑥 𝑖 ) 𝑓(𝑥 𝑖 ) … 𝑓(𝑥 𝑛−1
) 𝑓(𝑥
𝑛 )
𝑛 soni 𝑏−𝑎
𝑛 ≤ 𝜀 shartning bajarilishidan saylab olinadi. Bundan 𝑛 ≥ 𝑏−𝑎 𝑛
nisbatiga ega bo’lamiz. 𝑓(𝑥) faraz qilishimiz bo’yicha 𝑓(𝑥) 𝜖 𝑄[𝑎, 𝑏] bo’lganligidan bu funksiya global minimum nuqtaga ega bo’ladi. Mayli, ba’zi bir 𝑥
𝜖[𝑎, 𝑏] nuqtada 𝑓(𝑥
𝑚 ) = min
𝑖=0,𝑛 ̅̅̅̅̅
𝑓(𝑥 𝑖 ) (2) Sharti bajarilsin shunda: 𝑥 ∗ ≈ 𝑥 𝑚 , 𝑓 ∗ = 𝑓(𝑥
∗ ) ≈ 𝑓(𝑥
𝑚 ) (3) deb qabul qilinadi. U butun sonini saylab olishimiz bo’yicha bunda yo’l qo’yilgan xatolik 𝜀 𝑚
𝑚 )| ≤ 𝜀
𝑚 tengsizligini bajarishga olib keladi. Bunda 𝜀 𝑚
bajariladi. Saylab olish usuli to’g’ri usullarning orasidagi eng oddiy usul bo’lib, unimodal funksiyaning minimum nuqtaslarini taqribiy ravishda hisoblash uchun amaliyotda keng qo’llaniladi. 2. Kesmani teng o’rtasidan bo’lish usuli. Bu yerda ham minimum masalasi izlaniytgan uzluksiz differensiallanadigan va 𝑓(𝑥) 𝜖 𝑄[𝑎, 𝑏] ya’ni unimodal funksiya deb faraz qilinadi. Bu usulning asosiy ma’nosi [𝑎, 𝑏] kesmadan foydalanib bir-birining ichida yotgan kichik kesmadan ketma-ketligini tuzishdan iborat
[𝑎, 𝑏] ⊃ [𝑎 1 , 𝑏 1 ] ⊃ [𝑎
2 , 𝑏
2 ] ⊃ … ⊃ [𝑎 𝑛−1 , 𝑏
𝑛−1 ] ⊃ [𝑎
𝑛 , 𝑏
𝑛 ] Bu kesmalarning har birining ichida 𝑓(𝑥) funksiyaning izlanayotgan 𝑥 ∗ 𝜖[𝑎, 𝑏] minimum nuqtasi yotadi. Mayli 𝑓(𝑥) 𝜖 𝑄[𝑎, 𝑏] funksiyasi 𝑥 ∗ 𝜖[𝑎, 𝑏] minimum nuqtasini 𝜀 > 0 aniqligi bilan hisoblash talab qilinsin. Buning uchun avval 𝛿𝜖[0,2𝜀] sonini saylab olib quyidagi formulalar yordamida {𝑎 𝑛 }, {𝑏 𝑛 }, {𝑥 1 (𝑛)
} , {𝑥 2 (𝑛) } Sonlarning ketma-ketligini yasaymiz. 𝑎 0
𝑛 = 𝑏
𝑥 1 (𝑛−1) = (𝑎 𝑛−1
+ 𝑏 𝑛−1
− 𝛿)/2 𝑥 2 (𝑛+1) = (𝑎
𝑛−1 + 𝑏
𝑛−1 + 𝛿)/2
𝑎 𝑛 = 𝑎 𝑛−1 , 𝑏
𝑛−1 = 𝑥
2 (𝑛−1)
, 𝑎𝑔𝑎𝑟𝑑𝑎 𝑓(𝑥 1 (𝑛−1) ≤ 𝑥 2 (𝑛−1) )𝑏𝑜 ′ 𝑙𝑠𝑎, 𝑎 𝑛 = 𝑥 1 (𝑛−1)
, 𝑏 𝑛 = 𝑏 𝑛−1 , 𝑎𝑔𝑎𝑟𝑑𝑎 𝑓(𝑥 1 (𝑛−1)
> 𝑥 2 (𝑛−1) )𝑏𝑜 ′ 𝑙𝑠𝑎 Bu formula bilan hisoblashlarni bajarishning 𝑛 qadami 𝑥 𝑛 =
2 (𝑎 𝑛 + 𝑏 𝑛 ) deb qabul qiladi. Agarda |𝑓(𝑥
𝑛) | ≤ 𝜀 bo’lsa 𝑥 ∗ ≈ 𝑥
1 , 𝑓
∗ = 𝑓(𝑥
∗ ) ≈ 𝑓(𝑥
𝑛 ) deb qabul qilinadi. Bunda yo’l qo’yilgan xatolik 𝜀 𝑛 = 𝜀 𝑛 − 𝑎 𝑛 2 = (𝑏 − 𝑎 − 𝛿) 𝑛+1
+ 𝛿 2 (2) Sharti bajarilsa, hisoblashlar 𝜀 𝑛
3. Oltin kesma usuli. Mayli
𝑓(𝑥) 𝜖 𝑄[𝑎, 𝑏] bo’lsin bu funksiyaning minimum nuqtasini topishning oltin kesma usulining ma’nosi quyidagidan iborat. 1. 𝑏−𝑎
𝑥 1 −𝑎 = 𝑥 1 −𝑎 𝑏−𝑥
1 nisbatlari o’rinli bo’ladi. 2. 𝑥 1 , 𝑥 2 nuqtalari [ 𝑎, 𝑏] kesmaning oxirgi nuqtalaridan teng masofada yotadi, deb faraz qilinadi. 𝑥 2
1 (2) (2)- tenglikdan { 𝑥 1 = 𝑎 + 𝑏 − 𝑥 2 𝑥
= 𝑎 + 𝑏 − 𝑥 1 (3) Shunday qilib oltin kesmaning bir nuqtasi ma’lum bo’lsa uning ikkinchi nuqtasini (3)- formula bilan hisoblash mumkin bo’ladi. Endi (1)- tenglamani soddalashtirib, kelib chiqqan tenglamadan 𝑥 1 nuqtasining koordinatalarini aniqlashga boladi. (𝑏 − 𝑎)(𝑏 − 𝑥 1 ) = (𝑥 1 − 𝑎)
2
𝑏 2 − 𝑏𝑥
1 − 𝑎𝑏 + 𝑎𝑥 1 = 𝑥
1 2 − 2𝑎𝑥 1 + 𝑎
2
𝑥 1 2 − 2𝑎𝑥 1 + 𝑏𝑥
1 − 𝑎𝑥
1 + 𝑎𝑏 − 𝑏
2 + 𝑎
2 = 0
𝑥 1 2 = (2𝑎 − 𝑏 + 𝑎)𝑥 1 + 𝑎 2 − 𝑏
2 + 𝑎𝑏 = 0 𝑥 1
= (3𝑎 − 𝑏)𝑥 1 + 𝑎 2 − 𝑏
2 + 𝑎𝑏 = 0 bu tenglamani yechib {
𝑥 1 = 𝑎 + 3 − √5 2 (𝑏 − 𝑎) 𝑥 2 = 𝑎 + √5 − 1 2 (𝑏 − 𝑎) yechimlariga ega bo’lamiz. Oltin kesmani tuzuvchi 𝑥 1 va
𝑥 2 nuqtalarini [ 𝑎, 𝑏] kesmada ketma-ket bir necha marotaba topib bu usuldan foydalanib, berilgan 𝑓(𝑥) 𝜖 𝑄[𝑎, 𝑏] funksiyaning minimum nuqtasini aniqlovchi formulani yozish mumkin. Bu formula quyidagi ko’rinishda yoziladi. Bunda 𝑎 1
1 = 𝑏 deb olinadi.
{ 𝑎 𝑛 = 𝑎 𝑛−1
, 𝑏 𝑛−1
, 𝑎𝑔𝑎𝑟 𝑓(𝑥 1 𝑛 ) ≤ 𝑓(𝑥 2 𝑛 )𝑏𝑜 ′ 𝑙𝑠𝑎, 𝑎 𝑛 = 𝑥 1 𝑛 , 𝑏 𝑛 = 𝑏
𝑛−1 𝑎𝑔𝑎𝑟 𝑓(𝑥 1 𝑛
2 𝑛 ) 𝑛 = 1,2, … , 𝑥 1 𝑛−1
, 𝑥 2 𝑛−1 , [𝑎 𝑛−1
, 𝑏 𝑛−1
] kesmani oltin kesmaga ajratuvchi nuqtalar usulni 𝑘 qadamidan so’ng 𝑥 𝑛 = 1 2 (𝑎 𝑛 + 𝑏 𝑛 ) deb qabul qilinadi. Agarda |𝑓(𝑥 𝑛 )| ≤ 𝜀 sharti bajarilsa hisoblashlar to’xtatilib 𝑥 ∗ ≈ 𝑥 ∗ , 𝑓
∗ = 𝑓(𝑥
∗ ) ≈ 𝑓(𝑥
𝑛 ) deb faraz qilinadi. Bunda olingan natijaning xatoligi quyidagicha hisoblanadi. ‖𝑥 ∗ ≤ 𝑥 𝑛 ‖ ≤ 𝜀 𝑛 = (
√𝛿 − 1 2 ) 𝑛 (𝑏 − 𝑎) (5) So’ngi (5)- formuladan foydalanib, 𝑓(𝑥) funksiyaning 𝑥𝜖[𝑎, 𝑏] kesmadagi 𝑥 ∗ 𝜖[𝑎, 𝑏] 𝜀 > 0 aniqligi bilan hisoblash uchun kerakli bo’lgan iteratsiyalarning soni
𝑛 ni hisoblash kerak bo’ladi. Buning uchun (5)- formulaning ikki tomonini ham logarifmlaymiz: ln 𝜀 𝑛
√5 − 1 2 ) + ln(𝑏 − 𝑎) ln 𝜀 𝑛 − ln(𝑏 − 𝑎) = 𝑛 ln( √5 − 1 2 ) n ≥ ln 𝜀 𝑛 𝑏 − 𝑎 / ln(
√5 − 1 2 ) = −2.1 ln( 𝜀 𝑛 𝑏 − 𝑎 ) (6)
Download 185.64 Kb. Do'stlaringiz bilan baham: 
|