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

Iteratsiyalar usuli (ketma-ket yaqinlashishlar usuli)

Yuqoridagi (1) nochiziqli tenglamalar sistemasi ushbu

x₁  ₁(x₁, x₂ , ..., x_n ), _
x   (x , x , ..., x ),^
2 2 1 2 n ^


... ... ... ... ... ... ... ... ^
(15)

x_n  _n (x₁, x₂ , ..., x_n ) ^_

ko‘rinishga keltirilgan bo‘lsin, bu yerda ₁,₂,
- haqiqiy funksiyalar

1 2
bo‘lib, ular bu sistema izolyatsiyalangan _x^, x^,
yechimining biror

atrofida aniqlangan va uzluksiz.
Qulaylik uchun quyidagi vektorni kiritamiz:
^{x }  ^x₁^{, x}₂^, va ^  ^x ^ _^1 ^x^,2  ^x^{, ,n}  ^x_ .
U holda (15) ni quyidagi vektor shaklida yozish mumkin:
^{x  }  ^x^{. (16)}

(16) tenglamaning
x^  _x^, x^,
vektor-ildizini topish uchun

1 2
ko‘pincha quyidagi iteratsiyalar usulini qo‘llash juda qulay:

yoki
_x^{k 1} _{  x}^k  _,
k  0,1,2,
, (17)

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

1 1 2 n _

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

2 1 2
n ^ k  0,1,2, ,

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

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

n ⁿ 1 ²
n ^

bu yerda yuqoridagi indeks iteratsiyalar yaqinlashishi nomerini bildiradi;

_x⁰ _{ x}

• 
  boshlang‘ich yaqinlashish. Usulning blok-sxemali algoritmi 5-
  

rasmda tasvirlangan.

Agar (17) iteratsion jarayon yaqinlashivchan bo‘lsa, u holda ushbu   lim x^^k^(18) k  limitik qiymat (17) tenglamaning ildizi bo‘ladi. Haqiqatdan ham, agar (18) munosabat bajarilgan desak, u holda (17) tenglikda k  bo‘yicha limitga o‘tib,   x funksiyalarning uzluksizligidan quyidagiga ega bo‘lamiz: lim x^^k^^1^  lim x^^k^, k  k  ^ya’ni^^^^^. Shunday qilib,   bu (16) vektor tenglamaning ildizi. Agar, bundan tashqari, barcha x^^k^ ^k^^0,1, ^yaqinlashishlar^biror^^-sohaga tegishli bo‘lsa, u holda   x^ ekanligi

5-rasm. Nochiziqli tenglamalar sistemasini yechish uchun iteratsiyalar usulining blok-sxemali algoritmi.

yaqqol ko‘rinadi.
Soddaroq qilib aytganda, (17) iteratsion jarayon


_x⁰ ₌

x⁽⁰⁾ , x⁽⁰⁾ , ..., x⁽⁰⁾ 

• 
  boshlang‘ich yaqinlashishdan boshlanib, bitta
  

1. 
   2 n
   

iteratsiyadan keyin barcha argumentlar orttirmasining moduli berilgan ε
miqdordan kichik bo‘lmaguncha davom ettiriladi, ya’ni

_x(k 1) _{ x}(k )
 max x^{(k 1)}  x^{(k )}   .

^ 1in ^{i i}
Bu shartga teng kuchli bo‘lgan quyidagi shartdan ham foydalanish mumkin:

_x(k 1) _{ x}(k )
_{ x}(k 1) _{ x}(k )
 max ^
_x(k 1) _{ x}(k ) _^{2 } _{ }

 _{i i} 
² 1in ^{ }
Oddiy iteratsiya usuli dasturlash uchun juda qulay, ammo u quyidagi muhim kamchiliklarga ega:

1. 
   ^(x) _  q  1, bu yerda ’ - vektor-funksiya  ning Yakob
   


matritsasi,
 _ belgi bilan esa matritsa normasi kiritilgan:

^(x)
 max ^ n
^{i } _;

^ 1in ^^{ x }

2. 
   
   _ j 1
   
   l
   
   j _
   ^(x)  q  1, bu yerda ’ - vektor-funksiya  ning Yakob
   



l
matritsasi, belgi bilan esa matritsa normasi kiritilgan:

^(x)
 max ^ n
^{i }_;

^l 1 j n ^^{ x }

3. 
   
   _i 1
   
   j _
   agar boshlang‘ich yaqinlashish aniq yechimdan uzoqroq tanlangan bo‘lsa, u holda a) shart bajarilishiga qaramasdan, usulning yaqinlashishiga kafolat yo‘q; demak, boshlang‘ich yaqinlashishni tanlashning o‘zi ham sodda emas ekan;
   
4. 
   iteratsion jarayon juda sekin yaqinlashadi.
   

Oddiy iteratsiya usuli

Iteratsiyalar usulini dastlabki
f _ x_  0
umumiy sistemaga ham

qo‘llash mumkin, bu yerda
f _ x_

• 
  vektor-funksiya bo‘lib, izolyatsiya-
  

langan x^ - vektor-ildiz atrofida aniqlangan va uzluksiz.
Masalan, bu sistemani quyidagi ko‘rinishda yozaylik:
x  x  f _ x_
bu yerda   xosmas matritsa. Quyidagi belgilashni kiritamiz:
^{x  f}  ^x ^{ }  ^x ^{. (19)}
U holda quyidagiga ega bo‘lamiz:
^{x  }  ^x^{. (20)}

Agar
f _ x_
funksiya
f ^_ x_

• 
  uzluksiz hosilaga ega bo‘lsa, u holda
  


(19) formuladan quyidagi tenglik kelib chiqadi:
^_ x_  E  f ^_ x_.

Agar
^_ x_
o‘zining normasi bo‘yicha kichik bo‘lsa, u holda (20)

tenglama uchun iteratsiyalar jarayoni tez yaqinlashadi. Bu holatni e’tiborga olib, Λ matritsani shunday tanlaymizki, ushbu
^_x^0 _  E  f ^_x^0 _  0

tenglik bajarilsin. Bu yerdan, agar quyidagi tenglikka ega bo‘lamiz:
_{f x}⁰ _
- xosmas bo‘lsa, u holda

  
Shuni ta’kidlash muminki,
_{f x}⁰ _^1 _.
bu mazmunan Nyuton modifikatsion

jarayonining (19) tenglamaga qo‘llanilishi demakdir.

Xususan, agar

det
f ^_x^0 _  0

bo‘lsa, u holda boshqa

_x⁰ _-

boshlang‘ich yaqinlashishni tanlash lozim bo‘ladi.
Oddiy iteratsiya usuli nafaqat haqiqiy ildizlarni, balki kompleks ildizlarni ham topish imkonini beradi. Oxirgi holda kompleks boshlang‘ich yaqinlashishni tanlash lozim bo‘ladi.
Iteratsiyalar jatayoni yaqinlashishining yetarli sharti quyidagicha.
Faraz qilaylik, shunday DRⁿ yopiq soha mavjud bo‘lsinki, bunda ixtiyoriy xD uchun (x)D bo‘lsin. Xuddi shunday, ixtiyoriy x₁ va x₂D lar uchun quyidagi shart bajarilsin:

(x₁)  (x₂)
 q x₁  x₂ ,
q  1,
(*)

bu yerda 
- Rⁿ dagi biror norma. U holda osongina ko‘rsatish mumkinki,

D sohada (16) tenglamaning x^* yechimi mavjud bo‘lib, (17) iteratsion jarayon tanlangan ixtiyoriy x₀D uchun shu yechimga yaqinlashadi. Bunda quyidagi yaqinlashish tezligini baholash o‘rinli:

bu yerda c – biror o‘zgarmas.
x^m  x^*
_ cq^m _,
1  q

Yuqoridagi (*) shartni qanoatlantiruvchi  funksiya siqiluvchan akslanish deb, (18) tenglamaning yechimi esa  funksiyaning qo‘zg‘almas nuqtasi deb ataladi.

Shuni ta’kidlaymizki,
_xm1 _{ x}*


 (x^m )  (x^*)


 q x^m  x^* ,

shuning uchun, oddiy iteratsiya usulining yaqinlashish tartibi 1 ga teng.

Agar (x) funksiya D sohada uzluksiz va differensiallanuvchan bo‘lsa, u holda (*) shartning bajarilishi uchun ixtiyoriy xD lar uchun
^{(x)  q  1} shartning bajarilishi yetarli.
Izoh. (x) funksiya f(x) funksiya orqali bir qiymatli aniqlanmaydi.

^(x)
 q  1
shartning bajarilishi uchun (x) funksiyani qanday tanlash

lozim? Agar x⁽⁰⁾ nuqta atrofida f(x) uzluksiz differensiallanuvchan va

f ^_ x_
matritsa-funksiya aynimagan bo‘lsa, unda umumiy holda

quyidagicha yozish mumkin:
(x)  x 


f (x) _.
f '(x₀ )

Xususiy hollarda (x) funksiyani tanlash va ushbu
^(x)
 q  1

shartning bajarilishini tekshirish ancha sodda bo‘lishi mumkin.


Xususiy hol. Hisoblashlarni amaliyot uchun qulay bo‘lgan n=2 bo‘lgan holda ko‘rib chiqaylik. (15) sistemani


x  ₁x, y,_

y  ₂
x, y^
(21)

ko‘rinishda yozib olamiz.
₁ x, y, ₂ x, y
funkiyalar iterasiyalovchi

funksiyalar deb yuritiladi. Taqribiy yechimni topish algoritmi ushbu
x_n1  ₁x_n , y_n , _

^yn1
 ₂
x_n
, y_n 
_ n  0,1,2,3,.....

(22)

ko‘rinishda beriladi. Bu yerda ^{x0 , y0 }

• 
  birinchi yaqinlashish qiymatlari.
  

(22) iterasion hisoblash jarayoni yaqinlashuvchi bo‘ladi, agarda ushbu


_{2 }
x
 q₁


 q₂
 1, ^





 1 ^
(23)

tengsizliklar bajarilsa.
Xususiy va umumiy holda (x) funksiyaning grafigini qurish va iteratsion jarayonning R² dagi yaqinlashishini ta’minlovchi shartni tekshirishga oid misollar qaraylik.

1. 
   misol. Quyidagi sistemani qaraylik:
   


^ f (x, y)  x  ¹ cos y  0.3  0,

 _{1 3}

f₂ (x, y)  y  sin( x  0.6) 1.6  0.