Ishdan maqsad: Talabalarda algoritmlarni asimptotik tahlil qilish haqida ko’nikmalar hosil



Yüklə 1,47 Mb.
Pdf görüntüsü
səhifə4/6
tarix29.07.2023
ölçüsü1,47 Mb.
#137872
1   2   3   4   5   6
alg
Summa (
but
N, 
haqjad
A[1:N],
haq
S) 
arg
N,A 
boshlbut

S:=0 
sb

uchun

dan

gacha
S := S + A[i] 
so
tamom
 
Blok sxemasi: 
 
Quyidagi yig’indini hisoblovchi dastur tuzing.
𝑓(𝑥) = ∑
1
𝑖
50
𝑖=1
𝑆 = 1 +
1
2
+
1
3
+. . . +
1
50
//’Takrorlanuvchi operatori’ 
#include  
#include  
using namespace std; 
int main () 

float S=0; 
for (float i = 1; i <=50; i++) 
s+=1/i; 
cout <return 0; 

 
1.1. Taqribiy integrallash usullari. Zaruriy aniqlikni ta’minlovchi qadamni tanlash. 
Ma’lumki, agar integral osti funksiyasi
𝑓(𝑥)
ning boshlang’ich funksiyasi
𝐹(𝑥)
ni topish 
mumkin bo’lmasa aniq integralni hisoblashda Nyuton-Leybnits formulasi 
∫ 𝑓(𝑥)
𝑏
𝑎
𝑑𝑥 = 𝐹(𝑏) − 𝐹(𝑎)
(1.1) 
ni tadbiq qilib bo’lmaydi. Bunday hollarda (1.1) aniq integralning geometrik ma’nosi, ya’ni
𝑦 =
𝑓(𝑥)
funksiya grafigi bilan chegaralangan egri chiziqli trapetsiya yuzasini taqribiy hisoblashga 
asoslangan sonli usullarga murojaat qilinadi. Bunday usullar ko’p. Biz bu yerda ulardan faqat 
ikkitasida to’xtalamiz. 


1-rasm. 
1-rasmda berilgan ABCD egri chiziqli trapetsiya yuzasi (1.1) formula bo’yicha 
hisoblangan aniq integral qiymatiga teng. Shuning uchun integralni (1.1) formula bo’yicha 
hisoblashning iloji bo’lmasa ABCD trapetsiya yuzasini hisoblashga o’tamiz. Buning uchun (
a,b
)
oraliqni
n=2m
juft bo’laklarga bo’lamiz. Bo’linish nuqtalari
𝑥
𝑖
= 𝑎 + 𝑖ℎ ;
𝑖 = 0,1,2 … , 𝑛 ;
𝑥
𝑛
= 𝑎 + 𝑛 ∙ ℎ = 𝑏 ℎ =
𝑏−𝑎
𝑛
Simpson formulasiga ko’ra
∫ 𝑓(𝑥)𝑑𝑥 ≈

3
∙ ∑
(𝑓
2𝑖−2
+ 4𝑓
2𝑖−1
+ 𝑓
2𝑖
)
𝑚
𝑖=1
𝑏
𝑎
(1.2) 
(1.2) formulani yoyib yozib yuborsak 
∫ 𝑓(𝑥)𝑑𝑥 ≈

3
∙ (𝑓
0
+ 4𝑓
1
+ 2𝑓
2
+ 4𝑓
3
+ 2𝑓
4
+ ⋯ + 4𝑓
2𝑚−1
+ 𝑓
2𝑚
)
𝑏
𝑎
(1.3) 
formulani hosil qilamiz. (1.3) formula taqribiy formula bo’lib uning xatoligi
𝑂(ℎ
4
)
tartibida 
bo’lar ekan. Bu degani, (1.3) Simpson formulasi sodda lekin ancha aniq formulalardan ekan. 
Amaliyotda bu formula juda keng qo’llaniladi. Uni dasturlash ham oson. 
Monte-Karlo usuli esa ehtimolning geometrik va statistik ta’riflarini muvofiqlashtirishdan 
kelib chiqqan. Buning uchun
y=f(x)
funksiyani yuqori chegarasi
|𝑓(𝑥)| < 𝑀, 𝑎 ≤ 𝑥 ≤ 𝑏
topiladi. 
Chizma 
 
2-rasm. 
2-rasmdagidek xolat o’rinli bo’lsin, ya’ni 


𝑓(𝑥) ≤ 𝑓(𝑏)
𝑚𝑎𝑥
𝑎 ≤ 𝑥 ≤ 𝑏
𝑓(𝑥) = 𝑓(𝑏) = 𝑀.
U xolda
𝑆
𝐴𝐵𝐶𝐸
= 𝑀 ∙ (𝑏 − 𝑎),
𝑆
𝐴𝐵𝐶𝐷
= ∫ 𝑓(𝑥)𝑑𝑥
𝑏
𝑎
.
Ikkinchi tarafdan ehtimolning geometrik ta’rifiga ko’ra ABCE to’g’ri to’rtburchakka 
tavakkaliga tashlanadigan tasodifiy nuqta ABCD egri chiziqli trapetsiyaga tushish ehtimoli 
𝑃(𝐴) =
𝑆
𝐴𝐵𝐶𝐷
𝑆
𝐴𝐵𝐶𝐸
=
∫ 𝑓(𝑥)𝑑𝑥
𝑏
𝑎
𝑆
𝐴𝐵𝐶𝐸
∫ 𝑓(𝑥)𝑑𝑥
𝑏
𝑎
= 𝑃(𝐴) ∙ 𝑆
𝐴𝐵𝐶𝐸
(1.4) 
Agar A – tasodifiy hodisa ABCE to’g’ri to’rtburchakka tavakkaliga tashlangan nuqtaning 
ABCD egri chiziqli trapetsiyaga tushishi deb qaralsa, bu xodisaning ehtimolini hisoblash uchun 
ehtimolning statistik ta’rifidan foydalanamiz. Buning uchun
[𝑎, 𝑏]
oraliqda tekis taqsimlangan
𝑥
𝑖
tasodifiy miqdorlar va
[𝑜; 𝑀]
oraliqda tekis taqsimlangan
𝑦
𝑖
tasodifiy miqdorlar ketma-
ketligini tuzamiz. Buning uchun kompyuterda mavjud bo’lgan psevdotasodifiy miqdorlar 
generatoridan foydalanish mumkin. Hosil bo’lgan bu ketma-ketlikning har bir juftligi
(𝑥
𝑖
, 𝑦
𝑖
) , 𝑖 = 1,2, … , 𝑛
, ABCE to’g’ri to’rtburchakka taaluqli bo’ladi. Ulardan ABCD 
trapetsiyaga taaluqlilarini ajratamiz. Buning uchun
𝑦
𝑖
≤ 𝑓(𝑥
𝑖
)
shart bajarilishi kerak. Bunday 
nuqtalar soni
m
ta bo’lsin. U holda
A –
hodisa ehtimoli uchun 
𝑃(𝐴) ≈
𝑚
𝑛
(1.5) 
formuladan foydalanish mumkin. 
n – 
qanchalik katta bo’lsa (1.5) formula shunchalik aniq bo’ladi. 
(1.5) formuladan topilgan qiymatni (1.4) formulaga olib borib qo’yilsa 
∫ 𝑓(𝑥)𝑑𝑥
𝑏
𝑎

𝑚
𝑛
∙ 𝑆
𝐴𝐵𝐶𝐸
=
𝑚
𝑛
∙ 𝑀 ∙ (𝑏 − 𝑎)
(1.6) 
formula hosil bo’ladi. Integralni bu usulda hisoblash Monte-Karlo usuli deyiladi. 
Misol:
f
(
x
) = 4 
sin
(
x
) funksiyani Simpson usulidan foydalanib [0; 3] oraliqda integrali 
hisoblansin. 

Yüklə 1,47 Mb.

Dostları ilə paylaş:
1   2   3   4   5   6




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin