Alisher navoiy nomidagi samarqand davlat universiteti mexanika – matematika fakulteti «Hisoblash usullari»

1.4 Nyuton usuli. Kvazinyuton usullari 

 

Ko‟p  o‟zgaruvchili  funksiyalarni  minimallashtirish  masalalarini  echishing 

Nyuton  usuli  bir  o‟lchovli  optimallashtirish  usullarining  umumlashmasidir. 

Minimallashtiriluvchi  funksiyaga  nisbatan  ba‟zi  talablar  qo‟yilganda  bu  usul 

gradiyent  usullarga  qaraganda sezilarli  darajada tezroq yaqinlashadi. 

Ko‟p  o‟lchovli  Nyuton  usuli  algoritmini  2  o‟lchovli  hol  uchun 

asoslaymiz:

  maqsad  funksiyasining 

  nuqta  atrofidagi  Teylor  qatori 

quyidagi  ko‟rinishda bo‟ladi: 

 

(4 a) 

 

Bu  yerda  barcha  hosilalar 

  nuqtada  hisoblanadi.(4  a)  ifodani  vektor-

matritsa  ko‟rinishida  ham yozish mumkin.Buning   uchun 

 

elementliH  kvadrat  matritsani  (Gesse  matritsasini)  vasiljishlarning

 

vektor-ustunini  kiritamiz.  Natijada  (4 a) ifoda 

 

ko‟rinishda yoziladi.  (4 b) formula n o‟lchovli holda ham o‟z shaklini  saqlaydi. 

Agarda  (4  b)  ifodada 

  bo‟yicha  2-tartibgacha  qo‟shiluvchilarnigina 

qoldirsak u holda 

 maqsad funksiya 

 

---

kvadratik  forma  bilan  almashinadi.  Maqsad  funksiyasining  minimumiga  yangi 

yaqinlashishni  hosil  qilish  uchun 

ni  minimallashtiramiz,  buning  uchun 

uning bo‟yicha  gradiyentini  hisoblaymiz: 

 

vauni  nolga  tenglashtiramiz.  Natijada   

vektorningkomponentalariga  nisbatan 

chiziqli 

algebraik 

tenglamalar 

sistemasini 

hosil 

qilamiz, 

bu 

yerda 

nuqtadan yangi 

 nuqtaga siljish  vektoridir: 

                                      (5) 

(5)  tenglama  Nyuton  tenglamasi  deb  ataladi.  Bu  teglamaning  yechimi  yangi 

yaqinlashishni   

 .                                              (6) 

ko‟rinishda aniqlash  imkonini  beradi. 

Agarda  (5)  tenglamaning  yechimini  formal  ravishda  Gesse  matritsasining 

teskarisi     

 orqali yozsak: 

 

u holda ko‟p o‟lchovli Nyuton usulining  iteratsion  formulasi  quyidagicha  bo‟ladi: 

                                   (7) 

Lekin  bu  algoritmni  formal  yozishdan  boshqa  narsa  emas.Nyuton  usuli  bilan 

hisoblashlarni  amaliy  amalga  oshirish  uchun  (5)  tenglamalar  sistemasini  Gesse 

matritsasining  teskarisini  oshkor ko‟rininshda tuzmasdan echish kerak. 

Ko‟p  o‟lchovli  Nyuton  usuli  xuddi  bir  o‟lchovli  holdagidek minimum nuqtasi 

atrofida kvadratik  yaqinlashish  xossasiga ega bo‟ladi. 4-chizmada  

 

funksiyaning  minimum  nuqtasiga  Nyuton  usuli  bilan  tushish  traektoriyasi 

keltirilgan.  Bu  holda 

  nuqtadan

    nuqtagacha 

o‟tish uchun bor yo‟g‟i 4 taiteratsiya talab qilinadi. 

---

 

4-chizma. Nyuton usuli traektoriyasi 

 

Biroq  Gesse  matritsasini  hisoblash  zarurligi  Nyuton  usulining  amaliy 

tadbiqini  ancha  qiyinlashtiradi.  Albatta,  bu  yerda  ham  xuddi  bir  o‟lchovli 

xoldagidek  2-hosilani  chekli  ayirmalar  bilan  approksimatsiyalash  mumkin,  lekin 

bu  ish  no‟lchovli  hol  uchun  funksiya  qiymatlarini 

  ta  qo‟shimcha  hisoblashni 

talab  qiladi.  Agarda  funksiyaning  ko‟rinishi  murakkab  bo‟lsa  bu  juda  ko‟p  vaqtni 

talab qiladi. 

Usulning  yana  bir  muhim  kamchiligi  shundaki  har  bir  iteratsiyasida  n  ta  (5) 

chiziqli  tenglamalar  sistemasini  yechish  zarurligidir,  bunda  har  bir  holda 

  ta 

arifmetik  amal  bajarishga  to‟g‟ri  keladi,n  ning  katta  qiymatlarida  bitta  iteratsiyada 

shuncha ishni  bajarish  qiyinlik  qiladi.   

Hozirgi  paytda  Nyuton  usulining  modifikatsiyalari  ishlab  chiqilgan.  Bu 

modifikatsiyalarda  Gesse  matritsasining  teskarisini  hisoblash  talab  qilinmaydi  va  

yaqinlashish  tezligi  saqlanib  qoladi.  Bunday  usullar  guruhi  kvazinyutonusullari  deb 

ataladi.Shulardan    eng  taniqlilaridan  biri  Devidon-Fletcher-Pauel  usulidir.  Bu 

---

usulda  (7)  algoritmdan  farqli  ravishda,  har  bir  iteratsiyada  tushish 

ning 

yo‟nalishida  olib  boriladi,  bu  yerda 

-munosabat  aniqlanganmusbat  matritsa 

bo‟lib har bir qadamda yangilanadi  va limitda  Gesse teskari matritsasiga  intiladi.