Tarmoqlanivchi algoritmalar. Algebraik va transsendent tenglamalarni taqribiy yechish usullari. Samaradorligini baholash. Iteratsion sikllar

3 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. Xuddi shunday sharoitga 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 yechish jarayonida 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 berilgan tenglamaning aniq yechimini topish noreal masala bo`ladi, chunki yechim ichida dastavval xatoliklar bor.
Agar usul xatoligi dastlabki ma`lumotlar xatoligi tartibiga mos kelsa, bunday tanlangan usul mantiqan o`zini oqlaydi. Bu fikr bizga doimo qo'llanma va dasturul amal bo'lib xizmat qiladi.
Masalaning fizik tomoniga qaramasdan, to'g'ridan-to'g'ri matematik masalani ko'rib chiqamiz. Quyidagi tenglamaning oraliqdagi yechimini topish talab qilinadi:
(3.1)
Bu ko`rinishdagi funktsiyalar uchun (3.1) tenglamaning aniq yechimlarini topishning analitik formulalari mavjud. Buning uchun (3.1) tenglamaning ildizini har qanday oldindan aniqlangan yo`l bilan topishga imkon beradigan, funktsiya va uning oraliqdagi, faqat taqribiy yechimlarining universal usulini ko'rib chiqamiz, shuningdek, ushbu usul algoritmlarini aniq keltirib va EXM-da osongina amalga oshiramiz.
(3.1) tenglamaning ildizlarini ajratib otirmasdan, tenglamani oraliqda topilgan bitta ildizini tanlab olamiz va keyigi bosqichga o`tamiz. Biz bu tenglama ildiznini kerakli aniqlikda yetarlicha kichik son uchun, tanlashmiz kerak.
Endi biz sodda, keng tarqalgan usullardan biri, oraliqlarni ikkiga bo'lish usuli bilan tanishamiz. Shunday qilib, bizga (3.1) tenglama va bu tenglamaning oraliqqa tegishli bitta ildizi berilgan bo`lsin. (3.1) tenglama ildizining oraliqqa tegishli bo'lishining zaruriy sharti Bu algoritmni tuzishda asosiy shartlardan biri bo'ladi. Soddagina qilib algoritmni quyidagicha maxsus tushuntirishlarsiz sxematik tarzda keltiramiz:

1. 
   Kiritish
   
2. 
   
   
3. 
   Agar bo`lsa u xolda
   
4. 
   Agar bo`lsa, u xolda 2 ga o`tilsin.
   
5. 
   
   
6. 
   Chiqich
   

Algoritmning g'oyasi shundan iboratki, oraliqni ikkiga bo'lib so'ngra, kerakli ildiz tushgan yarmini olamiz. Bu usulni davom ettirib, 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 mumkunki, uning ildizi dan kichik bo'lsin. Shunday qilib, ushbu oraliqning o'rtasini kerakli ildizning taqribiy qiymati sifatida tanlaymiz. Quyidagi tengsizlikdan aniqlikka erishish uchun zarur bo'lgan qadamlar sonini oson hisoblab topish mumkin,
(3.2)
Yuqoridagi algoritmdan foydalanib, ushbu tenglama dasturi algoritmini osongina amalga oshirishimiz mumkin. Qadamlarining ko`pligi ushbu usulning qiyinchiligi va kamchiligini bildiradi.
Algebraik tenglamalarni yechishning tejamkor usullaridan biri vatarlar usuli hisoblanadi. Ushbu usul ko'rinishi 1- rasmda sxematik tarzda ko'rsatilgan.
1.