Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 3
Текст из файла (страница 3)
ш1 з(и) =ш(пХ(и). В этом случае говорят, что функция з(и) ино »»Фп поотАновкА ЗАдАчи зп на У достигает своей нижней грани. Подчеркнем, что зп1 У(и) = и У =.уи всегда существует, а ппп у(и), как мы видели нз приме ияУ ров 1 — 4, не всегда имеет смысл. Введем еще два определения. Определение 4. Последовательность (и„)злУ называется хшнимизирующей для функции 3(и) на множестве У, если Иш Х (иь) = (п1 У (и) = Х . Из определения и существования нпжней грани следует, что минимизирующая последовательность всегда существует.
О п р е д е л е н и е 5. Скажем, что последовательность (и„) сходится к полустону множеству У, если 1пп р(ид, П) = О, где р(иь, У) = ш1 (и„— и) — расстояние от точки и„до множества П. имн Заметим, что если Г„М 8, то всегда существует минимизирующая последовательность, сходящаяся к У~; например, можно взять стационарную последовательность из=из (!с = 1, 2, ...), где и — какая-либо точка из Г . Однако не следует думать, что при У ~ Я любая минимизирующая последовательность будет сходиться к Уи. и Пример 5. Пусть У(и) = — „У=К.
Очевидно, здесь 1+ и~ .7и = О и множество У„состоит из единственной точки ии = О. Последовательность и„= й (й= 1, 2, ...) является минимизирующей, так как 1пп й(й) = О, но р(ию Уи) = й не стремится к нулю. Теперь можем перейти к формулировке задачи минимизации функции У(п) на множестве Г В дальнейшем будем рззлпчать задачи двух типов. К первому типу отнесем задачи, в которых требуется определить величину Уи = (н1 У (и). Сразу и и же подчеркнем, что в задачах первого типа неважно, будет ли множество Уи точек мпнпмума Л(и) на У непустым илн оно пусто.
Ко второму типу задач отнесем те задачи, у которых множество У„непусто и требуется наряду с У найти какую-либо точку и„е= Уи. Заметим, что получить точное решение аадачи первого илп второго типа удается лишь в редких случаях. Поэтому на практике при решении задач первого типа обычно строят какую-либо минимизирующую последовательность (и„) для функции 1(и) на У и затем в качестве приближения для Хи берут величину Х(и,) при достаточно большом й. Аналогично для приближенного решения задач второго типа достаточно построить минимизирующую последовательность (и,), которая сходится ко множеству У в смысле определения 5, и в качестве приближения для У„ 12 методы минимизАции Функций ОднОЙ пегеыеннои ~гл. $ и гочеп и„е= Пв взять соответственно велпчину Х(и„) п точку иь прп достаточно большом й.
Как показывает пример 5, в отличие от задач первого типа не всякая минимизирующая последовательность может быть использована для получения приближенного решения задач второго типа. Построение минимизирующих последовательностей, сходящихся ео множеству Пв, в общем случае требует привлечения специальных методов (6, 22). В настоящей главе будем рассматривать лишь такие задачи второго типа, у которых любая минимизирующая последовательность сходится и Пв. Один такой класс задач дается следующей теоремой, называемой теоремой Вейеригтрасса. Теорема 1. Пусть П вЂ” замкнутое ограниченное множество из В, функция Х(и) непрерывна на П. Тогда Х(и) ограничена снизу на Г, множество Пв точек минимума Х(и) на П непусто, замкнуто и любая минимизируюизая последовательность 1и,) сходится к П„.
Доказательство втой теоремы можно найти, например, в 110, 160, 165, 233). Несколько более общий Фант будет установлен в $ 2 1, из которого также будет следовать теорема 1. Предлагаем читателю вернуться и примерам 1 — 5 и выяснить, в каких случаях и какое из условий теоремы 1 нарушено п и чему это приводит.
Возможна и более широкая постановка задач минимизации второго типа — когда ищутся не только точки минимума в смысле определения 1, но и точки так называемого локального минимума. Определение 6. Точка ов в= П называется точкой локального минимума функции Х(и) на множестве П со значением с= Х(о ), если существует такое число а) О, что Х(гв)(Х(и) длявсехи е= П П (и: (и — гв) <а) = Оа(ов).
Если прп некотором а> 0 равенство Х(о„) = Х(и) для и ее 0„(ов) возная;но только при и = о, то гв называют точкой строгого локального минимума. Для функции, графин которой изображен на рис. 1.1, точки и„ и„ и, являются точками строгого локального минимума, а в точках, удовлетворяющих неравенствам и, < и ( и, и и, ( ( и ( и„реализуется нестрогий локальный минимум. Функция из примера 1 в точках и„=1/й (й=~1, ~2) имеет строгий локальный минимум на П = К, а в точке ив= 0- нестрогий локальный минимум. Точки локального минимума, в которых минимум достигается в смысле определения 1, часто называют точками глобального или абсолютного минимума функции Х(и) на множестве П.
Выделим класс функций, у которых все точки локального минимума являются точками глобального минимума. ПОСТАНОВКА ЗАДАЧИ Определение 7. Функцию Х(и) назовем уиимодальной на отрезне Е/= [а, Ь], если она непрерывна на [а, Ь] и существуют числа а, б (а <а < р < Ь) такие, что: 1) Х(и) строго монотонно убывает прн а<и<и (если а<а)1 2) Х(и) строго монотонно возрастает прп р < и< Ь (если р< Ъ); 3) Х(и) =Хе = ЕпЕ Х(и) прп и<и~~[1, так что Е/е = [и, р]. Случаи, когда один пли два 'к"'.-: й ~ гм ~ рь =ли г Рис.
1Л из отрезков [а, и], [а, р], [р, Ь] вырождаются в точку, здесь не исключаются. В частности, если а=р, то Х(и) назовем строго унимодальной на отрезке [а, Ь]. Функция пз примера 2 унимодальна на любом отрезке [а, Ь]; функция пз примера 1 строго уннмодальна на [2/3, 2], но не будет уппмодальной на [1/2, 2]. Нетрудно видеть, что если функция У(и) унимодальна на [а, Ь], то она остается унимодальной п на любом отрезке [с, й]гв — [а, Ь]. В заключение кратко остановимся на задаче максимизации функции.
О п р е д е л е н и е 8. Функция Х(и) называется ограниченной сверху на множестве Е/, если существует такое число В, что Х(и)<В прп всех и~и Е/. Функция Х(и) не ограничена сверху на Е/, если существует последовательность (и,) я Е/, для которой 1пп Х(иь) = со. Функцию Х(и) называют ограниченной на Е/, А-~ю если она ограничена на Е/ сверху и снизу. О и р е д е ч е н и е 9. Если функция Х(и) ограничена сверху на Е/, то число Х* называется верхней гранью Х(и) на Е/ в том случае, когда: 1) У(и)< Хе для всех и ~ Е/; 2) для любого числа е > 0 найдется такая точка и, я Е/, что Х(и,) >Ха — з. Если Х(и) не ограничена сверху на Е/, то по определению принимается Ха= .
Последовательность (и,) ~ Е/ называется максимигирующей для Х(и) на Е/, если 1пп Х(иь) = Х"'. Если существует такая А-~ ю точка и*е Е/, что Х(и~)=/*, то и* называется точкой максиму- 14 методы ыинимизлции Функцпй ОднОЙ пеггыеннон !Гл.! ма 1(и) на г1, а величина 1(и*) — наибольшим или максимальным значением 1(и) на У. Мнолгество точек максимума 1(и) на [1 будем обозначать череа Уе, верхнюю грань — через 1э = = зпр 1 (и). зс П Заметим, что верхняя грань и максимизпрующая последовательность всегда существуют, а ыаксимальное значение может не существовать.
Если выполнены условия теоремы 1, то 1* ( Уе ~(И и любая максимизирующая последовательность (и„) сходится к 1)в. В задачах максимизации также можно различать задачи двух типов: в задачах первого типа ищется величина 1е, а в задачах второго типа ищется 1* и какая-либо точка неги (1а. Нетрудно видеть, что впр 1(и) = — [п[ ( — 1(и)), мп прпчем любая точка максимума и любая макспмизирующая последовательность для 1(и) на У являются точкой минимума и соответственно ыпнпмизпрующей последовательностью для функции -1(и) на г). Это значит, что лгобая задача максимизации функции 1(и) на У равносильна задаче мипиыизации функции -1(и) на том же множестве У.
Поэтому мы можем ограничиться изучением лишь задач минимизации. Наконец, немного о точках локального максимума. Определение г0. Точка паж г1 нааывается точкой локального максиэгума функции 1(и) на множестве У, если существует такое число а>0, что 1(пв)~1(и) для всех иен() П й(и: [и — п*[(и) =0„(п*). Если при некотором а)0 равенство 1(па)=1(и) для и~О„(эе) возможно только при и = и*, то и* называют точкой строгого локального макси.
пума. Для функции, график которой изображен на рис. 1.1, точки и„и„и„и„являются точками строгого локального максимума, а в точках, удовлетворяющих неравенствам и, -и(и, и и,( ( и (и„реализуется нестрогий локальный максимум; и, — точка глобального максимума. Множество всех точек локального минимума и максимума функции на множестве () принято называть точками локального экстремума функции на этом множестве илп, проще, точками экстремума. У и р э ж н е н и я.
1. Построить мннкмпзпрующую н мзьсвмнзярующую последовательности для фувкцкя 1(и) = вес!як пз У = к. Достпгэет лн функция своих няжнпх н верхних граней нв К? 2. Пусть г'(а) = ~а' — 1[ пря и чь 1 и У(1) = 1. Пзйтя множество Уа точек мяннмумв 1(и) нз У = К. Можно вп утверягээть, что любая зщннмнзярующзя последовательность для этой функции будет слодкться к Уаг 3 1!зйтя все точки локального экстремума функцкя!(и) = [[[и' — 1[— — 1[ — 1[ нэ отрезке [а, Ь) прн различных а, Ь. Прн каких а, Ь этэ функ. цня будет унвмодзльной нз [а, Ь)! (5 кллссическэги метод 0 2! 4. Выяснить, яа каких отрезках будут увпыодальяыпп фупкцпп 1(и) = о", 1(и) = и', 1(и) = — ио, 1(и) = Г')и(, 1(и) = сое и.
5. Кслп функция 6(и) уппыодальпа па отрезке [с, А), то функция 1(и) = й((А — с)(и — а)/(Ь вЂ” а) +о) уяякодальяа на отрезке (а, Ь). Доказать. 6. Доказать, что лпнейвзя функция 1(и) = Аи+ д, где А, )7 — постеяаные, Л Ф О. достигает своего ыяяпыуые я ыапеяпуыа яа отрезке (а, Ь) только прп и = а пап и = Ь. 7. Найти ээппиээуи функции 1 (и) = шах [ ! — и! [ па ээяепэествах У 2 эаоаэ ~Ки У=(и:!(и(оо). $2. Классический метод Под классическим методом будем подразумевать тот подход к поиску точек экстремума функции, который основан на дифференциальном исчислении н подробно описан в учебниках по математнческоэгу анализу [(О, !60, 465, 233). Мы адесь лишь вкратце остановимся на этом методе. Пусть функция 1(и) кусочно непрерывна и кусочно гладка на отрезке [а, Ь].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
