Alisher navoiy nomidagi samarqand davlat universiteti hisoblash usullari kafedrasi

 
 
 
 
 
 
sxema 
qismlari 
2 
-3 
4 
1 
-3 
5 
-1 
2 
4 
-1 
1 
3 
1 
2 
3 
2 
11 
-6 
1 
1 
15 
-3 
8 
9 
 
 
 
 
 
 
 
 
1,41421 
-2,12133 
0,70708 
2,82843 
7,07138 
7,55013 
0,70711 
4,94995 
4,50363  
1,64904  
7,77819 
30,40691 
28,61122  
4,94718 
10,60661 
43,13538 
40,66504  
6,59622  
 
2,99958 
3,99970 
1,99975 
2,99980 
2,00002 
3,00004 
3,00004 
4,00004 
 
 
 
 
 
Jadvaldagi  yechimni  verguldan  keyin  uch  xonasigacha  yaxlitlab  olsak, 
quyidagiga ega bo’lamiz: 
. 
Bu esa aniq yechimni beradi. 
 
Mustaqil ishlash uchun savollar 
 
1.  Matrisa to’g’risida to’liq ma’lumotlar. 
2.  Uchburchak va dioganal matrisalar. 
  

























1
2
3
2
,
1
3
4
,
6
2
5
3
,
11
4
3
2
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
ij
a
i
b
A

ij
t
i
y
i
А

34
t
3
y
,
61122
,
28
55013
,
7
40691
,
30
07138
,
7
77819
,
7
8843
,
2
1
,
50363
,
4
55013
,
7
94995
,
4
07138
,
7
70711
,
0
82843
,
2
3
33
2
23
2
13
3
3
33
24
23
14
13
34
34
i
i
t
y
t
y
t
b
y
i
i
t
t
t
t
t
a
t


















1
i
a
2
i
a
3
i
a
4
i
a
i
y

A
1
i
t
2
i
t
3
i
t
4
i
t
i
y

i
i
i
i
i
1
A
i
x
i
x
2
A
0000
,
3
;
000
,
2
;
000
,
2
;
000
,
3
4
3
2
1




x
x
x
x

 
97
9-ma’ruza 
 
ITERASION METODLAR 
 
Reja: 
1.  Iterasion jarayonni qurish prinsiplari. 
2.  Oddiy iterasiya metodi. 
3.  Zeydel metodi. 
 
 
Tayanch  iboralar:  Maxsusmas  matrisa,  yaqinlashish  sharti,  maxsus  predmet, 
bosh qism. 
 
Endi  iterasion  metodlarni  bayon  qilishga  o’tamiz.  Bobning  boshida  aytib 
o’tilganidek,  bu  yerda  aniq  yechim  cheksiz  ketma-ketliklarning  limiti  sifatida 
topiladi. 
Hozirgi  vaqtda  har  xil  prinsiplarga  asoslangan  holda  juda  ko’p  iterasion 
metodlar  yaratilgan.  Umuman,  bu  metodlarning  o’ziga  xos  tomonlaridan  yana  biri 
shundan  iboratki,  ular  o’z  xatosini  o’zi  tuzatib  boradi.  Agar  aniq  metodlar  bilan 
ishlayotganda biror qadamda  xatoga  yo’l qo’yilsa, bu  xato oxirgi  natijaga  ham ta’sir 
kiladi.  Yaqinlashuvchi  iterasion  jarayonning  biror  qadamida  yo’l  qo’yilgan  xato  esa 
faqat  bir  necha  iterasiya  qadamini  ortiqcha  bajarishgagina  olib  keladi  xolos.  Biror 
qadamda  yo’l  qo’yilgan  xato  keyingi  qadamlarda  tuzatib  boriladi.  Metodlarning 
hisoblash sxemalari sodda bo’lib, ularni EHMlarda realizasiya qilish qulaydir. Lekin 
har  bir  iterasion  metodning  qo’llanish  sohasi  chegaralangandir.  Chunki  iterasiya 
jarayoni  berilgan  sistema  uchun  uzoqlashishi  yoki,  shuningdek,  sekin  yaqinlashishi 
mumkinki, amalda yechimni qoniqarli yniqlikda topib bo’lmaydi. 
Shuning  uchun  ham,  iterasion  metodlarda  faqat  yaqinlashish  masalasigina 
emas, balki  yaqinlashish tezligi  masalasi  ham katta ahamiyatga egadir. Yaqinlashish 
tezligi dastlabki yaqinlashish vektorining qulay tanlanishiga ham bog’liqdir. 
Bu  paragrafda  avval  iterasion  jarayon  qurishning  umumiy  prinsipini  ko’rib 
chiqamiz,  so’ngra  esa  hisoblash  amaliyotida  keng  qo’llaniladigan  iterasion 
metodlarni keltiramiz. 
Iterasion jarayonni qurish prinsiplari. Faraz qilaylik, maxsusmas matrisali 
                                                               (9.1) 
sistema berilgan bo’lsin. Iterasion metodlarni qurayotganda en-pop ixtiyoriy dastlabki 
yaqinlashish vektori 
 olinib, keyinga yaqinlashishlar 
 quyidagi 
                                                     (9.2) 
rekurrent  formula  yordamida  topiladi,  bu  yerda 
  umuman  olganda  A  matrisaga, 
ozod  hadlar  vektori 
  ga,  yaqinlashish  nomeri 
  ga  va  dastlabki  yaqinlashishlar 
 ga bog’liq bo’lgan qandaydir funksiyadir. 
Agar 
 faqat 
 ga bog’liq bo’lib, 
 larga bog’liq bo’lmasa, u 
holda iterasiya metodi barinchi tartibga ega deyiladi. Agar 
 funksiyasi   ga bog’liq 
b
x
A 
)
0
(
x
)
(
)
2
(
)
1
(
,
.
.
.
,
,
k
x
x
x
)
,
.
.
.
,
,
(
)
(
)
1
(
)
0
(
)
1
(
k
k
k
x
x
x
f
x


k
f
b
k
)
(
)
1
(
)
0
(
,
.
.
.
,
,
k
x
x
x
k
f
)
(k
x
)
(
)
1
(
)
0
(
,
.
.
.
,
,
k
x
x
x
k
f
k

 
98
bo’lmasa,  iterasiya  metodi  stasionar  deyiladi.  Albatta, 
  funksiyaning  eng  soddasi 
chiziqli  funksiyadir.  Ketma-ket  yaqinlashishlarning  birinchi  tartibli  eng  umumiy 
chiziqli metodi quyidagi 
                                                        (9.3) 
ko’rinishga ega bo’lib, bu yerda 
 — kvadrat matrisa va 
 — vektor. Biz (9.2) va 
(9.3)  iterasion  metodlarga  tabiiy  ravishda  (9.1)  ning  aniq  yechimi 
 
qo’zg’almas  nuqta  bo’lishi  kerak,  ya’ni 
  sifatida  aniq  yechim 
  olinganda 
keyingi  yaqinlashish-lar  xam 
  ga  teng  bo’lishi  kerak  degan  talabni  qo’yishimiz 
kerak. Bu esa birinchi tartibli chiziqli metod uchun ushbu 
                                                         (9.4) 
yoki 
                                                      (9.5) 
tengliklarga olib keladi. O’z navbatida (8.5) day 
                                                            (9.6) 
tenglik  kelib  chiqadi.  (9.5)  dan  foydalanib,  (9.3)  iterasion  jarayonni  quyidagicha 
yozishimiz mumkin: 
                                                         (9.7) 
Bu yerda 
 va 
 matrisalar 
 ga bog’liq emas. Endi (9.6) ni (9.7) ga keltirib 
qo’ysak, 
                                                      (9.8) 
hosil bo’ladi. 
Agar 
 matrisa mavjud bo’lsa, u holda (9.7) ning ikala tomonini chapdan 
 
ga ko’paytirib, 
                                                          (9.9) 
ni hosil qilamiz. Tabiiyki, bu yerda 
                                                              (9.10) 
tenglik  bajarilishi  kerak.  (9.9)  tenglik 
  ni  oshkormas  ko’rinishda  aniqlaydi. 
Shuning  uchun  ham 
  shunday  matrisa  bo’lishi  kerakki, 
  ni  topish  qiyin 
bo’lmasin.  Odatda 
  sifatida  diagonal  yoki  uchburchak  matrisa  olinadi.  Birinchi 
holda metod to’liq qadamli, ikkinchi holda esa bir qadamli, deyiladi. 
Ketma-ket  yaqinlashishlar,  birinchi  tartibli  chiziqli  metodlarning  turli 
ko’rinishlari  asosan  (9.7)  —  (9.10)  formulalar  yordamida  amalga  oshiriladi.  Juda 
ko’p chiziqli va chiziqli bo’lmagan ketma-ket yaqinlashish metodlarini 
 
funksionalni  eng  kachik  kvadratlar  metsdi  yoki  boshqa  metod-lar  bilan 
minimallashtirish natijasida hosil qilish mumkin.  
Oddiy iterasiya metodi. Faraz qilaylik, 
                                                           (9.11) 
sistema biror usul bilan 
k
f
)
(
)
(
)
1
(
k
k
k
k
c
x
B
x



k
B
)
(k
c
b
A
x
1



)
0
(
x

x

x
k
k
c
b
A
B
b
A




1
1
b
C
b
A
B
E
c
k
k
k



1
)
(
E
A
C
B
k
k


b
C
x
B
x
k
k
k
k



)
(
)
1
(
k
B
k
C
b
)
(
)
(
)
(
)
1
(
b
x
A
C
x
x
k
k
k
k




1

k
С
1

k
С
b
x
F
x
D
k
k
k
k



)
(
)
1
(
A
F
D
k
k


)
1
( 
k
x
k
D
1

k
D
k
D
2
)
(
b
x
A
x
f


b
x
А 

 
99
                                                         (9.12) 
ko’rinishga keltirilgan bo’lsin, qanday keltirish kerakligini keyinchalik ko’rib o’tamiz 
va  dastlabki  yaqinlashish  vektori 
  bi-ror  usul  bilan  (masalan, 
  kabi) 
topilgan bo’lsin. Agar keyingi yaqinlashishlar 
                                               (9.13) 
rekurrent  formulalar  yordamida  topilsa,  bunday  metod  oddiy  iterasiya  metodi 
deyiladi.  (9.12)  dan  ko’ramizki,  oddiy  iterasiya  metodi  bu  birinchi  tartibli  to’liq 
qadamli  iterasion  metoddir.  Agar  (9.13)  ketma-ketlikning  limiti 
  mavjud  bo’lsa, 
(bu limit (9.13) sistemaning, (shu bilan (9.11) sistemaning ham) yechimi bo’ladi. 
Haqiqatan ham, (9.13) tenglikda limitga o’tsak, 
 kelib chiqadi. 
Oddiy iterasiya metodining yaqinlashish shartini aniqlaylik. 
1-teorema.  (9.13)  oddiy  iterasiya  jarayoni  o’zining  ixtiyoriy  dastlabki 
yaqinlashish vektori 
 da yaqinlashuvchi bo’lishi uchun 
 matrisaning barcha xos 
sonlari birdan kichik bo’lishi zarur va kifoyadir. 
Isbot.  Zarurligi.  Faraz  qilaylik,  ixtiyoriy  dastlabki  vektor  uchun 
 
limit  mavjud  bo’lsin.  U  holda 
  (9.13)  ni  bu  tenglikdan  ayirib, 
quyidagilarni hosil qilamiz: 
. 
Endi 
 vektor   ga bog’liq bo’lmaganligi uchun 
 
tenglikda 
 limitga o’tsak, 
 
kelib  chiqadi, 
  matrisaning  barcha  xos  sonlarining  modullari  birdan  kichikligi 
ko’rinadi.  
Kifoyaligi.  (9.13)  orqali  aniqlanadigan  barcha  yaqinlashishlarni  dastlabki 
vektor 
 va   orqali ifodalaymiz: 
 
Endi, faraz qilaylik, 
 ning barcha xos sonlari birdan kichik bo’lsin. U holda  
. 
Demak, 
 qanday bo’lishidan qat’i nazar 
 yaqinlashuvchi ketma-ketlikdir. 
Isbot  qilingan  teorema  nazariy  jihatdan  foydali,  chunki  u  mavjud  haqiqatni 
aniq  ifodalaydi.  Lekin,  amaliy  ishlar  uchuya  yaramaydi.  Endi  V  matrisaning 
elementlari orqali ifodalanadi-gan kifoyalilik belgisini keltiramiz. 
2-teorema.  (9.13)  oddiy  iterasiya  jarayonining  yaqinlashuvchi  bo’lishi  uchun 
 matrisaning biror normasi birdan kichik bo’lishi kifoyadir. 
Isbot.  Haqiqatan  ham,  agar  ||
||<1  bo’lsa,  bu  matrisaning  barcha  xos  sonlari 
modullari  bo’yicha  birdan  kichik  bo’lib,  bundan  1-teoremaga  asosan  oddiy  iterasion 
jarayonning yaqinlashishligi kelib chiqadi. 
2-teorema bir necha qulay kifoyalilik belgilarini keltirishga imkon beradi. 
b
x
B
х


)
0
(
x
c
x

)
0
(
.)
.
.
,
2
,
1
(
,
)
1
(
)
(




k
c
x
B
x
k
k

x
c
x
B
х




)
0
(
x
B



 x
x
k
k
)
(
lim
c
x
B
x




)
(
..
.
)
(
)
(
)
0
(
)
2
(
2
)
1
(
)
(
x
x
B
x
x
B
x
x
B
x
x
k
k
k
k














)
0
(
x
x 

k
)
(
)
0
(
)
(
x
x
B
x
x
k
k







k
0
lim



k
k
B
B
)
0
(
х
c
.
)
...
(
.
.
.
)
(
)
(
1
)
0
(
)
2
(
2
)
2
(
)
1
(
)
(
c
B
B
E
x
B
c
B
E
x
B
c
c
x
B
B
c
x
B
x
k
k
k
k
k
k



















B
1
1
2
)
(
...
,
0











B
E
B
B
B
E
B
k
k
k
)
0
(
x
)
(k
x
B
B

 
100
3-teorema. (9.13) oddiy  iterasiya jarayovd  yaqinlashishi  uchun 
  matrisaning 
elementlari quyidagi 
,                                                (9.14) 
,                                                (9.15) 
                                                (9.16) 
tengsizliklarning birortasini qanoatlantirishi kifoyadir.  
Agar biz 
 
normalarni  eslasak,  teoremadagi  avvalgi  ikkita  shart  2-  teoremadan  kelib  chiqadi. 
Oxirgi  shartdagi  tengsizlik  esa, 
  ning  birdan  kichik  ekanligini  ko’rsatadi. 
Haqiqatan  ham,  bu  yerda 
 
  matrisaning  eng  katta  xos  soni  bo’lganligi  va 
 
ning barcha xos sonlari manfiy bo’lmaganligi uchun 
 
Lekin  bu  tengsizlikning  o’ng  tomoyaidagi  ifoda 
  ning  iziga  (ya’ni 
  matrisa 
diagonal elementlarining yig’indisiga) teng bo’lib, u esa 
 ra tengdir. 
Endi yaqinlashish tezligini baholaydigan quyidagi teoremani keltiramiz. 
4-teorema.  Agar 
  matrisaning,  x  vektorning  berilgan  normasiga  moslangan 
biror  normasi  birdan  kichik  bo’lsa,  u  holda  (9.13)  oddiy  iterasiya  metodining  xatosi 
quyidagicha baholanadi: 
Isbot. Teorema shartiga ko’ra 
, shuning uchun ham 
.                                               (9.17) 
Bu tenglikni (9.15) dan ayirsak, 
.                                            (9.18) 
Bundan esa 
. 
Shuni  isbotlash  talab  qilingan  edi.  Shuni  ham  ta’kidlab  o’tish  kerakki,  agar 
 
sifatida ozod hadlar ustuni   olingan bo’lsa, u holda iterasiyaning xatosi quyidagicha 
baholanadi: 
.                                                        (9.19) 
Haqiqatan ham, 
 deb olsak, u holda (9.18) o’rniga 
 
tenglikka ega bo’lamiz, bundan esa (9.19) kelib chiqadi. 
B
1
|
|
max
1





n
j
ij
i
b
1
|
|
max
1





n
i
ij
j
b
1
|
|
1
,
2





n
j
i
ij
b






n
i
ij
j
n
j
ij
i
b
B
b
B
1
2
1
1
|
|
max
,|
|
max
1
3


B
1

B
B
B
B
n








.
.
.
2
1
1
B
B
B
B


n
j
i
ij
b
1
,
2
|
|
B
1

B
c
B
B
B
E
x
k
...)
...
(
1
2








c
B
B
x
B
x
x
k
k
k
k
...)
(
1
)
0
(








B
c
B
x
B
c
B
B
x
B
x
x
k
k
k
k
k
k










1
...)
(
)
0
(
1
)
0
(
)
(
)
0
(
x
c
B
c
B
x
x
k
k





1
1
)
(
c
x

)
0
(
c
B
B
x
x
k
k
k
...)
(
2
1








 
101
Endi  (9.11)  sistemani  (9.12)  ko’rinishga  keltirish  va  oddiy  iterasiyaning  amalda 
qo’llanilishi ustida to’xtalib o’tamiz. Shu maqsadda ixtmyoriy mdxsusmas R matrisa 
olib, iterasiyaning quyidagi 
                                                 (9.20) 
ko’rinishda yozish mumkin. Albatta, R matrisa shunday tanlangan bo’lishi kerakki, 
 
matrisa  uchun  yaqinlashish  sharti  bajarilsin.  Quyidagi  ikkita  xususiy  holni  ko’rib 
chiqamiz. 
1. 
,  bu  yerda 
  diagonal  matriad  bo’lib,  diagonal  elementlari  A 
matrisaniig  diagonal  elementlari  bilan  ustma-ust  tushsin.  Bu  holda  (9.20)  iterasiya 
jarayonini tuzish 
 
sistema  tenglamalarini  mos  ravishda 
  larga  bo’lib,  hosil  bo’lgan 
tenglamalarda 
  larnn  mos  ravishda  chap  tomonda  qoldirib,  qolganlariii 
o’ng tomonga o’tkavishdan iboratdir. Natijada, 
 
sistemaga ega bo’lamiz. Albatta bu usulni qo’llash  mumkin bo’lishi uchun barcha ai 
lar  noldan  farqli  bo’lishi  kerak.  Bundan  tashqari  diagonal  elementlarning  modullari 
boshqa  elementlarining  modullaridan  ancha  katta  bo’lishi  kerak.  Aniqrog’i  quyidagi 
tengsizliklarning birortasi bajarilishi lozim: 
,                                                   (9.21) 
,                                                     (9.22) 
.                                                 (9.23) 
Bu  tengsizliklar,  bajarilsa,  u  holda  mos  ravishda  (9.14)  —  (9.16)  tengsizliklar  ham 
bajariladi. 
2. 
,  bu  yerda 
  elementlarining  modullari  yetarlicha  kichik 
bo’lgan matrisadir. Bu holda (9.20) tenglik 
 
c
P
x
PA
E
х
k




)
(
)
1
(
)
(

PA
E
B


1

 D
P
D



















n
n
nn
n
n
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
.
.
.
.
.
.
.
.
.
.
.
.
.
.
,
.
.
.
,
.
.
.
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
nn
a
a
a
,
.
.
.
,
,
22
11
n
x
x
x
,
.
.
.
,
,
2
1
1
1
,
1
1
22
2
1
22
21
22
2
2
11
1
2
11
12
11
1
1
.
.
.
.
.
.
.
.
.
.
.
,
.
.
.
,
.
.
.














n
nn
n
n
nn
n
nn
n
n
n
n
n
n
x
a
a
x
a
a
a
b
x
x
a
a
x
a
a
a
b
x
x
a
a
x
a
a
a
b
x
ii
n
i
j
i
ii
ij
i
a
a
a



 ,
1
max
1
max
,
1




j
i
i
ii
ij
j
a
a
1
|
|
1
1
,
1
2
1
2






n
i
i
ij
n
j
ij
a
a
s
A
P


1
 
ij



c
A
x
A
x
k
k
)
(
1
)
(
)
1
(








 
102
ko’rinishga ega bo’lib, A matrisa yaqinlashish shartini qanoatlantiradi. 
(8.11)  sistemani 
  ga  ko’paytirish  sistema  tenglamalari  ustida  elementar 
almashtirish bajarish bilan teng kuchlidir. 
Odatda  R  ni  2-ko’rinishda  olinganda  misol  yechish  uchun  quyidagicha  ish 
tutiladi.  Berilgan  sistemadan  shunday  tenglamalarni  ajratib  olinadiki,  bu 
tenglamalarda  biror  noma’lum  oldidagi  koeffisiyent  moduli  bo’yicha  shu 
tenglamaning  qolgan  barcha  koeffisiyentlari  modullarining  yig’indisidan  katta 
bo’lsin.  Ajratilgan  tenglamalar  shunday  joylashtiriladiki,  ularning  eng  katta 
koeffisiyentlari  diagonal  koeffisiyentlari  bo’lsin.  Tenglamalarning  qolganllridan  va 
ajratilganlaridan  yuqoridagi  prinsip  saqlanadigan,  ya’ni  eng  katta  koeffisiyent 
diagonal  koeffisiyent  bo’ladigan  qilib  o’zaro  chiziqli  erkli  bo’lgan  chiziqli 
kombinasiyalar tuziladi  va barcha bo’sh satrlar to’ldiriladi. Shu bilan birga dastlabki 
sistemaning har bir tenglamasi yangi sistema tenglamalarini tuzayotganda qatnashishi 
kerak. 
Bu yerda ko’rsatilgan usullarni misollarda tushuntnramiz. 
1-misol. Quyidagi sistema odiy iterasiya metodi bilan yechilsish: 
                                             (9.24) 
Ye  ch  i  sh.  Birinchi  usulda  aytilganidek,  bu  sistemaning  tenglamalarini  mos 
ravishda  olamiz  10,  25,  —20,  10,  —20  larga  bo’lib,  quyidagi  ko’rinishda  yozib 
olamiz: 
                                  (9.25) 
Bu yerda (9.14) dagi yig’indilar mos ravishda 0,7; 0,36; 0,4; 0,7; 0,3 bo’lib, bulardan 
esa 
 kelib chiqadi. 
Dastlabki yaqinlashish 
 sifatida ozod hadlar ustuni (0,6; 0,44; 0,95; 1; 1,6)' 
ni olib, keyingi yaqinlashishlarni topamiz: 
, 
 
Shunga  o’xshash 
.  Hisoblashlarning  davomi  1- 
jadvalda keltirilgan. 
Shuni  ham  ta’kidlab  o’tish  kerakki,  hisoblashlarni  qisqartirish  maqsadida 
avvalgi  bir  necha  yaqinlashishlarni  kamroq  o’nli  raqamlari  bilan  hisoblash  ham 
mumkin. 
Hisoblashlar,  odatda, 
  va 
  yaqinlashishlar  kerakli  aniqlikda  ustma-ust 
tushgunlari qadar davom ettiriladi. 
 
 
P




























32
20
2
2
,
10
5
10
,
11
2
5
25
,
6
2
3
10
5
4
3
2
1
5
4
3
2
5
4
3
2
1
5
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x


























.
1
,
0
05
,
0
1
,
0
05
,
0
6
,
1
,
5
,
0
1
,
0
1
,
0
1
,
08
,
0
2
,
0
04
,
0
04
,
0
44
,
0
,
1
,
0
2
,
0
3
,
0
1
,
0
6
,
0
4
3
2
1
5
5
3
2
3
5
4
3
1
2
5
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
1
7
,
0
1


B
)
0
(
x
881
,
0
6
,
1
1
,
0
1
2
,
0
95
,
0
3
,
0
44
,
0
1
,
0
6
,
0
1
,
0
2
,
0
1
,
0
6
,
0
)
0
(
5
)
0
(
4
)
0
(
2
)
1
(
1














x
x
x
x
754
,
0
6
,
1
08
,
0
1
2
,
0
95
,
0
04
,
0
6
,
0
04
,
0
44
,
0
)
1
(
2










x
72
,
1
;
851
,
1
;
892
,
0
)
1
(
5
)
1
(
4
)
1
(
3



x
x
x
)
(k
x
)
1
( 
k
x

 
103
1- jadval