|
Kesmani teng ikkiga bo‘lish usuli (dixotomiya usuli).
Bu usul
f
(
x
) funksiya
haqida ma’lumotlar juda ham kam bo‘lganda foydalanishga qulay. Faraz qilaylik,
f
(
x
)
funksiya (
a
,
b
) intervalning qaysidir bir nuqtasida nolga aylanishini aniqladik, bunda
ildizdan chaproqda
f
(
x
)<0 va o‘ngroqda esa
f
(
x
)>0. Bunday holda izlanayotgan ildizni
66
topish murakkab bo‘lmaydi. Kesmani teng ikkiga bo‘lamiz va hosil bo‘lgan
x
i
nuqtada funksiyaning ishoraini qaraymiz. Agar
f
(
x
i
)>0 bo‘lsa, yuqori chegarani
b = x
i
deb, aksincha esa quyi chegarani
a = x
i
deb siljitamiz va hokazo (2.12-rasm).
Bularni quyidagicha ham ifodalash mumkin:
Faraz qilaylik,
f
(
a
)
f
(
b
) < 0.
a
0
=
a
va
b
0
=
b
deb belgilash kiritamiz. U holda
ketma–ket yaqinlashish quyidagicha:
.
0
)
(
)
(
agar
,
,
,
0
)
(
)
(
agar
,
,
,
...;
,
2
,
1
,
2
1
1
1
1
1
1
1
1
n
n
n
n
n
n
n
n
n
n
n
n
n
n
b
f
c
f
b
c
c
f
a
f
c
a
b
a
n
a
b
a
x
.
0
)
(
)
(
agar
,
,
,
0
)
(
)
(
agar
,
,
,
1
1
1
1
1
1
n
n
n
n
n
n
n
n
n
n
b
f
x
f
b
x
x
f
a
f
x
a
b
a
Bu jarayon
f
(
x
n
+1
) = 0 bo‘lganda to‘xtatiladi va
x
=
x
n
+1
deb qabul qilinadi.
2.12–rasm. Kesmani ikkiga bo‘lish usulining sxematik tasviri.
Bu usul
kesmani teng ikkiga bo‘lish usuli
,
dixotomiya usuli
(grekchadan
–
ikki qismga
– kesish),
biseksiyalar usuli
yoki
vilka usuli
deb ataladi.
Agar tenglamaning qolgan ildizlarini ham aniqlash zarurati tug‘ilsa, u holda
g
(
x
)
=
f
(
x
)/(
x –
x
) tenglikdan ketma-ket foydalanib, har safar topilgan
x
ildiz chiqarib
tashlanadi (endi
g
(
x
) = 0 va
f
(
x
) = 0 tenglamalarning
x
(bu nuqta
g
(
x
) funksiya uchun
qutb,
f
(
x
) funksiya uchun esa ildiz) dan boshqa barcha ildizlari mos keladi).
Talab qilingan aniqlikdagi yechimga erishish uchun avvalo
g
(
x
) funksiyaning
ildizi qo‘pol holda bo‘lsa ham topiladi, keyin esa bu ildiz
f
(
x
) funksiyadan foydalanib
aniqlashtiriladi.
Bu usul uchun
hisob tugashining kriteriyasi
ushbu
x
n
+1
–
x
x
n
+1
–
x
n
1
2
n
a
b
< ε
shartning bajarilishidan iborat, bunda ε – berilgan absolyut aniqlik.
Bu baholash
usulning xatoligini
anglatadi va u
xatolikning aprior bahosi
deb
ham ataladi. Bu
usulning yaqinlashish tartibi
1
ga teng
, ya’ni bu
usul chiziqli yaqin-
67
lashish tezligiga ega
. {
x
n
} ketma-ketlik maxraji 1/2 ga teng bo‘lgan geometrik pro-
gressiya tezligi bilan ildizga yaqinlashadi.
Bundan kelib chiqadiki, berilgan
ε
aniqlik bilan ildizni hisoblash uchun zarur
bo‘lgan
N
– iteratsiyalar soni qiyidagi tengsizlikdan aniqlanadi:
N
a
b
2
yoki
2
ln
ln
)
ln(
yoki
a
b
N
a
b
N
2
log
.
Usulning qulayliklari:
f
(
x
) funksiya haqida ma’lumotlar kam bo‘lganda ham undan foydalanish juda
qulay;
bu usul algoritmi juda sekin, ammo barcha noqulayliklardan holi.
Usulning kamchiliklari:
ko‘p hollarda funksiyaning holati juda murakkab bo‘lib, bu chetki nuqtalarida
funksiyaning ishorasi har xil bo‘lgan [
a
,
b
] kesmani oldindan aniqlashga qiyin-
chilik tug‘diradi;
yaqinlashish juda sekin;
sodda bo‘lmagan ildiz, masalan, ildiz funksiyaning ekstremum nuqtasi bilan
mos kelganda (2.2-rasmda
x
2
nuqta), bu usulni qo‘llab bo‘lmaydi, chunki bunda
ildiz atrofida funksiya o‘z ishorasini almashtirmaydi.
agar tenglama [
a
,
b
] kesmada bir nechta ildizga ega bo‘lsa, u holda hisoblash ja-
rayonida shu ildizlardan qaysi biri topilishi noma’lum.
uni tenglama karrali (jufr karrali) va kompleks ildizlarga ega bo‘lganda qo‘llab
bo‘lmaydi;
uni tenglamalar sistemasiga qo‘llab bo‘lmaydi.
Usulning algoritmi:
1.
f
(
a
) va
f
(
b
) ni hisoblang;
2.
c =
(
a
+
b
)/2 deb
f
(
c
) ni hisoblang;
3.
agar sign(
f
(
c
)) = sign(
f
(
a
)) bo‘lsa
a
=
c
deb, aks holda esa
b
=
c
deb almashtirish
oling (bunda sign ishora funksiyasi);
4.
agar
b – a
> ε bo‘lsa, u holda qadam 2 ga o‘ting, aks holda hisob jarayonini
to‘xtating (chunki biz talab qilingan ε – absolyut aniqlikka erishdik). Oxirgi
kesma uchlaridan xoxlagan bittasi yoki ular yig‘indisining yarmini berilgan
f
(
x
)=0 tenglamaning yechimi deb qabul qilishimiz mumkin.
Kesmani teng ikkiga bo‘lish (dixotomiya) usuli algoritmining blok-sxemasi
2.13-rasmda tasvirlangan.
Namunaviy mashqlar va ularning yechimlari
1-misol.
Ushbu
x
4
–
x
3
–2
x
2
+3
x
–3 = 0 tenglamaning ildizlarini analitik yo‘l bilan
ajrating va uning ildizlaridan birini ε = 0,01 aniqlik bilan kesmani teng ikkiga bo‘lish
usulidan foydalanib toping.
68
Yechish.
Yuqorida 3-misolda biz bu tenglamaning ikkita haqiqiy ildizi
mavjudligini, ular
x
1
[–2; –1];
x
2
[1; 2] kesmalarda yotganligini aniqlagan edik.
Ushbu tenglamaning, masalan
x
1
[–2; –1] oraliqdagi haqiqiy ildizini ε = 0,01
aniqlikda topaylik. Barcha hisoblashlar natijalarini jadval ko‘rinishida ifodalaymiz:
n
n
a
n
b
x
n
=
2
n
n
b
a
)
(
n
x
f
0
1
2
3
4
5
6
7
–2,00
–2,00
–1,75
–1,75
–1,75
–1,75
–1,75
–1,74
–1,00
–1,50
–1,50
–1,63
–1,69
–1,72
–1,73
–1,73
–1,50
–1,75
–1,63
–1,69
–1,72
–1,73
–1,74
–3,5625
0,3633
–1,8140
–0,7981
–0,2363
–0,0406
0,1592
Javob:
x
1
≈ –1,73. Ikkinchi ildizni ham xuddi shunday topish mumkin.
2.13-rasm. Kesmani teng ikkiga bo‘lish usulining blok-sxemasi.
69
Yuqoridagi hisoblashlarni bajarish uchun Maple dasturining ushbu
Numerical-
Analysis
paketiga murojaat qilamiz:
# Paketga murojaat qilish
with
(
Student
[
NumericalAnalysis
]):
# Funsiyaning berilishi
f
:=
x
4
–
x
3
–2
x
2
+3
x
–3;
# Funksiyaning grafigini chizish (2.14-rasn)
plot
(
f
,
x
=–2..2);
# Tenglamaning ildizlari
solve
(
f
);
# Tenglama ildizlarining o‘nli kasr ko‘rinishi 2.14-rasn.
# Biseksiya funsiyasiga murojaat va uning natijasi
Bisection
(
f
,
x
= [–2, –1],
tolerance
= 0.0005);
–1.731933594
# Usulning hisob qadamlaridagi intervallar
Bisection
(
f
,
x
=[–2, –1],
tolerance
=0.0005,
output=sequence
);
[–2,. –1], [–2., –1.500000000], [–1.750000000, –1.500000000], [–1.750000000,
–1.625000000], ], [–1.750000000, –1.687500000], [–1.750000000, –1.718750000],
[–1.734375000, –1.718750000], [–1.734375000, –1.726562500], [–1.734375000,
–1.730468750], [–1.732421875, –1.730468750], [–1.732421875, –1.731445312]
#
Approksimatsiya kriteriyasi bo‘yicha iteratsiyalarning to‘xtashi natijasi
Bisection
(
f
,
x
=[–2, –1],
tolerance
=0.0005,
stoppingcriterion=absolute
);
–1.731933594
# Kesmani teng ikkiga bo‘lish jarayonining grafigi va animatsiyaning bosh-
lang‘ich holati (2.15,
a
-rasm)
Bisection
(
f
,
x
=[–2, –1],
output
=
animation
,
tolerance
=0.0005,
stoppingcriterion=function_value
);
# Kesmani teng ikkiga bo‘lish jarayonining grafigi va animatsiyaning oxirgi holati
(2.15,
b
-rasm)
Bisection
(
f
,
x
=[–2, –1],
output
=
animation
,
tolerance
=0.0005,
maxiterations
=10,
stoppingcriterion=relative
);
70
a
b
2.15-rasm. Kesmani teng ikkiga bo‘lish jarayonining grafigi va animatsiyasi.
# Usul hisobining har bir qadami bo‘yicha natijalarning jadval ko‘rinishidagi ifodasi
Roots
(
f
,
x
=[–2, –1],
method=bisection
,
tolerance
=0.01,
output=information
);
2-misol.
Kesmani teng ikkiga bo‘lish usulidan foydalanib,
x
3
+3
x
2
–3=0
tenglamaning [–3;–2] kesmadagi ildizini ε = 0,1 aniqlik bilan hisoblang.
Do'stlaringiz bilan baham: |
