Министерства высшего и среднего специального

X  (x, y)
= (1; 1) ni Broyden usuli

Yechish. Misolning yechimi jarayonini, iteratsiyalardagi

X_k  (x_k , y_k )
yaqinlashishlarni quyidagi jadval shaklida ifodalaylik:

K	xk	yk	Xk  X
0	2,000000000	2,000000000	1,414213562
1	1,694513211	0,889023252	0,703323850
2	1,532940994	0,835742461	0,557679695
3	1,330935487	0,770464391	0,402746685
4	1,251500757	0,804076528	0,318808151
5	1,139841409	0.866849425	0.193092452
6	1.087198127	0.913245001	0.123003835
7	1.039140157	0.958904664	0.056751903
8	1.016525113	0.982554663	0.024029547
9	1.003700722	0.996037640	0.005421774
10	1.000537288	0.999428320	0.000784536
11	1.000005832	0.999993444	8.774735736E-6
12	1.000000808	0.999999157	1.167386327E-6
13	0.999999806	1.000000202	2.795316564E-7
14	1.000000000	1.000000000	3.994662952E-10

Jadvaldan ko‘rinadiki, bu misolning natijasiga Nyuton usuli bilan 8 qadamda erishilgan edi. Bu esa Broyden usulining iteratsiya tezligi Nyuton usulinikidan past ekanligini ko‘rsatadi. Shunga qaramasdan, Broyden usuli ommabop bo‘lib, hisoblash amaliyotida keng qo‘llanilib kelinmoqda.

10. Tezkor tushish usuli (Gradiyent usuli)

Yuqoridagi (1) tenglamalar sistemasini qaraymiz. Faraz qilaylik, f_i
funksiyalar o‘zlarining umumiy aniqlanish sohasida haqiqiy va uzluksiz differensiallanuvchan. Quyidagi funksiyani qaraymiz:

U _ x_ 
ⁿ  f _ x_²  _ f _ x_,
^{f  x} ^.

^ ⁱ 
i1
Ravchanki, (1) sistemaning har bir yechimi U(x) funksiyani nolga

aylantiradi; va aksincha U(x) funksiya nolga teng bo‘ladigan sonlar (1) sistemaning ildizlari.
x₁, x₂,

Faraz qilamizki, (1) sistema izolyatsiyalangan yechimgagina ega
bo‘lib, bu yechim U(x) funksiyaning qat’iy minimum nuqtasi bo‘lsin. Bu bilan masala n o‘lchovli fazoda U(x) funksiyaning minimumini topishga olib kelinadi.

Faraz qilaylik, x  (1) sistemaning vektor-ildizi,
_x⁰
esa uning

boshlang‘ich yaqinlashishi bo‘lsin.
_x⁰
nuqta orqali U(x) funksiyaning

sath sirtini o‘tkazamiz. Agar
_x⁰
nuqta x ildizga yetarlicha yaqin bo‘lsa, u

holda bizning farazimiz bo‘yicha sath sirti o‘xshash.
^U  ^x ^{ U} _^x0 _
ellipsoidga

_x⁰
nuqtadan boshlab
^U  ^x ^{ U} _^x0 _
sirt normali bo‘ylab

harakatlanib, bu harakatni shu normal qaysidir boshqa bir
^U  ^x ^{ U} _^x1 _

sath sirtiga biror
_x¹
nuqtada urinmaguncha davom ettiramiz. Keyin yana

_x¹
nuqtadan harakatni
^U  ^x ^{ U} _^x1 _
sath sirti bo‘ylab davom ettirib, bu

^{harakatni shu normal boshqa bir yangi U}  ^x ^{ U} _^x2 _
sath sirtiga biror
_x²

nuqtada urinmaguncha davom ettiramiz va hokazo. Vaholanki,
U _x^0 _  U _x^1 _  U _x^2 _  bo‘lsa, u holda biz shu yo‘l bilan
harakatlanib, U(x) ning (1) sistemaning izlanayotgan x ildiziga mos keluvchi eng kichik qiymatli nuqtasiga tezkor yaqinlashib boramiz. Ushbu

_U _
 _x1 

U

 
U _ x_  ^{ }
 
_ ^xn _
– tuzilgan U _ x_
funksiyaning gradiyenti belgilashini kiritib,

OM₀M₁, OM₁M₂, vektorli uchburchaklardan quyidagini yozamiz:
^{x p1  x p  pU} _^{x p} _, _ p  0,1,2, _.

Endi _p
ko‘paytuvchin aniqlash qoldi. Buning uchun quyidagi skalyar

funksiyani qaraymiz:
_ _  U ^x^{ p}  _pU _x^p _^ .

 
^{Bu }^ 
funksiya U funksiya sathining
_x ^p
nuqtadagi sath sirtiga

o‘tkazilgan normalga mos keluvchi o‘zgarishini beradi.
  _p

ko‘paytuvchini shunday tanlash lozimki,
_ _
funksiya minimumga

erishsin. Bu funksiyadan  bo‘yicha hosila olib, uni nolga tenglashtiramiz. Unda quyidagi tenglamani hosil qilamiz:
^_ _  ^d U ^x^{ p}  _pU _x^{ p} _^  0 . (40)
_d _ _

40. 
    tenglamaning eng kichik musbat ildizi bizga _p
    

ning qiymatini

beradi. Endi _p
sonni taqribiy topish usulini qarab chiqaylik. Faraz

qilamizki,   kichik parametr bo‘lib, uning kvadrati va undan yuqori darajalarini e’tiborga olmaslik mumkin. U holda quyidagiga kelamiz:

2

^ ⁱ _{ }

_ _ 
n


i1
^{f x p  U} _^{x p} _^ .

f_i funksiyani  ning chiziqli hadlarigacha aniqlikdagi darajalariga
yoyib, quyidagiga ega bo‘lamiz:

_n ^{ } f_{i }x^{ p} _
2

_ _  _^ f_i ^ x^{ p}  
_{U x} ^p _^ _,

x
 
i1 _{ 
} _{ }_

bu yerda

f_{i } ^ f_{i ,} f_{i , ,}



f_i ^ _.

x ^x₁ x₂ x_n ^
 
Bulardan
_n ^ f_{i }x^{ p} _ ^ f_{i }x^{ p} _


^_ _  2_^ f_{i }x^p _   U _x^{ p} _^  U _x^{ p} _  0 .

Natijada,

ⁿ _{f x} ^p
_{p } i1
i1 ^




^ i  
f_{i }x^{ p} _
x
x
U _x^{ p} _




<sub>


</sub> f _x^{ p} _,
x


_{W x} ^p _{U x} ^p _
,

_n ^f_{i }x^{ p} _
^2 _W _x^{ p} _U _x^{ p} _,
_{W x} ^p _{U x} ^p _





i1 ^{ x}

U _x^{ p} _^


_

bu yerda W _ x_  f_i
x  vektor-funksiya f ning Yakob matritsasi.

Yuqoridagilardan quyidagi tenglikka kelamiz:

U _ 
^ n  f
_ x_^{2 }  2 n
_{f  x} f_{i } x_{ .}

x x
^_{ i}
^{   i} x

Bu yerdan esa

_{j j} i1


_ n
_

f_{i } x_

x






i
f _ x_^
i1 _j

U _ x_  2 ^i1 1 ^  2W ^_ x_ f _ x_



_
_ n
_i1
f_{i } x_
x_n



f_{i } x_^


^{bu yerda W } ^x

• 
  transponirlangan Yakob matritsasi.
  

Shularga ko‘ra quyidagi natijaga kelamiz:
_ f ^p ,W_pW_p^ f ^{ p} _

  _
_p  2_p  _{W W  f  p,}
, (41)
W W ^ f ^p

p p p p
bu yerda soddalik uchun quyidagicha yozuv qabul qilingan:

f ^^p^ f x^^p^; Wp  W x^^p^, bularga ko‘ra x ^p^^1  x ^p  pWp f  ^p ,  p  0, 1, 2, . (42) Gradiyent usuli algoritmining blok-sxemasi 9-rasmda tasvirlangan.