9 Сурет – Функцияларды сканирлеумен зерттеу графигі: a,b – анықсыздық интервалының шекарасы

Іздеудің басқа әдістері тиімдірек, бірақ сканирлеу ие болатын әмбебаптық оларда болмайды. Олардың тиімділіктері бағытты іздеу әдістері болуымен байланысты, олар факторлық кеңістікті зерттеп қана қоймайды, сонымен қатар ізделетін экстремум жағына қарай осы кеңістікте қозғалуда өтеді. Дегенмен іздеудің бағыттылығы әдістердің қолданылуын шектейтін бірқатар шарттардың сақталуын талап етеді.

Бәрінен бұрын, бағытты іздеу сенімді нәтиже береді, егер функция унимодалды болса. Унимодалды функция ұйғарынды аймақта қажетті белгінің бір экстремумын ғана береді (бір максимум, егер максимум іздесек, бір минимум, егер минимум іздесек).

F 2 1

3

X

a b

10 Сурет – Унимодалды және унимодалды емес функциялар:

a,b – ұйғарынды мәндер аймағының шекарасы; 1 – функция унимодалды; 2 – максимумды іздеуде унимодалды; 3 – унимодалды емес.

Мысалы, 10 суретте 1функция унимодальды. Функция 2 унимодалды, егер максимум ды іздесек, және унимодалды емес егер минимумды іздесек (екі минимум х = а және х = b кезінде). Функция 3 унимодалды емес.

Бағытты іздеу әдістері экстремумдардың бірін нүктеге әкелуге қабілетті, бірақ оның жалғыз экстремум екендігін белгілеуге мүмкіндік бермейді, ал егер жалғыз еместігі белгілі болса, онда қандай экстремумға түскенімізді: ғалами ма (барлық аймақ үшін экстремалды) немесе жергілікті (басқа нүктелер максимум жағдайында жоғары бола алады, немесе минимум жағдайында төмен бола алады). Егер оптималдау есебін шығару кезінде біз унимодалдік емес құбылыспен кездесік деген күдік туса, функцияны сканирлеумен дөрекі зерттеу және ғалами экстремум аймағын бөліп көрсету қажет.

Іздеу әдісін таңдау кезінде ескерілетін Ғ функциясының және бір маңызды қасиеті – бұл факторлар саны. Бұл жерде екі негізгі жағдай ерекшеленеді. Біріншісі, F тек бір факторға F=F(х) тәуелді: онда бірөлшемді іздеу туралы айтуға болады. Екіншісі, факторлар біреуден көп болғанда – көпөлшемді іздеу. Жәнеде көпөлшемді іздеудің барлық әдістері принципиалды факторлардың барлық санында k>1 қолданбалы, бұл кезде k = 1 басқа бірөлшемді әдістер қолданылады. Тек қана бірнеше әдістер, мысалы сканирлеу сияқты, бірөлшемдіде, көпөлшемдіде жағдайларда қолданылады.

Бірөлшемді әдістің екі әдісін және үш – көпөлшемдіні қысқаша қарастырамыз.

в) Дихотомия. Сканирлеудің сипаттамасындағы сияқты, 11 суретте көрсетілгендей, [a,b] кесіндісіндегі максимумды іздеуді қарастырайық. Кесіндіні екіге бөлейік – л нүктесі (сол жағы) суретте. Осы нүктедегі F = F(л) мәнін есептейміз. Әзірше экстремум туралы оның біздің кесіндімізде жатқанынан өзге ешнәрсе айта алмаймыз.

Енді ε тең фактордың төменгі түрленуін таңдаймыз, және кесіндіде оң нүктені саламыз п = л + ε. F(п) есептейміз. Енді, 11 суретте кескінделгендей, F(л) >F(п) болғандықтан, егер F(х) унимодалды болса, онда максимум кесіндінің сол жартысында орналасқан деп айтуға болады.

Енді келесі сатыға өтеміз. Кесіндінің оң жартысын алмаймыз (онда максимум жоқ). Ол үшін оң шетін – b нүктесін – л нүктесіне саламыз. Оны былай жасаймыз. л нүктесін b арқылы белгілейміз. 11 суретте бұл тасымал тілмен белгіленген. Әрине, егер F(л) <F(п) болса, онда л нүктесін а нүктесіне салар едік. Кесіндінің шетін п нүктесінеде салуға болады, бірақ л сияқты п жақын болғандықтан бұл бірдей десек болғандай.

Кесіндінің оң шетін ауыстырғаннан соң, есеп өзінің бастапқы шарттарына оралады: а – дан b-дейінгі кесінді берілген, содан максимумды іздеу қажет. Сондықтан, b мәнінен өзге өткен есептеуден ешқандай ерекшелігі жоқ есептеудің келесі циклі басталады. Кесіндіні қайтадан екіге бөлеміз, тағыда ε қашықтыққа қосалқы нүктені саламыз, қайтадан орталыққа оңба немесе солма шетті келтіреміз. Мұндай алгоритм (есептеу бірдей циклдерден тұрады, тек қана бастапқы шарттармен ерекшеленеді) итерациялық деп аталады.

F

а л п b x