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

1.3   Gradiyentli usullar. Eng tez tushish usuli 

 

Gradiyentli  usullarning  asosida  minimumni  qidirish  uchun  nafaqat  maqsad 

funksiyasining  qiymatlaridan,  balki  uning  gradiyentining  ham  qiymatlaridan 

foydalanish  yotadi. Eslatib o‟tamiz:  gradiyent  vektori 

 

sathsirtiga  (chizig‟iga)  perpindikulyar  bo‟ladi  va  funksiyaning  o‟sish  yo‟nalishi 

tomonga  qaragan  bo‟ladi.  Qaralayotgan  nuqtadagi  gradiyentning  yo‟nalishi 

funksiyaning  eng katta o‟sish yo‟nalishidir. 

Gradiyentli  usullardan  biri  gradiyent  bo‟yicha  tushish  deb  atalib,  gradiyent 

yo‟nalishiga  teskari  yo‟nalish  bo‟yicha  o‟zgarmas  qadam  bilan  ko‟chish  va  hosil 

qilingan  nuqtada  maqsad  funksiyasining  qiymatini  hisoblashga  asoslangan.  Agar 

bu  qiymat  avvalgi  qiymatdan  kichik  bo‟lsa,  gradiyent  yangi  nuqtada  hisoblanadi. 

Agarda  maqsad  funksiyasining  qiymati  oshsa  yoki  o‟zgarmasa  avvalgi  nuqtadan 

ko‟chish  qadami  kichraytiriladi  va  barcha  hisoblashlar  takrorlanadi.  Iteratsiya 

jarayoni  ikkita  ketma-ket  iteratsiyadan  olingan  nuqtalar  orasidagi  masofa  berilgan 

miqdorgacha  kamayguncha,    yoki  maqsad  funksiyasining  qiymatlari  orasidagi 

yaqinlik  berilgan  aniqlikka  erishguncha  davom ettiriladi. 

    (3) 

Agarda 

gradiyent 

vektorining 

komponentalarini 

analitik 

ko‟rininshda 

ifodalash  mumkin  bo‟lmasa,  qaralayotgan  nuqtada  hosilani  markaziy  ayirmalar 

bilan  approksimatsiyalash  yordamida  ularning  taqribiy  qiymatlarini  toppish 

mumkin: 

 

bu yerda   - 

 o‟zgaruvchining  kichik  orttirmasi. 

Gradiyent  bo‟yicha  tushish  variantlaridan  biri  eng  tez  tushish  usulida 

qo‟llaniladigan  algoritmdir.Bu  algoritmda  gradiyent  tushish  traektoryasining  har 

bir  nuqtasida  emas,  faqat  avvalgi  iteratsiyada  berilgan  yo‟nalish  bo‟yicha 

---

harakatlanganda  funksiya  minimumiga  erishilgan  nuqtalarda  hisoblanadi.  Tushish 

 boshlang‟ich yaqinlashishdan 

) yo‟nalish b‟yicha 

 

tenglama  bilan  berilgan  to‟gri chiziq bo‟ylab amalga  oshiriladi. 

Tushish jarayonida   

 

biro‟zgaruvchili  funksiya  minimallashtiriladi.  Bir  o‟lchovli  optimallashtirishning 

natijasi

  nuqta iteratsiyaning2-qadamida 

 

to‟g‟richiziqbo‟ylab tushishda 

 

funksiyani  minimallashtirishning  boshlang‟ichnuqtasibo‟libxizmatqiladi. 

Iteratsion jarayon  (1) shart bajarilgunga  qadar davom ettiriladi. 

Iteratsiyani  maqsad  funksiyasi  qiymatlarining  yaqinligi  ta‟minlanguncha  ((3) 

shartga  qarang)davom  ettirish  ham  mumkin.Bundan  tashqari,  minimum  nuqtasida 

maqsad  funksiyasining  gradiyenti  nolga  teng.Shuning  uchun  gradiyent  modulining 

kichiklashuvi  ham  ko‟p  o‟lchovli  optimallashtirish  jarayonining  tugash  belgisi 

bo‟lib xizmat  qilishi  mumkin. 

Ta‟kidlab  o‟tamizki,  eng    tez  tushish  usuli  ko‟p  o‟lchopvli  funksiyalarni 

minimallashtirishning  eng avval  qo‟llangan  usullaridan  biridir. 

Bu  usulning  g‟oyasi  1845-yildayoq  Koshi  tomonidan  berilgan  edi.Sirt  sathlari 

yarim  o‟qlari  bir  xil  tartibga  ega  bo‟lgan  ko‟p  o‟lchovli  ellipsoidalarga  yaqin 

bo‟lgan  funksiyalarni  minimallashtirishda  eng  tez  tushish  metodi  boshqa 

gradiyentli  metodlar  bilan  bir  qatorda,  odatda,  koordinata  bo‟yicha  tushish usuliga 

nisbatan tezroq yaqinlashadi. 

Bu 

yerda 

qaralayotgan 

gradiyentli 

usullarning 

umumiy 

kamchiligi- 

minimallashtiruvchi  funksiya  sirtlarida  jarliklar  bo‟lganda  sekin  yaqinlashishidir. 

Gap  shundaki,  bu  holda  ishlatilayotgan  algoritmlar  uchun  foydalanilayotgan  lokal 

gradiyentlar  minimum  nuqtasining  yo‟nalishinihatto  taxminan  ham  ko‟rsatmaydi. 

---

Gradiyent  vektorlar  minimum  yo‟nalishiga  nisbatan  kuchli  ostsilliyatsiya  qiladi, 

ya‟ni  juda  qisqa  davrli  tebranish  hosil  bo‟ladi,natijada  tushish  traiktoryasi 

minimum  yo‟nalishiga  kichik  qadamli  egri-bugri  siniq  chiziqlar  (zigzag) 

ko‟rinishida  bo‟ladi. 

 

3-chizma. Gradiyentli tushishning traektoryasi 

 

3-chizmada  gradiyentli  tushishning 

 boshlang‟ich nuqtadan  

+100

, 

funksiyaning 

 nuqtadagi minimumiga  borish traektoriyasi  ko‟rsatilgan. 

Berilgan  maqsad  funksiyasining  sirti  jarlikni  saqlaydi.Bunda  traektoriyaning 

egri-bugriligi 

aniq  ko‟rinib  turibdi. 

 

nuqtaga 

qaralayotgan  misolda 

  iteratsiyada  kelinayapti.  Bu  yerdan  ko‟rinadiki 

yaqinlashishni  tezlashtirish  masalasiga  zarurat  tug‟iladi. 

---