O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
KOMPYUTER INJINIRINGI FAKULTETI
KI-17-21 (S) GURUH TALABASINING
ALGORITMLARNI LOYIHALASH
FANIDAN
3–MUSTAQIL ISHI
Bajardi: Nasimov O
Qabul qildi: Begulov O.U
Reja:
1 .P va NP sinflar, NP- to’liq masalalar tushunchasi, Algoritmlarni baholash mezonlari.
2.Vaqt va hajm bo’yicha baholashga misollar.
3. Integrallarni taqribiy hisoblashda Nyuton-Kotes formulalari. G’oyalari va hatolik tartibi
4 .Integrallarni taqribiy hisoblashda Gauss formulalari
5.Algebraik va transsendent tenglamalarni taqribiy yechishda vatarlar va Nyuton usullarini samaradorlik bo’yicha taqqoshlash.
Aniq integralni taqribiy hisoblash
Quyidagi
b
I f f x dx
a
aniq integralning qiymatini taqribiy hisoblashni qaraylik. Bu erda
a, b oraliqda uzluksiz.
f x
(1)
funksiya
Berilgan funksiyani a, b oralig’ini n ta uzunligi
h b a
n
ga teng bo’lgan
x0, x1,x1, x2 ,.....,xn1, xn kesmalarga ajratamiz.
b
y0
yn
I f f
a
x dx h
2
y1 y2 ...... yn1 2
(2)
hosil qilmiz. Ushbu (2) formula umumiy trapetsiyalar formulasi deyiladi. Bu
formula geometrik nuqtai-nazardan integral ostidagi y f x funktsiyaning
grafigini tugun nuqtalarni tutashtiruvchi siniq chiziq bilan almashtirishdan iboratdir.
Faraz qilaylik
n 2m
juft son bo’lsin. a, b
integrallash oralig’ini n ta
uzunligi
h b a b a
ga teng bo’lgan x , x ,x , x
,.....,x , x
kesmalarga
n 2m
0 1 1 2
n1 n
ajratamiz. Berilgan funksiyani har bir kesmasini parabolik funksiya bilan almashtirsak
b h
3
I f f x dx y0 y2m 4 y1 y3 y2m1
a
2 y2 y4 ...... y2m2
bo’ladi. Keltirilgan (3) formula Simpson (parabolalar) formulasi deyiladi.
(3)
y f x
funktsiyaning grafigini har bir oraliqda parabolalar bilan
almashtirishdan iboratdir.
Aniq integralni taqribiy hisoblash usullari
h
Nyuton-Kotes formulalari J NK ( f ) .
J ( f ) int( f , a,b)) integralni hisoblash uchun Lagranj interpolyatsion ko’phadi
formulasidan foydalanamiz:
h n
J NK ( f ) J ( L ( f ; x))
b
b
Ln ( f ; x) dx a
n n
f ( xi ) li ( x) dx f ( xi ) pi
(1)
bu yerda
a
b
p l (x)dx
i0
b x xj dx
i0
(2)
i a i
a ji xi xj
xi1 - xi h , hol uchun Nyuton - Kotes formulasi deyiladi, (2) Nyuton -
Kotes koeffitsientlari deyiladi. (2) da x x th almashtirishni bajarsak
dx hdt, x t, a 0,b n, h (b - a)/ n va
p b a n (1)ni t( t 1)...( t n) dt
(3)
i n 0
i!(n i)!(t i)
ko’rinishni hosil qilamiz. (3) ni hosil qilishda
x - xj ( t - j) h, xi - xj
(i - j)h
tengliklardan foydalandik.
To’g’ri to’rtburchaklar formulasi
h
J TT ( f ) .
Kvadratura formulasi (integral yig’indi)
b n
J ( f ) a
f (x)dx
pif(i )
i=0
(4)
da i xi h / 2,
pi h,
i 0, 1, ..., n 1
deb ushbu markaziy to’g’ri to’rtburchaklar
formulasi
J TT ( f )
ga kelamiz:
h
n1 n1
h i i 0.5
J TT ( f ) h f (x h / 2) h f .
i0 i0
Markaziy to’g’ri to’rtburchaklar formulasida egri chiziqli trapetsiya yuzi chizmada
ko’rsatilgan asoslari h va
f ( xi h / 2)
ga teng to’g’ri to’rtburchak yuzalarining
yig’indisi JhTT(f) ga almashtirilmoqda.
h
Trapetsiya formulasi JT ( f ) .
Kvadratura formulasidai xi , p0 pn h / 2, pi h,i 1,..., n 1deb olamiz
n1
JT ( f )
fi fi1 h h {f +2(f +...+f )+f }
(5)
h
i0
2 2 0 1 n-1 n
formula trapetsiya formulasi deyiladi. Trapetsiya formulasida egri chiziqli trapetsiya yuzi chizmada ko’rsatilgan asoslari fi, fi+1, h balandlikka ega trapetsiyalar yuzalarining yig’indisi JhT(f) bilan almashtirilmoqda.
h
Simpson formulasi JC ( f ) .
J ( f )
integralni taqribiy hisoblash uchun {(xi , f (xi )), i 0,1,..., 2n} jadval olib
xar bir [x2i , x2i2 ] {i 0,1,..., 2n - 2 } kesmada Nyutonning ikkinchi darajali ko’pxadini
quramiz. Bu funktsiyalar
[x0 ; x2n ]
kesmada uzluksiz ikkinchi darajali (parabolik)
interpolyatsiya splayni S( f , x) ni tashqil qiladi.
f (x2i ) (x - x2i ) f [x2i , x2i1]
S ( f , x) (x - x )(x - x ) f [x , x , x ]
(6)
2i
2i1 2i 2i1 2i2
x x x
, i 0.1,..., n -1
h
2i
2i 2
so’ng
J ( f ) J ( S) JC ( f )
deb qabul qilamiz va
JC ( f )
ni Simpson formulasi deb
h
ataymiz. Ravshanki,
C
n1
x2i2
h n1
Jh ( f )
i0
x2 i
L2,i ( f ; x)dx
[ f2i 4 f2i1 f2i2 ]
3
i0
h { f 4( f ... f ) 2( f ... f ) f }
3 0 1 2m1 2 2m2 2m
Oraliq natija quyidagicha yaratiladi. interpolyatsiya ko’phadini integrallaymiz.
[x0 , x2 ]
kesmada Nyutonning 2-darajali
Lemma 1. Ushbu sodda Simpson formulasi o’rinli:
x2
2 0 1 2 h 2
N (x)dx h( f 4 f f ) / 3 J C (N ).
x0
Isbot.
a0 f0 , a1 f [x0 , x1], a2 f [x0 , x1, x2 ] deb quyidagilarni olamiz:
x2 x2
2
0 1 0 2 0 1 0 1 2
N ( x) dx ( a
0 1 2 h 2
x0 x0
a (x x ) a (x x )(x x )dx 2ha
2 a h2 2 a h3 / 3
2
2hf0 2h
3
h
2
( f1 f0 ) / h 2 3 ( f0 2 f1 f2 ) / 2h
h( f 4 f f ) / 3 J C (N ).
Lemma 2.
rC ( f ) f (x) JC ( f )
desak
rC (x ) 0, 0,1, 2,3 .
h h
h
Isbot. 0,1, 2 hollar ravshan, 3 hol elementar ko’rsatiladi:
1 ( x
x x 1
( x2 x2 ) 3
rC (x3)
(x4 x4) 2 0 [x3 4( 0 2 )3 x3]
(x4 x4) 2 0 [x2 x2] 0
h 4 2 0 6 0 2
2 4 2 0
6 2 0 2
|