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

Zeydel usuli

Oddiy iteratsiya usulining iteratsion jarayon yaqinlashishini tezlashtirituchi modifikatsiyalaridan biri Zeydel usuli bo‘lib, bu usulning asosiy formulasi quyidagicha ifodalanadi:

_x(k 1)
 ₁(x^(k) , x^(k) , ..., x^(k) ), ^

1 1 2 n _

_x(k 1)
 ₂ (x^{(k 1)} , x^(k) , ..., x^(k) ), ^

2 1 2
ⁿ  k  0,1,2,
, (25)

... ... ... ... ... ... ... ... _

_x(k 1) _{ }
(x^{(k 1)} , ...,
_x(k 1) _{, x}(k ) _),^

n ⁿ 1
n1
n ^

Bu iteratsion jarayon bilan bir qatorda ushbu
f₁( , x^(k), ..., x^(k) )  0, ^
2 n _
f₂ (x^{(k 1)},  , ..., x^(k) )  0, ^

1 n _
(26)

... ... ... ... ... ... ... ... _
f (x^{(k 1)}, ..., x^{(k 1)},  )  0^
n ₁ n1 ^_

x
iteratsion jarayonni qarab, yaqinlashish vektori komponentalarini shu tenglamalar sistemasidan topish mumkin. Bu tenglamalar sistemasining har birida bitta  noma’lum qatnashadi. Ana shu ₁ larning qiymatlari (26)

tenglamalar sistemasining yangi birinchi
(k 1) 1
= ₁ yaqinlashishi qiymati

to‘plami bo‘lib xizmat qiladi. Navbatdagi ₂ lar esa ikkinchi

yaqinlashishning qiymatlar to‘plamini beradi, ya’ni
x^{(k 1)} =  va hokazo.

2
2

Bu usulning qulayligi shundaki, uni bitta tenglama yechimini topishga qo‘llash juda oddiy, ammo bu usul amaliyotda juda katta hajmdagi hisoblashlarni bajarishni talab qilishi mumkin.


Xususiy hol. Ikki noma’lumli ikkita nochiziqli tenglamalar sistemasini taqribiy yechish uchun ba’zi hollarda (22) iterasion hisoblash jarayoni o‘rniga quyidagi «Zeydel jarayoni»dan foydalanish juda qulay:
x_n1  ₁x_n , y_n , _

^yn1
 ₂
^xn1
, y_n 
_ n  0,1,2,3,... .


2. Parametrlarni qo‘zg‘atish usuli

Bu usulning g‘oyasi quyidagicha. Dastlab (1) tenglamalar sistemasi bilan bir qatorda avvaldan uning yechimi ma’lum bo‘lgan quyidagi biror tenglamalar sistemasi qaraladi:

h⁽⁰⁾ (x , x , ..., x )  0,^
1 1 2 n _
h⁽⁰⁾ (x , x , ..., x )  0,_

2 1 2 n _
(27)

... ... ... ... ... ... ... ... _
h⁽⁰⁾ (x , x , ..., x )  0.^
n 1 2 n 
Bunga misol qilib chiziqli algebraik tenglamalar sistemasini olish mumkin.

27. 
    tenglamalar sistemasinining chap tarafini shunday o‘zgartiramizki, u biror K songa nisbatan (1) tenglamaning chap tarafiga qo‘yilib, uni quyidagi ko‘rinishga keltirsin:
    

_h(k 1) _{(x , x}
, ..., x )  h^(k) (x , x , ..., x )  ^

1 1 2
n 1 1 2 n _

• 
  f (x , x
  

, ..., x
)  h^(k) (x , x
, ..., x
_)k  1_,

1 1 2
n 1 1 2
n _{K }

_h(k 1) _{(x , x}
, ..., x )  h^(k) (x , x , ..., x )  ^

2 1 2
n 2 1 2 n _

 f
(x , x
, ..., x
)  h^(k) (x , x
, ..., x
_)k  1_,^

27. 
    

... ... ... ... ... ... ... ...

2 1 2
n 2 1 2 n ^

K



_h(k 1) _{(x , x}
, ..., x )  h^(k) (x , x , ..., x )  ^

n 1 2
^{n n 1 2 n} 

 f
(x , x
, ..., x
)  h^(k) (x , x
, ..., x
_)k  1_,^

n 1 2
n n 1 2 n ^



K


bu yerda k = 0,1,…,K. Agar K ning qiymati kattaroq tanlansa bu funksiyalar qiymatlarining ketma-ket o‘zgarishi kichrayib boradi. Har bir o‘zgartirishdan keyin parametrlari qo‘zg‘atilgan ushbu

_h(k 1) _{(x , x}
, ..., x
)  0,^

1 1 2 n _

_h(k 1) _{(x , x}
, ..., x
)  0,_

2 1 2 n _

27. 
    

... ... ... ... ... ... ... ... _

_h(k 1) _{(x , x}
, ..., x
)  0 ^

n 1 2 n 
tenglamalar sistemasi iteratsion usullar bilan yechib boriladi.

(27) tenglamalar sistemasining yechimi (29) uchun k = 0 da boshlang‘ich yaqinlash deb foydalaniladi. (29) tenglamalar sistemasining yechimi (27) sistema yechimidan kam farq qilganligi uchun iteratsion jarayonning yaqinlashishi ta’minlanadi deb hisoblashimiz mumkin. Shundan keyin olingan yechim (29) sistemaning k = 1 dagi boshlang‘ich yaqinlashishi deb qaraladi va hokazo. Oxiriga borib, k = K-1 bo‘lganda hosil bo‘lgan (29) tenglamalar sistemasi dastlabki (1) tenglamalar sistemasiga ekvivalent bo‘lib qoladi.
Shunday qilib, parametrlarni qo‘zgatish usulining boshlang‘ich yaqinlashishini tanlash masalasi yechiladi.
Bu usulning noqulayligi shundaki, (27) tenglamalar sistemasini yechiladigan tenglamalar sistemasiga aylantirish katta hisob qadamlarini (hatto 10 dan 100 gacha) talab qilishi mumkin. Shuning ushun, bu usulning qo‘llanilishi mashinada juda katta hisob vaqtini talab qilishi mumkin. Bu usulning afzalligi shundaki, (28) sistema muvaffaqiyatli yechilganda (29) sistemaning yechimi bir necha iteratsiya qadamlardagina topilishi mumkin.

2. Pikar iteratsiyalari

Bir qator hollarda (1) sistema maxsus ko‘rinishga ega bo‘lib, u vektor- matritsa ko‘rinishida quyidagicha yoziladi:

Ax  f(x) = 0, (30)
bu yerda A – berilgan aynimagan matritsa; f – nochiziqli vektor-funksiya. Bunday tenglamalar sistemasiga, masalan, nochiziqli chegaraviy masalalarni chekli ayirmalar usuli bilan yechishda kelinadi.
(30) sistema uchun quyidagi iteratsion prosedura o‘rinli:

_x(k 1)
 A^1 f x^{(k )} 
(31)

va u Pikar iteratsiyalari deb ataladi. Iteratsion algoritmni ixcham yozish maqsadida (31) formulada A^-1 teskari matritsadan foydalanildi. Aslida esa iteratsiyaning har bir qadamida quyidagi chiziqli algebraik tenglamalar sistemasi yechiladi:

_Ax(k 1) _
f x^(k) .

Pikar iteratsiyalarini quyidagi umumlashgan iteratsiyon jarayonning xususiy holi deb qarash mumkin:
^{x(k 1)  x(k )  BFx(k ) }, (32)
bu yerda B – berilgan aynimagan matritsa. Bu yerdan ko‘rinadiki, agar

Fx  Ax 
f (x)
va B  A^1

bo‘lsa, u holda (32) tenglik (31) ga aylanadi. Agar B matritsa boshqacharoq tanlansa, u holda boshqa bir necha algoritmlar yuzaga keladi, xususan, Nyuton usuli algoritmlari va ko‘p o‘chovli kesuvchilar usuli.

2. Broyden usuli

Nyuton-Rafson usuli juda yaxshi yaqinlashishni beradi, ammo Yakob matritsasining teskarisini hisoblash juda ko‘p mashina vaqtini oladi. Bunday hollarda Yakob matritsasini hisoblash o‘rniga biror boshqa yaqinlashishni tuzish uslubi kvazinyuton usullar (algoritlar) deb ham ataladi. Ana shunday usullardan biri bu 1965 yilda taklif etilgan Broyden usuli bo‘lib, u Nyuton-Rafson usulining takomillashtirilgan varianti hamda u yuqorida ta’kidlangan kamchilikdan holi. Bu usulning quyidagi ikkita muhim farqlari mavjud:

1. 
   iteratsiyalarning har bir qadamida Yakob matritsasi to‘g‘risi yoki teskarisi hisoblanmaydi, o‘zgaruvchilar chetlashishini sonli baholash uchun qo‘shimcha funksiyalar hisoblanilmaydi, faqatgina sxema o‘zgarmas matritsasining mavjudligini topishdagi funksiyalardangina foydalaniladi;
   
2. 
   yechimning yaqinlashishini ko‘rsatuvchi so‘nish koeffitsiyenti har bir iteratsiyada hisoblanadi, bu o‘z navbatida, Broyden usulining yutug‘i bo‘lib, Nyuton-Rafson usuli yaqinlashishni kafolat bera olmaydi. Bundan tashqari, bu koeffitsiyent hatto, hali yechim topilmagan bo‘lsa ham, hisoblash xatoligini baholash imkonini beradi.
   

Broyden usulining mazmuni quyidagicha:

Nyuton-Rafson formulasi bo‘yicha navbatdagi x^(k+1) yaqinlashishni olish uchun k-yaqinlashishga tuzatma vektor qo‘shiladi, ya’ni:

_x(k 1) _{  W} (k ) _^1 _f (k ) _;
x(k 1) _{ x}(k ) _{ x}(k 1) _.

Broyden usulida bu tuzatmaning hammasidan emas, balki uning bir qismidan foydalanilmaydi:

bu yerda

_(k )
_x(k 1) _{ x}(k ) _{ }(k )_x(k 1) _,

• 
  skalyar koeffitsiyent shunday tanlanadiki,
  

_f (k 1)

vektor yoki

uning maksimal qiymat qabul qiluvchi elementi normasi minimumlashtiriladi (yoki kamaytiriladi). Agar Nyuton-Rafson usulining
yaqinlashishi ta’minlangan bo‘lsa, u holda ^(k) >1 ni tanlash hisobiga
Broyden usuli juda katta yaqinlashishga erishadi. Aksincha, agar Nyuton-

Rafson usulining yaqinlashishi ta’minmalangan bo‘lsa, u holda tanlash hisobiga bu yaqinlashish ta’minlanadi.
^(k) <1 ni

Broyden usuli Yakob matritsasi va uning teskarisini hisoblash bilan bog‘liq bo‘lgan Nyuton-Rafson usulining qiyinchiligini bartaraf qiladi. Bunga iteratsiyaning har bir qadamida Yakob matritsasining o‘rniga quyidagi formula bilan berilgan yaqinlashishni hisoblash evaziga
erishiladi:

_H (k 1) _{ H} (k ) _
(k )_x(k ) _{ H} (k ) _f (k 1) _
f (k ) _{x}(k ) _^T _H (k )

(33)

_x(k ) _^T _H (k ) _f (k 1) _
Broyden usulining algoritmi quyidagicha:

1. 
   x⁽⁰⁾ boshlang‘ich yaqinlashish tanlanadi.
   

_f (k ) _

2. 
   Yakob matritsasi W⁽⁰⁾ ning teskarisini hisoblash bilan H⁽⁰⁾
   

matritsaning boshlang‘ich qiymati hisoblanadi.

3. 
   f ^(k)  f x^(k)  , k=0,1,2, … hisoblanadi.
   

_{4. x}(k ) _{ H} (k ) _f (k )
hisoblanadi.

_{5. }(k )
koeffitsiyent shunday tanlanadiki,
_f (k 1) _
f (k )
bo‘lsin.

_{6. x}(k 1) _{ x}(k ) _{ }(k )_x(k 1)
hisoblanadi.

_{7. f} (k 1)
matritsa normasining yaqinlashishi tekshiriladi.

_{8. f} (k 1) _
f ^(k)  hisoblanadi.

_{9. H} (k 1)
matritsa (33) formula bo‘yicha hisoblanadi.

10. 
    Hisoblash jarayoni 3-qadamdan takrorlanadi.
    

1-misol. Ushbu




f₁ x, y  x⁵  y³  xy 1  0^

f₂ x, y  x² y  y  2  0 _

tenglamalar sistemasining nolinchi yaqinlashishini
X₀  (x₀ , y₀ )
= (2; 2)

deb olib, uning aniq yechimi yordamida aniqlang.