Alisher navoiy nomidagi samarqand davlat universiteti hisoblash usullari kafedrasi

 
Mustaqil ishlash uchun savollar 
 
1.  Oddiy iterasiya usulini asosiy g’oyasi.
 
 
2.  Yaqinlashish shartlari.
 
 
3.  Taqribiy predmetni aniqlash.
 
 
4.  Yaqinlashish haqidagi teorema.
 
 
5.    
Yaqinlashishni baholash.
 
  
  
 
 
 
 
 
)
1
,
.
.
.
,
2
,
1
(
|
|
|
|
1
1
1










n
j
t
s
j
i
ij
i
n
j
i
ij
j







n
j
i
i
ij
n
n
t
s
,
1
|
|
,
0

1
|
|
,
1










n
j
i
i
ij
j
j
t
s
1

j
s













n
j
k
i
j
j
n
j
k
i
j
j
n
i
k
i
i
x
x
t
x
x
s
x
x
1
)
(
1
)
1
(
1
)
1
(
|
|
|
|
|
|









n
j
k
j
j
i
n
j
k
j
j
j
x
x
t
x
x
s
1
)
(
1
)
1
(
|
|
|
|
)
1
(
)
1
(
j
j
j
j
s
s
s
t































n
j
j
j
j
k
n
j
k
j
j
j
n
j
k
j
j
j
x
x
s
x
x
s
x
x
s
1
)
0
(
1
)
(
1
)
1
(
|
|
)
1
(
)
(
|
|
)
1
(
|
|
)
1
(


1



0
|
|
)
1
(
lim
1
)
(







n
j
k
j
i
j
k
x
x
s
)
,
.
.
.
,
2
,
1
(
lim
)
(
n
j
x
x
j
k
j
k





 
108
10-ma’ruza 
ENG TEZ TUShISh. GRADIYeNTLAR METODI 
 
Reja: 
1. 
Eng tez tushish yoki gradiyentlar usulini asosiy g’oyasi.
 
2. 
Gradiyentlar usulini yaqinlashishi haqidagi teorema.
 
 
 
Tayanch  iboralar:  Hisoblash  vektori,  funksional,  funksionallash  gradiyenti, 
gradiyent, ortonormallashtirish. 
 
Bu  metod  haqiqiy  simmetrik  musbat  aniqlangan  matrisali,  chiziqli  algebraik 
tenglamalar 
 
 
 
 
 
                           (10.1) 
sistemasini yechish uchun mo’ljallangan. 
Gradiyentlar  metodini  bayon  qilishdan  avval  funksional  gradiyenti 
tushunchasiga qisqacha to’xtalib o’tamiz. 
Faraz qilaylik, 
   o’lchovli 
 vektorning biror funksionali 
bo’lib, 
 uzunligi birga teng bo’lgan vektor bo’lsin. 
Funksiyaning  o’sish  yoki  kamayish  tezligini  uning  hosilasi  xarakterlaganidek, 
 funksionalning   „argumenti" 
 yo’nalishi bo’yicha o’zgarganda, uning o’zgarish 
tezligini  funksionalning  hosilasi  aniqlaydi. 
  funksionalning 
  nuqtada 
 
yo’nalishi, bo’yicha hosilasi deb ushbu 
 
ifodaga aytiladi. Bu ta’rifdan 
 
bo’lganligi uchun 
 
                                          (10.2) 
bu yerda  
. 
 vektor 
 funksionalning gradiyenti deyiladi. (10.2) teng-likda 
 bo’lganligi 
uchun 
 
kelib chiqadi, bundan esa  
. 
Shu  bilan  birga  agar 
  ning  yo’nalishi  gradiyent  yo’nalishi  bilan  ustma-ust  tushsa, 
b
x
A 
)
(x
f
n
)
,
.
.
.
,
,
(
2
1


n
x
x
x
x
)
,
.
.
.
,
,
(
2
1


n
y
y
y
y
f
x
y
f
x
y
0
0
|
)
(
)
(
)
(
lim
)
(















y
x
f
d
d
x
f
y
x
f
y
x
f
)
,
.
.
.
,
,
(
)
(
2
2
1
1
n
n
y
x
y
x
y
x
f
y
x
f
















0
2
2
1
1
|
)
,
.
.
.
,
,
(
)
(





n
n
y
x
y
x
y
x
f
d
d
y
x
f
),
,
(
)
(
.
.
.
)
(
)
(
2
2
1
1
y
z
y
x
x
f
y
x
x
f
y
x
x
f
n
n











i
i
n
x
x
f
z
z
z
z
z





)
(
,
)
,
.
.
.
,
,
(
2
1
z
)
(x
f
1

y
)
^
,
cos(
)
(
y
x
z
y
x
f



z
y
x
f
z





)
(
y

 
109
 va uning yo’nalishi gradiyen yo’nalishiga qarama-qarshi bo’lsa, 
. Shunday qilib, gradiyent yo’nalishi bo’ylab 
 funksional katta tezlik bilan o’sar 
ekan va gradiyent yo’nalishiga teskari bo’lgan yo’nalish bo’yicha u katta tezlik bilan 
kamayar ekan. 
Endi gradiyentlar metodiga o’tamiz. 
Gradiyentlar metodida (10.1) sistemani yechish uchun 
 
 
 
 
(10.3) 
funksional  qaraladi.  Bu  funksional 
  larga  nisbatan  ikkinchi  tartibli 
ko’phaddir. 
 orqali (10.1) sistemaning yechimini, ya’ni 
 ni belgilaymiz. 
A matrisa simmetrik va musbat aniqlangan bo’lganligi uchun 
 
Shu bilan birga so’nggi ifodada 
 bo’lgandagina, tenglik ishorasi o’rinli bo’ladi. 
Shunday  qilib,  (10.1)  sistemani  yechish  masalasi  (10.3)  funksionalni  minimumga 
aylantiradigan 
  vektorni  topishga  keltiriladi.  Bunday  vektorni  topish  uchun 
quyidagicha ish ko’ramiz.  
 
Faraz  qilaylik, 
  ixtiyoriy  dastlabki  yaqinlashish  vektori  bo’lsin.  (10.3) 
funksionalning gradiyentini hisoblaymiz: 
. 
Buni  (10.2)  bilan  solishtirib, 
  ning  gradiyenti 
  ga  teng  ekanligini 
ko’ramiz.  Keyingi  tekshirishlarda  faqat  gradiyent-ning  yo’nalishigina  kerak 
bo’lganligi  uchun  gradiyent  o’rniga  mus-bat  ko’paytuvchi  2  ni  tashlab, 
 
vektorni  qaraymiz. 
  nuqtada  yo’nalishi  gradiyent  yo’nalishiga  teskari  bo’lgan 
vektorni 
 orqali belgilaymiz: 
. 
 
 
 
(10.4) 
Bu  vektor  (10.1)  sistemaning  xatolik  vektora  deyiladi. 
  vektorning  yo’nalishida 
  funksionalning 
  nuqtadagya  kamayshl  tezligi  eng  katta  bo’ladi. 
 
nuqtadan  boshlab 
  yo’nalish  bo’yicha 
  minimal  qiymatiga 
erishgunga qadar harakatni davom ettiramiz. Bu nuqtani 
 
tenglamadan topamiz: 
.   
 
 
 
(10.5) 
A matrisa musbat aniqlangan bo’lganligi sababli barcha 
 uchun 
. 
Agar 
 bo’lsa, u holda (10.4) dan ko’ramizki, 
 (10.1) sistemaning yechimini 
z
y
x
f



)
(
z
y
x
f



)
(
)
(x
f
)
,
(
2
)
,
(
)
(
x
b
x
x
A
x
f


n
x
x
x
,
.
.
.
,
,
2
1

x
b
A
x
1



0
)
),
(
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
2
)
,
(
)
,
(
2
)
,
(
)
,
(
2
)
,
(
)
,
(
2
)
,
(
)
(
)
(
































x
x
x
x
A
x
x
A
x
x
A
x
x
A
x
x
A
x
x
A
x
x
A
x
x
A
x
x
A
x
b
x
x
A
x
b
x
x
A
x
f
x
f

 x
x

x
)
0
(
x


).
,
(
2
)
,
(
2
)
(
)
,
(
2
)
,
(
|
)
,
2
)
(
(
|
)
(
)
(
0
2
0
0
y
b
x
A
y
x
A
b
x
f
y
x
A
b
y
y
A
d
d
y
x
b
y
x
A
d
d
y
x
f
d
d
y
x
f































)
(x
f
)
(
2
b
x
A 
b
x
A 
)
0
(
х
)
0
(
r
)
0
(
)
0
(
x
A
b
r


)
0
(
r
)
(x
f
)
0
(
x
)
0
(
x
)
0
(
r
)
(
)
0
(
)
0
(
r
x
f


0
)
,
(
2
)
,
(
2
)
(
)
0
(
)
0
(
)
0
(
)
0
(
)
0
(
)
0
(





r
x
A
b
r
r
A
r
x
f
d
d



)
,
(
)
,
(
)
0
(
)
0
(
)
0
(
)
0
(
0
r
A
r
r
r


0
)
0
(

r
0
)
,
(
)
0
(
)
0
(

r
A
r
0
)
0
(

r
)
0
(
x

 
110
beradi  va  shu  bilan  jarayon  to’xtaydi.  Agar 
  bo’lsa,  u  holda  navbatdagi 
yaqinla-shish sifatida 
   
 
 
 
 (10.6) 
vektorni olamiz. 
So’ngra 
  ni  hisoblaymiz.  Keyingi  yaqinlashish  vektori 
  ni 
 funksionalning minimumga erishish shartidan aniqlaymiz: 
. 
Bu jarayonni davom ettirib, quyidagilarga ega bo’lamiz: 
, 
 
 
 
 
(10.7)  
, 
.  
(10.8) 
Bu metodning yaqinlashishi haqida quyidagi teoremani isbotlaymiz. 
Teorema.  Agar  A  musbat  aniqlangan  simmetrik  matrisa  bo’lsa,  u  holda 
gradiyent  metodi  bilan  qurilgan 
  ketma-ket  yaqinlashishlar 
 
sistemaning  yechimi 
  ga  geometrik  progressiya  tezligida  yaqinlashadi.  Aniqrog’i, 
agar  A  matrisaning 
  xoc  sonlari 
  tengsizliklarni  qanoatlan-tirsa,  u 
holda 
  ketma-ketlikning 
  yechimga  yaqinlashish  tez-yaigi  uchinchi  normada 
quyidagicha baholanadi: 
. 
Isbot. A matrysaning xos sonlarini quyidagicha  
 
belgilaymiz,  bularga  mos  keladigan  ortonormallashtirilgan  xos  vektorlarni 
 orqali belgilaymiz. U holda ixtiyoriy 
 
vektor uchun 
 
tenglikka ega bo’lamiz. Bundan esa 
 
tengsizliklar  kelib  chiqadi.  Demak, 
  matrisa  musbat  aniqlakgan  bo’lganligi  uchun 
shunday o’zgarmas 
 va 
 sonlar topiladiki, 
 
tengsizliklar bajariladi. 
Ushbu 
  ayirmani  qaraylik.  (10.3)  va  (10.6)  -  (10.10) 
formulalarga  ko’ra,  murakkab  bo’lmagan  hisoblashlardan  keyin  quyidagilarga  ega 
bo’lamiz: 
. 
 
(10.9) 
0
)
0
(

r
)
0
(
0
)
0
(
)
1
(
r
x
х



)
1
(
)
1
(
x
A
b
r


)
1
(
х
)
(
)
1
(
)
1
(
r
x
f


)
1
(
1
)
1
(
)
2
(
)
1
(
)
1
(
)
1
(
)
1
(
1
,
)
,
(
)
,
(
r
x
x
r
r
A
r
r





)
(
)
(
k
k
x
A
b
r


)
,
(
)
,
(
)
(
)
(
)
(
)
(
k
k
k
k
k
r
r
A
r
r


)
(
)
(
)
1
(
k
k
k
k
r
x
x




)
(
)
1
(
)
0
(
,
.
.
.
,
,
k
x
x
x
b
x
А 

x
i

M
m
i




0
}
{
)
(k
x

х
))
(
)
(
(
1
)
0
(
2
3
)
(













x
f
x
f
m
M
m
M
m
x
x
k
k
0
.
.
.
2
1




n



n
u
u
u
,
.
.
.
,
,
2
1
)
(
)
2
(
2
)
1
(
1
.
.
.
n
n
u
c
u
c
u
c
x




n
n
c
c
c
x
x
A



2
2
2
2
1
2
1
.
.
.
)
,
(




)
,
(
)
.
.
.
(
)
,
(
)
.
.
.
(
)
,
(
1
2
2
2
2
1
1
2
2
2
2
1
2
x
x
c
c
c
x
x
A
c
c
c
x
x
n
n
n














A
0

m
0

M
)
,
(
)
,
(
)
,
(
x
x
M
x
x
A
x
x
m


)
(
)
(
)
0
(
)
1
(
x
f
x
f

)
,
(
)
,
(
)
(
2
)
,
(
)
(
)
(
)
0
(
)
0
(
2
)
0
(
)
0
(
)
0
(
)
0
(
0
)
0
(
)
0
(
2
0
)
0
(
)
1
(
r
A
r
r
r
r
r
r
A
r
x
f
x
f








 
111
A — simmetrik matrisa, 
 va 
 bo’lganligi uchun 
. 
Demak, (10.9) ga ko’ra 
. 
Endi 
 ni   matrisaning xos vektorlari bo’yicha yoyamiz:   
. 
U vaqtda, 
 
va 
. 
Demak, 
. 
Quyidagicha 
, 
belgilashni kiritib, 
  
 
 
(10.10) 
tenglikni hosil qilamiz. 
Quyidagini  isbotlaylik:  agar 
  bo’lsa,  u  holda  ixtiyoriy 
haqiqiy 
 sonlar uchun 
  
 
 
(10.11) 
tengsizlik  o’rinlidir.  Buni  isbotlash  uchun 
  o’rniga 
  sonlarni  olamiz,  u 
vaqtda  
 
bo’lib, 
 
tenglik  o’rinly  bo’ladi.  Oxirgi  ifodaga  ikki  son  o’rta  geometrigi  uning  o’rta 
b
x
A


)
(
)
0
(
)
0
(
x
x
A
r



)
,
(
)
(
),
(
)
(
)
(
)
0
(
)
0
(
1
)
0
(
)
0
(
)
0
(
r
r
A
x
x
A
x
x
x
f
x
f









2
)
0
(
)
0
(
)
0
(
)
0
(
1
)
0
(
)
0
(
)
1
(
)
0
(
)
0
(
)
,
(
)
,
)(
,
(
)
(
)
(
)
(
)
(
r
r
r
r
A
r
A
r
x
f
x
f
x
f
x
f





)
0
(
r
A



n
i
i
i
u
a
r
1
)
0
(








n
i
i
i
i
n
i
i
i
i
u
a
r
A
u
a
r
A
1
1
)
0
(
1
0
)
0
(
,










n
i
i
i
n
i
i
i
a
r
r
A
a
r
r
A
1
1
2
)
0
(
)
0
(
1
1
2
)
0
(
)
0
(
)
,
(
,
)
,
(



















n
k
k
n
i
i
i
n
i
i
i
a
a
a
x
f
x
f
x
f
x
f
1
2
1
1
2
1
2
)
1
(
)
0
(
)
0
(
)
(
)
(
)
(
)
(


)
,
0
(
1
1
1
2
2







n
i
i
i
n
k
k
i
i
d
d
a
a
d









n
j
j
j
n
i
i
i
d
d
x
f
x
f
x
f
x
f
1
1
1
)
1
(
)
0
(
)
0
(
)
(
)
(
)
(
)
(


)
,
1
(
0
n
i
M
m
i





1
),
,
1
(
0
1





n
i
i
i
d
n
i
d
2
1
1
1
4
1













M
m
m
M
d
d
n
j
j
j
n
i
i
i


i

mM
i



1
m
M
M
m
i














n
j
j
j
n
i
i
i
n
j
j
j
n
i
i
i
d
d
d
d
1
1
1
1
1
1





 
112
arifmetigiday ortmasligi haqidagi teoremani qo’llaymiz: 
. 
 
 
(10.12) 
Ushbu  
  
funksiya 
 bo’lganda (0, 1) oraliqda kamayib, 
 oraliqda 
o’sadi va o’zining eng kichik qiymatini 
 nuqtada qabul qiladi; 
 
oraliqda esa 
 va 
 nuqtalarda o’zining eng katta qiymatini qabul 
qiladi, bu qiymat 
   
 
 
 
(10.13) 
ga  tengdir.  (10.12)  ifodada  har  bir 
  ni  uning  eng  katta  qiymati  (10.13)  bilan 
almashtiramiz, u holda 
, 
shu bilan (10.11) isbotlandi. (10.11) ni (10.10) ga qo’llab, 
 
ni hssil qilamiz, bu yerda 
. Bunla 
n esa 
 deb belgilab olib, quyidagiga ega bo’lamiz: 
. 
Shunday qilib, ixtifiy   uchun  
 
ni hosil qilamiz. Endi 
 
ning 
 ga intilish tezligini uchinchi normada baholaylik, 
 bo’lganligi 
uchun 
. 
Ravshanki  
. 
Oxirgi ikki ifodadan   
. 
Shu bilan teorema isbot bo’ldi.