O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Tekshirdi: ____________________________.
Bajardi : 0170-21 guruh talabasi
Oripov Obidjon Sobir o’g’li
Toshkent-2023 y.
TARMOQLANIVCHI ALGORITMALAR. ALGEBRAIK VA TRANSSENDENT TENGLAMALARNI TAQRIBIY YECHISH USULLARI. SAMARADORLIGINI BAHOLASH. ITERATSION SIKLLAR.
Algoritmlarni loyihalash jarayonida biz hisob-kitoblarni davom ettirish uchun ikki va undan ko'proq yo'llar mavjud bolib, ulardan birini tanlashimizga togri keladi. Hisoblah yo'lni tanlash, ma'lum shartlarni bajarilishiga bog'liq. Худди шундай шароитга biz kvadrat tenglamalarni yechish va uchburchakning yuzini hisoblashnda duch kelganmiz. Algoritmning bunday qismini shakillantirish qoidalari bilan biz ozmi-ko'pmi tanishmiz. Ushbu bo'limda takrorlanish sonlari oldindan ma'lum bolmagan takrorlanuvchi algoritmlarini tuzish usullari bilan tanishamiz. Algoritmlarni bunday turi amaliy masalalarni yechis jarayenida hosil bo'ladi.
Ma'lumki, tabiatda yoki texnikida sodir bo'ladigan jarayonlarni tavsiflovchi matematik modellar ko'pincha ushbu jarayon parametrlarini bog'lovchi tenglamalar shaklida beriladi. Agar parametrlar orasida noma'lum qiymatlilari mavjud bo'lsa, bu tenglik tenglamaga aylanadi va bu tenglamani yechish kerak bo'ladi. Ba'zan tenglamaning berilishiga qarab, yechimning analitik usullarini topish mumkin. Ammo ko'p hollarda yechimning analitik usullarini topish mumkin bo`lmay qoladi va bunday hollarda taqribiy yechish usullari qo'llaniladi. Bundayi yondoshuvni oqlaydigan yana bir holatga e'tibor qaratsak.
Ma'lumki, jarayonning fizik parametrlari qiymatlari o'lchov asboblari yordamida o'lchanadi, asboblarning aniqligi bo'linish shkalasi va asboblarning sozligiga bog'liq.Demak, o'lchov natijasida olingan qiyimatlar bilvosita chetlab bo`lmaydigan xatoliklarni o'z ichiga olishi mumkin va ular natijani aniqligiga ta'sir ko'rsatadi. Bu holda берилган тенгламанинг аниқ ечимини топиш нореал масала бўлади, чунки ечим ичида даставвал хатоликлар бор.
Агар усул ҳатолиги дастлабки маълумотлар ҳатолиги тартибига мос келса, бундай танланган усул мантиқан ўзини оқлайди. Bu fikr bizga doimo qo'llanma va dasturul amal bo'lib xizmat qiladi.
Masalaning fizik mohiyatiga qaramasdan, to'g'ridan-to'g'ri matematik masalaga o'tamiz. Quyidagi oraliqda joylashgan tenglamaning yechimini topish talab qilinadi:
(3.1)
Muayyan turdagi funktsiyalar uchun (3.1) tenglamaning aniq yechimlarini topishning analitik formulalari mavjud. Bu yerda faqat (3.1) tenglamaning ildizini har qanday oldindan aniqlangan yo`l bilan topishga imkon beradigan, funktsiya va uning oraliqlaridan qat'iy nazar, faqat universal taqribiy yechish usullarni ko'rib chiqamiz, shuningdek, ushbu usullarning barchasi aniq shaklga keltirilgan algoritmi va EXM-da osongina amalga oshiriladi.
(3.1) tenglamaning ildizlarini topish masalasi bilan shug'ullanmasdan, ya`ni bu bosqichdan o'tilgan va (3.1) tenglamaning oraliqdagi bitta ildizi topilgan deb faraz qilamiz. Biz bu ildizni aniqlik bilan tanlashmiz kerak, bu erda yetarlicha kichik va u kerakli aniqlikni ko'rsatadigan son.
Amaliy nuqtai nazardan eng sodda, keng tarqalgan usullardan biri bu oraliqlarni ikkiga bo'lish usuli. Shunday qilib, bizga (3.1) tenglama va ushbu tenglamaning bitta ildizi bo'lgan oraliq berilgan. (3.1) tenglama ildizining oraliqda bo'lishining zaruriy sharti Bu shart bizning algoritmimizni tuzishda asosiy shartlardan biri bo'ladi. Soddagina qilib algoritm g'oyasini hech qanday maxsus tushuntirishlarsiz sxematik tarzda bayon qilamiz:
Kiritish
Agar bo`lsa u xolda
Agar bo`lsa, u xolda 2 ga o`tilsin.
Chiqich
Algoritm g'oyasi shundan iboratki, oraliqni ikkiga bo'lgandan so'ng, kerakli ildiz tushgan yarmini qoldiramiz. Bundan tashqari, n qadamdan keyin biz kerakli ildizni o'z ichiga olgan oraliq uzunligini olamiz.
Agar bu oraliqning uzunligi dan kichik bo'lsa, u holda bu oraliqning istalgan nuqtasini topish kerakki, uning ildizi dan kichik bo'lsin. Shunday qilib, ushbu oraliqning o'rtasi kerakli ildizning taqribiy qiymati sifatida qabul qilinishi mumkin. Tenglikdan olinadigan aniqlikka erishish uchun zarur bo'lgan qadamlar sonini quyidagi tengsizlikdan oson hisoblab topish mumkin
(3.2)
Yuqoridagi algoritmdan foydalanib, ushbu tenglamani algoritmini amalga oshiradigan dasturini osongina tuzish mumkin. Ushbu usulning qiyinchiligi va kamchiligi - qadamlarning ko'pligi.
Algebraik tenglamalarni yechishning tejamkor usullaridan biri urinmalar usuli hisoblanadi. Ushbu usul g'oyasi quyidagi 1- rasmda sxematik tarzda ko'rsatilgan.
1.
1-rasm.
dekart koordinatalar sistemasida oraliqda funktsiya grafigini chizaylik. Funktsiya grafigidagi va nuqtalarni olib va bu nuqtalarni tutashtirib to'g'ri chiziq hosil qilamiz.
Ushbu oraliqning OX o'qi bilan kesishish nuqtasi (3.1) tenglamaning ildiziga keyingi yaqinlashishi sifatida qarash mumkin. Funksiya grafigida nuqtani belgilaymiz. OX o'qi bilan kesmasini o`tkazib, kesishish nuqtasini nuqta bilan belgilaymiz. Ushbu jarayonni davom ettirsak, asta-sekin kerakli ildizga yaqin bo`ladigan - nuqtalar ketma-ketligini olamiz. Bu nuqtalar ketma ketligidan funktsiya grafigining OX o'qi bilan kesishish nuqntasidagi ildiziga intiladi.
Rasmdan ko'rinib turibdiki, bu holda nuqta qo`zg`almas bo'lib va nuqta boshlang`ich bo`lib, ketma-ket yaqinlashtirib borildi. Ushbu usulda algoritmning aniq bir nuqtasini oldindan belgilash kerak bo'ladi. Agar oraliqlar bo'yicha shartlar bajarilsa B nuqta qo`zg`almas bo`lishini, agar bo`lsa A nuqta qo`zg`almas bo`lishini osonlikcha tekshirish mumkin.
Ushbu usul dasturini tuzishdan oldin tekshirish mumkin, ammo hamma joyda, bunday masalalarni hal qilishda ushbu ifodaning ishorasi butun oraliq davomida saqlanib qoladi va ishorani oraliqning istalgan nuqtasida tekshirib, dasturlash orqali tanlovni amalga oshirish kifoya. Yuqoridagi tushunchalardan so'ng vatarlar usuli algoritmini loyihalashtirishga kirishishimiz mumkin. Shuning uchun biz algoritmni ma'lum bir algoritmik tilga bog'lamasdan blok-sxema ravishda tasvirlaymiz:
Kirish
Agar va bo`lsa u xolda ga o`ting, aks xolda bo`lsa ga o`ting.
Agar va bo`lsa u xolda ga o`ting, aks xolda ga o`ting.
Agar va bo`lsa u xolda ga o`ting, aks xolda ga o`ting
Chiqish
Tenglamalarning yechimlarni topishning bu usulni iteratsiyalash usuli deb ataladi. Kerakli aniqlikka erishish uchun qancha takrorlanish qo'llashni oldindan bilmaymiz. Agar kerak bo'lsa, dastur matniga takrorlash sonini hisoblaydigan hisoblagichni kiritishimiz mumkin. Intuitiv va vizual ravishda, 1-rasmga ko'ra, biz ushbu usul oraliqlarni ikkiga bo'lish usulidan ancha samarali ekanligini tushunamiz.
Endi algebraik tenglamalarni yechishning yana bir usuli - Nyuton usulini ko'rib chiqamiz. Nyuton usuli ketma-ket yaqinlashish usuli bo`lib uning g'oyasi 2-rasmda keltirilgan.
2-rasm.
Nyuton usulida funktsiya oraliqda uzluksiz va hosilasi mavjud bo`lshi talab etiladi, yna shu oraliqda bo`lsin. Bu shartlarni qanoatlantiruvchi oraliqda tenglamaning qo`yilashidan u yagona yechimga ega bo`lishi kelib chiqadi.
Bu usulning g'oyasi: biz nuqtani tanlaymiz. Bu nuqtani boshlang'ich yaqinlashish nuqtasi sifatida qabul qilib, Shu nuqtada funktsiya grafigiga urinma chizamiz. Ushbu urinmaning OX o'qi bilan kesishish nuqtasi boshlang`ich yaqinlashish sifatida qabul qilamiz, xuddi shu tarzda, nuqtadan chizilgan urinmani OX o'qi bilan kesishish nuqtasi belgilanadi.
Keyingi hisoblashlar ham shunga o'xshash tarzda topilgan. Bu jarayon shart bajarilmaguncha davom etadi. Bu jarayonning yaqinlashuvchilini 2-rasmdan ko'rish mumkin. Nazariy jihatdan yaqinlashish tezligi yetarlicha yuqori ekanligini isbotlash mumkin. Bu amaliy misollar bilan tasdiqlangan. Nyuton usulining yana bir afzalligi shundaki, Nyuton usulida agar qandaydir xato qilsak, ya'ni qaysidir qadamda xato qilsak, usul bizni to'g'ri yo'lga boshlaydi.
Endi algoritmning matematik tavsifiga va hisoblash tartibiga o'tamiz. Urinmaning nuqtadagi funktsiya grafigiga o`tkazilgan urinma tenglamasi quyidagicha bo`ladi:
Urinmaning OX o'qi bilan kesishish nuqtasi: Shuning uchun qiymati uchun quyidagi formula olinadi
(3.3)
(3.3) formula keyingi yaqinlashishga o'tish uchun qaytariluvchi (рекуррент) bo`ladi. Keyingi taqribiy qiymati topish uchun har bir qadamda faqat oldingi taqribiy qiymatdan foydalanilganligi sababli, algoritmni shakllantirishda biz ushbu hisoblarni qabul qilib, algoritm matnini soddalashtirishimiz mumkin. Shunday qilib, Nyuton usulining algoritmini quyidagicha ifodalashimiz mumkin.
Kiritish
Agar bo`lsa u xolda o`ting
Chiqish
Eslatma: dasturlashda va funktsiyalarni ko`rinishini funktsiyalarni berilish qismga qoyish mumkin.
Shunday qilib, biz har qanday algebraik tenglamalarni tatbiq etiladigan universal dasturni ko`ramiz.
Xulosa qilib aytganda, Nyuton usulining imkoniyatlarini va uning samaradorligini ko'rsatish uchun bitta misol keltiramiz.
Misol. ni qiymatini 0,001 aniqlik bilan hisoblash talab etilsin. Shubhasiz, arifmetik amallarning aniq, cheklangan ketma-ketligi yo'q, ba`zi hisob kitoblardan so`ng biz taqribiy qiymatni olishimiz mumkin. Keling, ushbu ifodani tenglama ko`rinishida yozib olamiz:
uning ildizlaridan biri oraliqda joylashgan bo'lib, bu tenglavani ko`rinishda yozib, tenglamaga Nyuton usulini qo'llasak, bu holda (3.3) formula quyidagicha bo'ladi:
yoki
ushbu formuladan foydalanib qiymatini qo`yib hisob-kitoblarni amalga oshirsak, quyidagilarga ega bo`lamiz:
Agar bu natijaning qiymatini qiymat bilan taqqoslasak, farqi 0,000003 aniqiikda ekanligini ko'ramiz. Faqat uch qadamda bunday katta aniqlikka erishildi.
Xuddi shunday algoritmni har qanday darajadagi ildizlarni hisoblash uchun tuzilish mumkin. Masalan, topish uchun biz quyidagi tenglamani yechamiz:
Va bu xolda Nyuton usuli bo'yicha hisoblash formulalari quyidagicha bo'ladi:
Quyidagi misollarini 0,0001 aniqlikda taqribiy yeching: .
|
