Yarim bo'linish usuli(boshqa ismlar: biseksiya usuli, dixotomiya usuli) tenglamani yechish uchun f(x) = 0 quyidagicha bo'ladi. Funktsiya uzluksiz va segmentning uchlarini olishi ma'lum bo'lsin
[a, b] turli belgilarning qiymatlari, keyin ildiz oralig'ida joylashgan ( a, b). Keling, intervalni ikkiga bo'laylik, so'ngra biz yarmini ko'rib chiqamiz, uning oxirida funktsiya turli belgilarning qiymatlarini oladi. Biz yana ushbu yangi segmentni ikkita teng qismga ajratamiz va ildizni o'z ichiga olgan birini tanlaymiz. Bu jarayon keyingi segment uzunligi kerakli xato qiymatidan kam bo'lguncha davom etadi. Bisektsiya usuli uchun algoritmning yanada qat'iy taqdimoti:
1) Keling, hisoblaylik x = (a+ b)/2; hisoblaylik f(x);
2) Agar f(x) = 0, keyin 5-bosqichga o'ting;
3) Agar f(x)∙f(a) < 0, то b = x, aks holda a = x;
4) Agar | b – a| > e, 1-bandga o'ting;
5) Qiymatni chiqaring x;
2.4-misol. Bisektsiya usulidan foydalanib, tenglamaning ildizini aniqlang ( x– 1) 3 = 0, segmentga tegishli.
Dasturda yechim Excel:
1) Hujayralarda A 1:F 4 2.3-jadvalda ko'rsatilganidek, yozuvni, boshlang'ich qiymatlarni va formulalarni kiritamiz.
2) Har bir formulani o'ninchi qatorga qadar to'ldirish belgisi bilan pastki katakchalarga ko'chiring, ya'ni. B 4 - gacha B 10, C 4 - gacha C 10, D 3 - gacha D 10, E 4 - gacha E 10, F 3 - gacha F 10.
2.3-jadval
| A | B | C | D | E | F | |
| f(a)= | =(1-B3)^3 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,95 | =(B3+E3)/2 | =(1-C3)^3 | 1,1 | =E3-B3 | ||
| =AGAR(D3=0,C3; AGAR(C$1*D3<0;B3;C3)) | =AGAR(C$1*D3>0; E3;C3) |
Hisoblash natijalari jadvalda keltirilgan. 2.4. Ustun ichida F interval uzunligi qiymatlarini tekshirish b – a. Agar qiymat 0,01 dan kichik bo'lsa, u holda bu qatorda ko'rsatilgan xato bilan ildizning taxminiy qiymati topiladi. Kerakli aniqlikka erishish uchun 5 ta takrorlash kerak bo'ldi. Uch kasrgacha yaxlitlashdan keyin 0,01 aniqlik bilan ildizning taxminiy qiymati 1,0015625 ≈ 1,00 ni tashkil qiladi.
2.4-jadval
| A | B | C | D | E | F | |
| f(a)= | 0,000125 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,95 | 1,025 | -2E-05 | 1,1 | 0,15 | ||
| 0,95 | 0,9875 | 2E-06 | 1,025 | 0,075 | ||
| 0,9875 | 1,00625 | -2E-07 | 1,025 | 0,0375 | ||
| 0,9875 | 0,996875 | 3.1E-08 | 1,00625 | 0,0187 | ||
| 0,996875 | 1,0015625 | -4E-09 | 1,00625 | 0,0094 | ||
| 0,996875 | 0,9992188 | 4.8E-10 | 1,0015625 | 0,0047 | ||
| 0,99921875 | 1,0003906 | -6E-11 | 1,0015625 | 0,0023 | ||
| 0,99921875 | 0,9998047 | 7.5E-12 | 1,000390625 | 0,0012 |
Berilgan algoritm hisobga oladi mumkin bo'lgan holat"ildizga urish", ya'ni. tenglik f(x) keyingi bosqichda nolga teng. Agar 2.3-misolda biz segmentni olsak, birinchi qadamda biz ildizga erishamiz x= 1. Haqiqatan ham, katakka yozamiz B 3 qiymati 0,9. Keyin natijalar jadvali 2.5 shaklini oladi (faqat 2 ta takrorlash berilgan).
2.5-jadval
| A | B | C | D | E | F | |
| f(a)= | 0,001 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,9 | 1,1 | 0,2 | ||||
Keling, uni dasturda yarataylik Excel f(x) va bisect(a, b, eps) o'rnatilgan til yordamida bisect usuli yordamida tenglamalarni yechish uchun maxsus funktsiyalar Visual Basic. Ularning tavsifi quyida keltirilgan:
f funksiyasi (byval x)
Ikki qismli funktsiya (a, b, eps)
1 x = (a + b) / 2
Agar f(x) = 0 bo'lsa, 5-ga o'ting
Agar f(x) * f(a)< 0 Then
Agar Abs(a - b) > eps bo'lsa, 1-ga o'ting
f(x) funksiya aniqlaydi chap tomoni tenglamalar va funksiya
bisect(a, b, eps) tenglamaning ildizini bisekt usuli yordamida hisoblaydi f(x) = 0. E'tibor bering, bisect(a, b, eps) funksiyasi f(x) funksiyasiga kirishdan foydalanadi. Bu erda maxsus funktsiyani yaratish algoritmi:
1) Menyuning “Asboblar - Makro - Muharrir” buyrug'ini bajaring Visual Basic" oyna " Microsoft Visual Basic" Agarda bu fayl dasturlari Excel makroslar yoki foydalanuvchi funksiyalari yoki protseduralari hali yaratilmagan bo'lsa, bu oyna 2.4-rasmda ko'rsatilgandek ko'rinadi.
2) Menyuning “Vstavka - Module” buyrug‘ini bajaring va 2.5-rasmda ko‘rsatilganidek, dastur funksiyalarining matnlarini kiriting.
Endi dastur varag'i kataklarida Excel Formulalarda yaratilgan funksiyalardan foydalanishingiz mumkin. Masalan, katakka kiramiz D 18 formula
Ikki qismli(0,95;1;0,00001),
keyin biz 0,999993896 qiymatini olamiz.
Boshqa tenglamani (boshqa chap tomoni bilan) yechish uchun “Asboblar - Makro - Muharrir” buyrug'i yordamida muharrir oynasiga o'tishingiz kerak. Visual Basic” va shunchaki f(x) funksiyaning tavsifini qayta yozing. Masalan, sin5 tenglamaning ildizini 0,001 aniqlik bilan topamiz. x + x 2 – 1 = 0, intervalga tegishli (0,4; 0,5). Buning uchun funksiya tavsifini o'zgartiramiz
yangi tavsif uchun
f = Sin(5 * x) + x^2 - 1
Keyin kamerada D 18 biz 0,441009521 qiymatini olamiz (bu natijani 2.3-misolda topilgan interval ildizining qiymati (0,4; 0,5) bilan solishtiring!).
Dasturda yarimga bo'lish usuli yordamida tenglamani yechish Mathcad kichik dastur funksiyasini yaratamiz bisek(f, a, b, e), bu erda:
f- tenglamaning chap tomoniga mos keladigan funksiya nomi f(x) = 0;
a, b- segmentning chap va o'ng uchlari [ a, b];
e - ildizning taxminiy qiymatining aniqligi.
Dasturdagi misol yechimi Mathcad:
1) Dasturni ishga tushiring Mathcad. Funktsiyaning ta'rifi bilan tanishamiz bisek(f, a, b, e). Buning uchun klaviatura va “Yunoncha ramzlar” asboblar panelidan foydalanib yozing bisek(f, a, b, e):=. “Dasturlash” asboblar panelidagi “:=” topshiriq belgisidan so‘ng sichqoncha ko‘rsatkichi yordamida “Qo‘shish qatori” tugmasini sichqonchaning chap tugmasi bilan bosing. Belgilangan belgidan keyin vertikal chiziq paydo bo'ladi. Keyinchalik, pastda ko'rsatilgan dastur matnini kiriting, "Dasturlash" asboblar panelidan foydalanib, "←" belgisini, tsikl operatorini kiriting. esa, operator tanaffus va shartli operator agar boshqacha bo'lsa.
2) Funktsiyaning ta'rifini kiritamiz f(x):=sin(5*x)+x^2–1, so‘ngra funksiya yordamida ildiz qiymatini hisoblang bisek berilgan qiymatlarda:
bisek(f, –0,8,–0,7,0,0001)=. “=” belgisidan keyin dastur tomonidan hisoblangan ildiz qiymati –0.7266601563 avtomatik ravishda paydo boʻladi. Qolgan ildizlarni xuddi shu tarzda hisoblaymiz.
Quyida varaq Mathcad funktsiya ta'rifi bilan bisek(f, a, b, e) va hisob-kitoblar:
Keling, tilda dastur beraylik C++ tenglamani yechish uchun f(x) = 0 yarmiga bo'lish usuli bilan:
#o'z ichiga oladi
#o'z ichiga oladi
juft f (ikki marta x);
typedef double (*PF)(juft);
juft bisek (PF f, double a, double b, double eps);
double a, b, x, eps;PF pf;
cout<< "\n a = "; cin >>a;
cout<< "\n b = "; cin >>b;
cout<< "\n eps = "; cin >> eps;
x = bisek (pf,a,b,eps); cout<< "\n x = " << x;
cout<< "\n Press any key & Enter "; cin >>a;
juft f(ikki marta x)(
r = sin(5*x)+x*x-1;
juft bisek (PF f, double a, double b, double eps)(
do( x = (a + b)/2;
agar (f(x) == 0) uzilish;
agar (f(x)*f(a)<0) b = x;
)while (fabs(b-a) > eps);
Dasturdagi funksiya f(x) tenglamani yechish uchun aniqlanadi
gunoh5 x + x 2 – 1 = 0
2.3-misoldan. 0,00001 aniqlikdagi interval (0,4; 0,5) ildizini aniqlash dasturining natijasi quyida keltirilgan (kompyuter ekrani):
Istalgan tugmani bosing va Enter
Natijani ko'rish uchun pauzani tashkil qilish uchun oxirgi qator kerak.
Nochiziqli tenglamalarni 2 sinfga bo'lish mumkin - algebraik va transsendental. Algebraik tenglamalar faqat algebraik funksiyalarni (butun, ratsional, irratsional) o'z ichiga olgan tenglamalar deyiladi. Xususan, polinom butun algebraik funktsiyadir. Boshqa funktsiyalarni (trigonometrik, eksponensial, logarifmik va boshqalar) o'z ichiga olgan tenglamalar deyiladi. transsendental.
Nochiziqli tenglamalarni yechish usullari ikki guruhga bo'linadi:
- aniq usullar ;
- iterativ usullar .
Aniq usullar ildizlarni qandaydir chekli munosabat (formula) shaklida yozish imkonini beradi. Maktab algebrasi kursidan bunday usullar trigonometrik, logarifmik, ko'rsatkichli, shuningdek, oddiy algebraik tenglamalarni yechish uchun ma'lum.
Ma'lumki, ko'pgina tenglamalar va tenglamalar tizimlarining analitik yechimlari mavjud emas. Bu, birinchi navbatda, ko'pchilik transsendental tenglamalarga tegishli. Bundan tashqari, to'rtdan yuqori darajali ixtiyoriy algebraik tenglamani yechish uchun ishlatilishi mumkin bo'lgan formulani qurish mumkin emasligi isbotlangan. Bundan tashqari, ba'zi hollarda tenglama faqat taxminan ma'lum bo'lgan koeffitsientlarni o'z ichiga oladi va shuning uchun tenglamaning ildizlarini aniq aniqlash vazifasi o'z ma'nosini yo'qotadi. Ularni hal qilish uchun biz foydalanamiz iterativ usullar ma'lum bir aniqlik darajasi bilan.
Tenglama berilsin
- Funktsiya f(x) [ oraliqda uzluksiz a, b] uning 1 va 2-tartibli hosilalari bilan birga.
- Qiymatlar f(x) segmentning oxirida turli xil belgilar mavjud ( f(a) * f(b) < 0).
- Birinchi va ikkinchi hosilalar f"(x) Va f""(x) butun segment bo'ylab ma'lum bir belgini saqlab qoladi.
1) va 2) shartlar [ oraliqda bo'lishini kafolatlaydi. a, b] kamida bitta ildiz bor va 3) dan shundan kelib chiqadi f(x) bu intervalda monotonik va shuning uchun ildiz noyob bo'ladi.
(1) tenglamani yechish iterativ usul uning ildizlari bor yoki yo'qligini, qancha ildiz borligini aniqlash va kerakli aniqlik bilan ildizlarning qiymatlarini topishni anglatadi.
Funktsiyani o'zgartiradigan har qanday qiymat f(x) nolga, ya'ni. shu kabi:
chaqirdi ildiz tenglamalar(1) yoki nol funktsiyalari f(x).
Tenglamaning ildizini topish masalasi f(x) = 0 iterativ usulda ikki bosqichdan iborat:
- ildiz ajratish - ildiz yoki uni o'z ichiga olgan segmentning taxminiy qiymatini topish;
- taxminiy ildizlarni takomillashtirish - ularni ma'lum bir aniqlik darajasiga etkazish.
Ildizni ajratish jarayoni funktsiya belgilarini o'rnatishdan boshlanadi f(x) chegarada x=a Va x=b mavjud bo'lgan mintaqadagi nuqtalar.
1-misol . Tenglamaning ildizlarini ajrating:
|
f( x) є x 3 - 6x + 2 = 0. |
Keling, taxminiy diagramma tuzamiz:
Demak, (2) tenglama [-3, -1] va oraliqlarda joylashgan uchta haqiqiy ildizga ega.
Ildizlarning taxminiy qiymatlari ( dastlabki taxminlar) masalaning fizik ma’nosidan, o‘xshash masalani turli boshlang‘ich ma’lumotlar bilan yechishdan ham ma’lum bo‘lishi mumkin yoki grafik usulda topish mumkin.
Muhandislik amaliyotida keng tarqalgan grafik usuli taxminiy ildizlarni aniqlash.
(1) tenglamaning haqiqiy ildizlari funksiya grafigining kesishish nuqtalari ekanligini hisobga olgan holda f(x) x o'qi bilan funktsiyani chizish kifoya f(x) va kesishish nuqtalarini belgilang f(x) aks bilan Oh, yoki o'qda belgi qo'ying Oh bitta ildizni o'z ichiga olgan segmentlar. Grafiklarni qurish ko'pincha (1) tenglamani almashtirish orqali sezilarli darajada soddalashtirilishi mumkin. ekvivalent uni tenglama bilan:
(4) tenglamani tenglik sifatida qulay tarzda qayta yozish mumkin:
Bundan ko'rinib turibdiki, (4) tenglamaning ildizlarini logarifmik egri chiziqning kesishish nuqtalarining abssissalari sifatida topish mumkin. y= jurnal x va giperbolalar y = . Ushbu egri chiziqlarni tuzib, biz taxminan (4) tenglamaning yagona ildizini topamiz yoki uni o'z ichiga olgan segmentni aniqlaymiz.
Takroriy jarayon dastlabki yaqinlashuvni ketma-ket takomillashtirishdan iborat X 0 . Har bir bunday qadam deyiladi iteratsiya. Takrorlashlar natijasida taxminiy ildiz qiymatlari ketma-ketligi topiladi X 1 , X 2 , ..., xn. Agar bu qiymatlar iteratsiyalar soni ortib borayotgan bo'lsa n ildizning haqiqiy qiymatiga yaqinlashamiz, keyin biz iterativ jarayon deb aytamiz birlashadi.
[ segmentiga tegishli (1) tenglamaning ildizini topish uchun a, b], bu segmentni yarmiga bo'ling. Agar f= 0, keyin x = tenglamaning ildizidir. Agar f 0 ga teng emas (bu amalda katta ehtimolga ega), keyin biz yarmlardan birini yoki uning oxirida funksiyani tanlaymiz. f(x) qarama-qarshi belgilarga ega. Yangi toraytirilgan segment [ A 1 , b 1] yana yarmiga bo'linib, xuddi shu harakatlarni bajaring.
Yarimlar usuli berilgan tenglamaning ildizini taxminiy topish uchun amaliy jihatdan qulaydir, usul sodda va ishonchli va har doim birlashadi.
Misol 3. Tenglamaning ildizini aniqlashtirish uchun yarmiga bo'lish usulini qo'llang
f( x) = x 4 + 2 x 3 - x - 1 = 0
segmentida yotgan [0, 1] .
Doimiy ravishda bizda:
f(0) = - 1; f(1) = 1; f(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;
f (0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;
f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;
f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;
f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;
f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 va boshqalar.
Qabul qilish mumkin
x = (0,859 + 0,875) = 0,867
Ushbu usulda iteratsiya jarayoni (1) tenglamaning ildiziga yaqinlashish sifatida quyidagi qiymatlarni olishdan iborat: X 1 , X 2 , ..., x n akkordning kesishish nuqtalari AB x o'qi bilan (3-rasm). Avval akkord tenglamasini yozamiz AB:
.
Akkordning kesishish nuqtasi uchun AB x o'qi bilan ( x = x 1 ,y= 0) tenglamani olamiz:
Ishonch hosil qilaylik f""(x) > 0 da a x b(voy beradi f""(x) < Agar biz tenglamani ko'rinishida yozsak, 0 biznikiga kamayadi. f(x) = 0). Keyin egri chiziq da = f(x) pastga qarab qavariq bo'ladi va shuning uchun uning akkordi ostida joylashgan AB. Ikkita mumkin bo'lgan holatlar mavjud: 1) f(A) > 0 (3-rasm, A) va 2) f(b) < 0 (Рисунок 3, b).
3-rasm, a, b.
Birinchi holda, oxirigacha A harakatsiz va ketma-ket taxminlar: x 0 = b;x , bu yerda funksiya f (X) ikkinchi hosilasining belgisiga qarama-qarshi belgiga ega f""(X).
Takrorlash jarayoni aniqlanmaguncha davom etadi
| x i - x i - 1 |< e ,
bu erda e - belgilangan maksimal mutlaq xato.
4-misol. Tenglamaning musbat ildizini toping
f( x) = x 3 - 0,2 x 2 - 0,2 X - 1,2 = 0
e = 0,01 aniqlik bilan.
Avvalo, biz ildizni ajratamiz. Chunki
f(1) = -0,6< 0 и f (2) = 5,6 > 0,
u holda kerakli ildiz x intervalda yotadi. Olingan interval katta, shuning uchun biz uni yarmiga ajratamiz. Chunki
f (1,5) = 1,425 > 0, keyin 1< x < 1,5.
Chunki f""(x) = 6 x- 1da 0,4 > 0< X < 1,5 и f(1.5) > 0, u holda masalani hal qilish uchun (5) formuladan foydalanamiz:
= 1,15;
| x 1- x 0 | = 0,15 > e,
shuning uchun biz hisob-kitoblarni davom ettiramiz;
f ( X 1) = -0,173;
= 1,190;
|x 2- x 1 | = 0,04 > e,
f (X 2) = -0,036;
= 1,198;
| x 3- x 2 | = 0,008 < e .
Shunday qilib, biz x = 1,198 ni e = 0,01 aniqlik bilan qabul qilishimiz mumkin.
E'tibor bering, tenglamaning aniq ildizi x = 1.2.
Mayli f(x) – uzluksiz funksiya [ da a; b], .
Nyuton usuli (tangens usuli)
Mayli f(x)
oraliqda ikki marta uzluksiz differentsiallanuvchi funksiya [ a;
b],
,
Va 
belgini [ ga o'zgartirmang a;
b].
bilan belgilaymiz 
belgilar joylashgan segmentning oxiri 
Va 
mos kelish. Aniq ildizga ketma-ket yaqinlashishlar c formula bo'yicha toping
Uchun 
.
Keyin 
(1) tenglamaning aniq ildizidir.
Hisoblash jarayoni odatda qachon to'xtatiladi 
belgilangan aniqlikdan kamroq bo'lib chiqadi ε
. Biroq, bu shart belgilangan aniqlikka erishishni qat'iy kafolatlay olmaydi. To'liq ishonch uchun siz ushbu bo'lim boshida aytib o'tilganidek, aniqlikni tekshirishingiz mumkin. Agar aniqlikka erishilmasa, unda siz takrorlashni yana bir necha marta takrorlashingiz kerak.
Sekant usuli
Ba'zi bir dastlabki taxminlar bo'lsin 
. Formuladan foydalanib, biz yana bir ball olamiz 
, Qayerda h- kichik raqam. Biz usulning bir necha bosqichlarini yakunladik deb taxmin qilamiz va shu nuqtada bizda ikkita ketma-ket yaqinlashish mavjud. 
Va 
aniq ildizga (dastlabki bosqichda bu 
Va 
). Keyin formuladan foydalanib keyingi taxminiylikni topamiz
,
Jarayon Nyuton usulidagi kabi mezon bo'yicha to'xtaydi.
Takrorlash usuli
Takrorlash usulida dastlabki tenglama (1) ekvivalent tenglamaga aylantiriladi 
. Dastlabki taxminiy qiymat tanlanadi 
. Har bir keyingi yaqinlik formula bo'yicha olinadi 
,
Jarayon Nyuton usulidagi kabi mezon bo'yicha to'xtaydi. Usul birlashadi, ya'ni. chegara 
tengsizlik ildizning qo'shnisida o'rinli bo'lsa, ildizning aniq qiymatiga teng 
va dastlabki yaqinlashuv ildizga juda yaqin.
Usullarning afzalliklari va kamchiliklari
Bisektsiya usuli ildizni ajratishni talab qiladi va yuqori aniqlikka erishish uchun funktsiyani ko'p marta baholash kerak. Ushbu usulda belgilangan aniqlikka erishish kafolatlanadi.
Nyuton usuli juda tez yaqinlashuvga ega (kvadrat konvergentsiya), ya'ni.
,
Qayerda c– ildizning aniq qiymati; M– funksiyaga qarab ba’zi doimiy. Taxminan aytganda, ma'lum bir iteratsiyadan boshlab, har bir iteratsiyada to'g'ri kasrlar soni ikki baravar ko'payadi.
Nyuton usulining yaqinlashishini kafolatlash uchun bir nechta shartlar bajarilishi kerak. Umuman olganda, siz ushbu shartlarni tekshirmasdan Nyuton usuli yordamida hisob-kitoblarni boshlashingiz mumkin, ammo keyin konvergentsiya kuzatilmasligi mumkin.
Sekant usuli silliq funksiyalar uchun Nyuton usulining yaqinlashuv tezligiga yaqin yaqinlashuv tezligini ta'minlaydi. Bu funktsiyaning hosilasini hisoblashni talab qilmaydi. Agar boshlang'ich nuqta ildizdan uzoqda olingan bo'lsa, unda hech qanday yaqinlashuv bo'lmasligi mumkin.
Iteratsiya usuli Nyuton usulidan ancha past yaqinlashuv tezligini beradi. Agar yaqinlashuv mavjud bo'lsa, taxmin qo'llaniladi 
, Qayerda 
- raqamlar, 
,
;c- ildizning aniq qiymati. Miqdorlar M,
q funktsiyaga bog'liq va iteratsiya soniga bog'liq emas. Agar 
u holda 1 ga yaqin q ham 1 ga yaqin va usulning yaqinlashuvi sekin bo'ladi. Takrorlash usuli yordamida hisoblashni shartlarni tekshirmasdan boshlash mumkin 
Va 
. Bunday holda, jarayon turlicha bo'lishi mumkin, keyin esa javob olinmaydi.
Nochiziqli tenglamaning ildizlarini topish uchun sanab o'tilganlardan tashqari ko'plab usullar mavjud. MATHCAD da ildiz funksiyasi formatda 
sekant usulidan foydalanadi va agar u kerakli natijaga olib kelmasa, Myuller usuli. Ikkinchisida, sekant usulidan farqli o'laroq, har bir qadamda ikkita qo'shimcha nuqta olinadi, funksiya grafigi uch nuqtadan o'tuvchi parabola bilan almashtiriladi va parabolaning o'q bilan kesishish nuqtasi sifatida qabul qilinadi. keyingi taxminiy ho'kiz. Root formatidagi ildiz funksiyasida root( f(x),
x,
a,
b) Ridder va Brent usullari qo'llaniladi. MATHCAD da ko‘phadning ildizlarini topish uchun Lager usuli qo‘llaniladi.
Dixotomiya usuli o'z nomini qadimgi yunoncha so'zdan olgan bo'lib, tarjimada ikkiga bo'lish ma'nosini bildiradi. Shuning uchun bu usulning ikkinchi nomi ham bor: yarimlar usuli. Biz undan tez-tez foydalanamiz. Aytaylik, "Raqamni toping" o'yinini o'ynaymiz, bunda bir o'yinchi 1 dan 100 gacha bo'lgan raqamni taxmin qiladi, ikkinchisi esa "ko'proq" yoki "kamroq" ko'rsatmalariga asoslanib, uni taxmin qilishga harakat qiladi. Birinchi raqam 50, ikkinchisi kamroq bo'lsa - 25, ko'p bo'lsa - 75 deb nomlanishi mantiqan to'g'ri keladi. Shunday qilib, har bir bosqichda (iteratsiya) noma'lumning noaniqligi 2 barobar kamayadi. Bular. hatto dunyodagi eng omadsiz odam ham bu diapazondagi yashirin raqamni 100 ta tasodifiy gap o'rniga 7 ta taxminda topadi.
Tenglamani yechishda yarimga bo'lish usuli
Yarimlar usuli yordamida tenglamani to‘g‘ri yechish faqat ma’lum oraliqda ildiz borligi ma’lum bo‘lsa va u yagona bo‘lsagina mumkin bo‘ladi. Bu dixotomiya usuli faqat chiziqli tenglamalarni yechish uchun ishlatilishi mumkin degani emas. Yuqori tartibli tenglamalarning ildizlarini ikkiga bo‘lish usuli yordamida topish uchun avvalo ildizlarni segmentlarga ajratish kerak. Ildizlarni ajratish jarayoni funksiyaning birinchi va ikkinchi hosilalarini topib, ularni f"(x)=0 va f""(x)=0 ga tenglashtirish orqali amalga oshiriladi. Keyin f(x) ning belgilari. kritik va chegara nuqtalarida funksiya |a,b| belgisini o'zgartiradigan interval aniqlanadi, bu erda f(a)*f(b).< 0.
Dixotomiya usulining algoritmi
Dixotomiya usulining algoritmi juda oddiy. |a,b| segmentini ko'rib chiqing uning ichida bitta ildiz x 1 mavjud
Birinchi bosqichda x 0 =(a+b)/2 hisoblanadi
Keyinchalik, funktsiyaning ushbu nuqtadagi qiymati aniqlanadi: agar f(x 0) bo'lsa.< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.
b-a farqi talab qilingan xatodan kam bo'lganda hisob-kitoblar to'xtaydi.
Yarimga bo'lish usulini qo'llash misolida 10 -3 aniqlikdagi x 3 -3*x+1=0 tenglama oralig'idagi ildizni topamiz.
Jadvaldan ko'rinib turibdiki, ildiz 0,347 ni tashkil qiladi. Takrorlashlar soni 10. Tugallanish sharti: a-b=0,0009< 10 -3
Yarimlar usuli yoki dixotomiya usuli tenglamani raqamli usullar yordamida yechish uchun eng oddiy hisoblanadi.
Yuklab oling:
Tenglamani dixotomiya usuli yordamida yechish - Paskalda ikkiga bo'linish usuli yordamida tenglamani yechish.
U dixotomiya usuli deb ham ataladi. Tenglamalarni yechishning bu usuli yuqorida ko’rib chiqilgan usullardan birinchi va ikkinchi hosilalar intervalda o’z belgisini saqlab qolish shartining bajarilishini talab qilmasligi bilan farq qiladi. Bisektsiya usuli har qanday uzluksiz f(x), shu jumladan differensiallanmaydigan funksiyalar uchun yaqinlashadi.
Segmentni nuqta bilan yarmiga bo'ling. Agar (bu amalda eng katta ehtimol bo'lsa), unda ikkita holat mumkin: yoki f(x) segmentdagi belgini o'zgartiradi (3.8-rasm), yoki segmentda (3.9-rasm).
Har bir holatda funktsiya belgisini o'zgartiradigan segmentni tanlab, yarimga bo'lish jarayonini davom ettirib, tenglamaning ildizini o'z ichiga olgan ixtiyoriy kichik segmentga erishish mumkin.
4-misol. 5x - 6x -3 = 0 tenglama oraliqda bitta ildizga ega. Ushbu tenglamani yarimga bo'lish usuli yordamida yeching.
Yechim: Paskal dasturi quyidagicha ko'rinishi mumkin:
f(x: real): real;
f:=exp(x*ln(5))-6*x-3;
a, b, e, c, x: haqiqiy;
esa abs(b-a)>e qiladi
agar f(a)*f(c)<0 then
writeln("x=",x:3:3," f(x)=",f(x):4:4);
Dasturni bajarish natijasi:
e=0,001 x=1,562 f(x)=-0,0047
20. Yarimlarga bo'lish usuli algoritmi.
1.Yangi ildiz yaqinligini aniqlang X segmentning o'rtasida [a,b]: x=(a+b)/2.
2. Funktsiyaning nuqtalardagi qiymatlarini toping A Va X: F(a) Va F(x).
3. Vaziyatni tekshiring F(a)*F(x)< 0 . Agar shart bajarilsa, ildiz segmentda joylashgan [Oh] b nuqtaga o'ting x (b=x). Agar shart bajarilmasa, ildiz segmentda joylashgan [x,b]. Bunday holda, sizga nuqta kerak A nuqtaga o'ting x (a=x).
4.1-bosqichga o'ting va segmentni yana yarmiga bo'ling. Algoritm shart bajarilgunga qadar davom etadi /F(x)/< e (belgilangan aniqlik).
21. Ildizlarni topishning oddiy takrorlash usuli. Geometrik talqin.
Dastlabki f(x)=0 tenglama chap tomonda noma’lum tanlangan shaklga ekvivalent o‘zgartirishlar yo‘li bilan qisqartiriladi, ya’ni x=ph(x), bunda ph(x) asl f funksiyasi bilan bog‘langan ba’zi funksiyadir. (x). Tenglamani yozishning bu shakli dastlabki x 0 yaqinlashuvini hisobga olgan holda keyingi, birinchi x 1 =ph(x 0) yaqinlashuvini, so‘ngra ikkinchi x 2 =ph(x 1) va hokazo x n +1 ni olish imkonini beradi. =ph(x n)… . Ketma-ket (x n )= x 0, x 1, x 2, …, x n,… boshlang‘ich qiymati x 0 bo‘lgan takrorlashlar yoki yaqinlashishlar ketma-ketligi deyiladi. Agar ph(x) funksiya uzluksiz bo‘lmasa va chegara mavjud bo‘lsa. p = lim x n n→∞ sifatida, u holda x n +1 =ph(x n) tenglikda chegaraga o‘tsak, n→ ∞ sifatida topamiz: lim x n +1 =lim ph(x n)=ph(lim x n) ), ya'ni, p=ph(p) Demak, agar yaqinlashishlar ketma-ketligi yaqinlashsa, u (2) tenglamaning ildiziga yaqinlashadi, demak, tenglama (1). Iteratsion jarayonning yaqinlashishi tufayli bu ildizni etarlicha katta hisoblash mumkin n har qanday aniqlik bilan. Biroq, ketma-ketlik (x n) qanday sharoitlarda yaqinlashishini aniqlash kerak. Ikki qo'shni yaqinlashish - e n va e n +1 xatoliklari orasidagi bog'lanishni olaylik: x n =p+e n, x n +1 =p+e n +1. Bu tasvirlarni x n +1 =ph(x n) ga almashtiramiz va funktsiyani ildiz yaqinidagi Teylor qatoriga kengaytiramiz:p+e n +1 =ph(l+e n)=ph(p)+e n. ph'(p)+ (e n 2 /2!)ph''(ē), bu erda ē O [l; p+e n ] M , chunki p ildiz bo‘lsa, u holda p=ph(p) ni olamiz: e n +1 =e n ph'(l)+(ph''(ķ)/2)e n 2. dan beri<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n|e n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.
Oddiy takrorlash usulining yaqinlashuvi haqidagi teorema. x=ph(x) tenglamaning ildizi p bo‘lsin, ph(x) funksiya aniqlangan va intervalda differentsiallanadi, x O uchun esa ph (x) O funksiyaning barcha qiymatlari. U holda, agar shunday musbat son q bo'lsa<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>ph'(x)>-1 bo'lsa, u holda qo'shni yaqinlashishlar ildizning qarama-qarshi tomonlarida yotadi - bunday yaqinlashish ikki tomonlama (yoki spiral) deb ataladi - 2-rasm. Chunki bu holda ildiz oraliqda joylashgan bo'lib, uning uchlari qo'shni yaqinlashishlar – pÎ(x n ,x n +1), keyin shartning bajarilishi |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.
Iterativ usullarni konvergentsiya tezligi nuqtai nazaridan solishtirish uchun quyidagi tushunchalar kiritiladi:
Ta'rif 1: Ketma-ketlikning (x n) p ga yaqinlashishi deyiladi chiziqli(mos ravishda, iterativ jarayon chiziqli konvergent), agar doimiy CO(0,1) va n 0 soni bo'lsa, tengsizliklar |p-x n +1 |≤C|l-x n | n≥n 0 uchun.
Ilgari kiritilgan xatolar uchun bu |e n+1 |≤C|e n |ni bildiradi. Oddiy takrorlash usulida C doimiysi q qiymatdir, ya'ni usul chiziqli yaqinlashadi.
Ta'rif 2: Taxminlovchilar ketma-ketligi (x n ) kamida bilan p ga yaqinlashadi R th tartib (mos ravishda, iterativ jarayon hech bo'lmaganda p-chi tartib), agar shunday konstantalar C>0 bo'lsa, p≥1 va n 0 , barcha n≥n 0 uchun shartlar |l-x n +1 |≤C|l-x n | p (yoki boshqa belgilarda |e n+1 |≤C|e n | p).
