7.2.2 Минимумды анықтаудың белсенді әдістері
Пассивті іздеу әдісінен ерекше, есептеу барысында алдын ала алынған ақпараттар пайдаланылатын әдістер кездеседі. Мұндай әдістер жалпы түрде минимумды іздеудің белсенді әдістері (немесе біртіндеп іздеу әдістері) деп аталады.
Осы
әдістер келесі сұлбаға негізделеді.
Бірін-бірі қамтитын төңіректеу
кесінділерінің
тізбегі құрылады:
,
,
мұндағы
.
Егер
болса, онда
.
Практикада төңіректеу
кесінділерінің
осындай тізбегін білу қажетті дәлдіктегі
минимумды төңіректеуге мүмкіндік
береді. Мысалы, егер қандай да бір
саны берілсе, онда
теңсіздігі орындалатындай
мәнінде
кесіндісінің кез келген
нүктесін есептің жуық шешімі деп
есептеуге болады. Бұл жерде
.
Біртіндеп
іздеу әдістері
,
кесінділер тізбегін құрумен ерекшеленеді.
Дербес жағдайда, алынған төңіректеу
кесінділерінде
пассивті іздеуді бірнеше рет қайталау
біртіндеп іздеу нұсқаларының бірі болып
табылады. Мысалы, егер әрбір
қадамда
деп ұсынсақ, яғни
,
,
,
және
онда
нүктелері төңіректеу
кесіндісін
4 бірдей бөлікке бөледі. Демек, жаңа
төңіректеу
кесіндісінің
ұзындығы
кесіндісінің ұзындығынан 2 есе (кей
жағдайда 4 есе кіші болуы мүмкін) кіші
болады.
Төңіректеу
кесіндісін
қысқартудың жоғары жылдамдылығы (әрбір
итерацияда, оның ұзындығы кем дегенде
екі есе кішірейеді) осы әдістің қолайлы
жағдайы болып есептеледі. Берілген
дәлдікке жету үшін қажетті
итерация санын есептеу оңай болады.
Шыныда да, кез келген
үшін
қатынасы орындалатындықтан,
саны
теңсіздігі орындалатын
-ның
ең кіші мәні болады. Сонымен,
.
Әрбір итерацияда алдыңғы итерациядан
қалған
,
,
үш нүктеге
,
жаңа нүктелерін қосып,
,
функцияларының мәнін есептеудің
қажеттілігі әдістің қолайсыз жері болып
есептеледі.
Әрі қарай әрбір қадамда белгілі түйіндерге тек қана бір жаңа түйін қосуға мүмкіндік беретін төңіректеу кесіндісін құру мүмкіндігін қарастырамыз.
Теорема
8.2 (функцияның
кесіндісіндегі унимодальдылық қасиеті)
қатынасы орындалатындай
,
нүктелері бар болсын. Егер
болса, онда
кесіндісі, егер
болса, онда
кесіндісі
төңіректеу
кесіндісі
болып табылады.
Теорема
8.3
(
унимодальды функциясын минимизациялау
әдісінің принципиальды сұлбасы).
унимодальды функция үшін
төңіректеу
кесіндісі
белгілі болсын.
,
төңіректеу
кесінділері
құрылсын.
кесіндісін табу тәсілін сипаттайық.
Қандай да бір тәсілмен
теңсіздігін қанағаттандыратын
,
сандары табылсын. Егер
болса,
,
деп ұсынамыз. Кері жағдайда
,
деп ұсынамыз.
Осы сұлбаның аясындағы әдістердің негізгі айырмашылығы – , нүктелерін есептеудің ережелерінің әр түрлілігінде. Көптеген әдістерде , нүктелері төңіректеу кесіндісінің ортасына қатысты симметриялы орналасады. Осындай әдістерге мысалы дихотомия, алтын қима, Фибоначчи және т.б. әдістерді жатқызуға болады.
8-лекция. Дихотомия әдісі
Бір
айнымалы функцияны минимизациялау
есебінде
төңіректік минимум нүктесі жататын,
сызықтық функция унимодальды болатын
аралығы анықталсын.
Унимодальдылық аралықты тарылту үшін кесіндісінің ортасына симметриялы орналасқан және нүктелерін пайдаланамыз:
.
саны
1 санынан едәуір кіші деп есептейік.
Сонда
,
нүктелері
кесіндісінде жатады және кішірейтілген
аралығын аламыз. Мүмкін болатын келесі
үш жағдайдың әрқайсысында кішірейтілген
кесіндінің ұзындығын бағалаймыз:
1.
,
,
;
2.
,
,
;
3.
,
,
,
.
Осылайша түрлендірудің бірінші қадамынан кейін ұзындығы кішірейген унимодальдылық аралығы табылады.
Егер
шамасы өте аз болса, онда 1-ші және 2-ші
жағдайларда унимодальдылық
кесіндісінің ұзындығы екі есе дерлік
кішірейеді.
Енді
жаңа кішірейген
аралығында осы кесіндінің ортасына
симметриялы
,
нүктелерін таңдаймыз:
.
Кішірейген
аралығын тапқанымыз секілді есептеулерді
жүргізе отырып ұзындығы
шамасынан артық болмайтын
аралығын аламыз, және т.т.
Нәтижесінде,
функциясының
төңіректік минимум нүктесі әрқайсысында
жататын және
,
,
тізбектерінің ортақ шегі болатын,
бірінің ішінде бірі орналасқан
,
,
,
...,
,
... кесінділер тізбегін аламыз.
Осыдан
жуық теңдігін аламыз, оның
-ші
қадамдағы дәлдігі
(8.3)
теңсіздігімен бағаланады.
(8.3) теңсіздіктен берілген дәлдікке жету мақсатында қадам санын анықтауға болады:
.
. (8.4)
Бұл әдісте әрбір итерацияда төңіректеу кесіндісі екі есе дерлік кішірейеді. Сондықтан кейбір әдебиеттерде бұл әдісті қақ бөлу әдісі деп айтады. Әрине, бұл әдістің артықшылығын көрсетеді. Сонымен қатар, (8.4) қатынастан берілген дәлдіктегі есептің жуық шешімін табу үшін итерация санын алдын ала есептеге болады.
8.2-мысал.
кесіндісінде
берілген
функциясының минимумын
дәлдікпен, дихотомия әдісін пайдаланып
анықтау керек.
Шығарылуы. теңсіздігін пайдаланып ең аз қадам санын анықтаймыз:
,
.
.
,
,
,
,
белгілеулерін
енгіземіз, мұндағы
,
,
,
– есептеудің
-ші
қадамында алынған кесіндінің басының
және соңының координаталары,
және
–
кесіндісіне тиісті.
Біртіндеп есептеулерді жүргіземіз.
.
,
.
,
.
,
,
.
1.
.
,
,
,
,
.
2.
.
,
,
,
,
.
3.
.
,
,
,
,
.
4.
.
,
,
,
,
.
5.
.
,
,
,
,
.
6.
.
,
,
,
,
.
7.
.
.
Алынған есептеулерді кестеге енгізейік:
Итерация саны |
|
|
|
|
|
|
|
|
0 |
-2 |
3 |
0,25 |
0,75 |
1,1992 |
|
-5,4883 |
5 |
1 |
0,25 |
3 |
1,4875 |
1,7625 |
-23,0296 |
|
-28,2278 |
2,75 |
2 |
1,4875 |
3 |
2,1681 |
2,3194 |
-28,885 |
|
-25,6452 |
1,5125 |
3 |
1,4875 |
2,3194 |
1,8618 |
1,945 |
-29,3645 |
|
-29,8945 |
0,8319 |
4 |
1,8618 |
2,3194 |
2,0677 |
2,1135 |
-29,8286 |
|
-29,5066 |
0,4576 |
5 |
1,8618 |
2,1135 |
1,9751 |
2,0002 |
-29,978 |
|
-30 |
0,2517 |
6 |
1,975 |
2,1135 |
2,0374 |
2,0512 |
-29,9487 |
|
-29,9029 |
0,1385 |
7 |
1,9751 |
2,0512 |
|
|
|
|
|
0,0761 |
Кестеден
көріп отырғанымыздай, берілген
дәлдікке
итерацияның 7-қадамында жетеміз.
Төңіректік минимум нүктесі –
аралығында,
,
.
Жауабы.
,
.