O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi farg’ona davlat universiteti raqamli texnalogiya fakulteti

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.

5.