Ф.П. Васильев - Методы оптимизации (1125241), страница 4
Текст из файла (страница 4)
Доказать, что линейная функция Дх) = Ах+В, где А,  — постоянные, А э! О, достигает своего минимума и максимума на отрезке [о, Ь) тольно при х = а или х = Ь. 7. найти минимум функции /(х) = так ]а~ — х!! на множествак х =и и и =(х: 1 <в с < со), о<~(! ф 2.
Классический метод Под классическим методом будем подразумевать тот подход к поиску точек экстремума функции, который основан на дифференциальном исчислении и подробно описан в учебниках по математическому анализу [327; 350; 352; 534]. Мы здесь лишь вкратце остановимся на этом методе. Пусть функция /(х) кусочно непрерывна и кусочно гладка на отрезке [а, 6].
Это значит, что на [а, Ь) может существовать лишь конечное число точек, в которых /(х) либо терпит разрыв первого рода, либо непрерывна, но не имеет производной. Тогда, как известно, точками экстремума функции /(х) на [а, 6) могут быть лишь те точйи, 'в которых выполняется одно из следующих условий: 1) либо у(х) терпит разрыв;:2) либо /'(х) непрерывна, но производная /'(х) не существует; 3)либо производная /'(х) существует и равна нулю; 4) либо х = а или,х — — Ь. Такие точки принято называть точками, подозрительными на экстремум. Поиск точек экстремума функции начинают с нахождения всех точек, подозрительных на экстремум, После того как такие точки найдены, проводят дополнительное исследование и отбирают среди них те, которые являются точками локального минимума или максимума, Для этого обычно исследуют знак первой производной /',(х) в окрестности (или соответствующей полу- окрестности точек разрыва и граничных точек х = а, х = 6) подозрительной точки.
Для того чтобы подозрительная точка и Е [а, 6) была точкой локального минимума, достаточно, чтобы !пп /(х) > у(в), !1ш /'(х) > /(в) и при в т — О ь в+О некотором ст >О на множествах [а, Ъ)Г!(в, и+ст) = 0„'(и), [а, 6]Г1(п-а", в) = = 0 (в) существовала производная /'(х), причем /б(х) > О при х е От(в) и 7"(х) <О при хе О (в).
Если же !пп /(х)< /(и), 1!гп /'(х)</'(в) и /'(х) <О при хе О+(и), г"(х) > О при хе О. (и), то в — точка локального максимума. В тех случаях, когда удается вычислить в подозрительной точке производные второго и более высокого порядков, то их также можно использовать для исследования поведения функции в окрестности этой точки. А именно, пусть известны производные /'(и),..., у! 1(в), причем г(!!(в) = О (т = 1,..., и — 1), а /!в!(в) ф О (и > 1).
Если и — четное число, то в случае /["1(в) > О в точке в реализуется локальный минимум, а в случае /! !(в) < Π— локальный максимум. Если и нечетно, то при а < в < Ь в точке и не может быть локального минимума или максимума; при и = а (в = 6) в случае Г("1(в) > О в точке и имеем локальный минимум (максимум), а в случае /'!"!(в) < Π— локальный максимум (минимум), Чтобы найти глобальный минимум (максимум) функции /'(х) на [а, 6], нужно перебрать все точки локального минимума (макснмума) на [а, 6) и среди них выбрать точку с наименьшим (наибольшим) значением функции, если таковое существует.
Если вместо отрезка [а, 6] имеем дело со множеством Х =(х: а< х <оо), или Х =(х; — со < х< 6), или Х =]к, то наряду с вышеописанными исследованиями нужно также изучить поведение функции при х- со или х- — оо. Классический метод исследования функции на экстремум следует использовать во всех тех случаях, когда достаточно просто удается выявить все подозрительные на экстремум точки и реализовать описанную выше схему отбора экстремальных точек. К великому сожалению, классический метод имеет весьма ограниченное применение. Дело в том, что вычисление производной /'(х) в практических задачах зачастую является непростым делом.
Например, может оказаться, что значения функции /(х) определяются из наблюдений или каких-либо физических экспериментов, и получить информацию о ее производной крайне трудно. Но даже в тех случаях, когда производную все же удается вычислить, решение уравнения /'(х) = О и выявление других точек, подозрительных на экстремум, может быть связано с серьезными трудностями.
Поэтому важно иметь также и другие методы поиска экстремума, не требующие вычисления производных, более удобные для реализации на современных ЭВМ, Упражнения !. Найти точки экстремума функции /(х) = з!пз в.+ созе х на отрезках [О, Зя/4], [О, 2я). 2, Пусть /(х) = (1+ в!/*) ! при х ~ 0 и ДО) = О. Найти точки экстремума этой функции на отрезках [О, 1), [-1, 0], [-1,!), [1, 2) и на и. 3. Пусть непрерывная на отрезке [о, Ь) функция /(х) в точке в (ос в < 6) имеет строгий локальный минимум. Можно ли утверждать, что существует число о > 0 такое, что /(х) монотонно убывает при в — а с х < в и монотонно возрастает при в с х с в+ о? Рассмотреть функцию /(х) = 2х + х з1п(1/х) (х ф 0), ДО) =0 на [-1, 1).
Исследовать случай, когда /(х) имеет на [в,6) конечное число точек локального экстремума. 4, Пусть функция /(х) определена на ]о,Ь] и дважды дифференцируема в точке в я[в,6]. Докааать, что если в( в ( 6 и в точке в реализуется локальныи минимум /(х), то необходимо, чтобы /" (х) > О. Будет ли верным это утверзкдение, если в = а или в = 6? Будет ли оно верным, э если в = о или в = 6 и, кроме того /'(в) = О? Рассмотреть функции Дх) = -х, /(х) = соз х на [ — я, а.], б.
Пусть функция /(х) определена на [о, Ь] и в точке в я[в, 6] имеет и производнык (и > 2), причем известно, что /!з!(в) = 0 при ! = 1,..., и — 1 и /1~1(в) ф О. Доказать, что если в— точка локального минимума и а < в < Ь, то и — четное число и /!"!(в) > О. Что иаменится, волив=анлив=Ь? О.
Пусть функция /(х) аналитична иа [в,Ь), т. е. Ряд Тейлора этой функции сходится к /(х) во всех точкак ]и, Ь]. Может ли эта функция иметь на [а, Ь] бесконечное число точек локального экстремума? 7, Пусть функция /(х) определена на [а, 6] и в точке в имеет производные всех порядков, Можно ли утверждать, что если в †точ локального минимума, то / (в) ф.О при каком!") либо и >! ? Рассмотреть функцию /(х) =е !М (х и О), /(О) = 0 в точке в=О. Что изменится, если функция /(х) аналитична на ]в,Ь]? 3.
Пусть функция /(х) дифференцируема на [о, Ь] и в точке в я [а, Ь] достигает своей нижней грани на [о, 6). Доказать, что тогда необходимо, чтобы /'(в)[х — в) > 0 прн всех х е а [о, Ь], Будет ли выполнение этого условия достаточно зля того, чтобы в точке в достигалась нил(няя грань /(х) на 1а, 6)? ф 3. Метод деления отрезка пополам Простейшим методом минимизации функции одной переменной, не требующим вычисления производной, является метод деления отрезка пополам. Опишем его, предполагая, что минимизируемая функция /'(х) унимодальна на отрезке [а, 6]. Поиск минимума /(х) на [а, 6] начинается с выбора двух 17 $ 3.
МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ 16 Пс 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ точек х, =(а+Ь вЂ” 6)/2 и х,=(а+6+6)/2, где 6 — постоянная, являющаяся параметром метода, 0 < 6 < Ь вЂ” а. Величина 6 выбирается вычислителем и может определяться целесообразным количеством верных десятичных знаков при задании аргумента х. В частности, ясно, что 6 не может быть меньше машинного нуля ЭВМ, используемой при решении рассматриваемой задачи.
Точки х„ х расположены симметрично на отрезке [а,Ь] атно- сительно его середины и при малых 6 делят его почти пополам — этим и объясняется название метода. После выбора точек х„ х вычисляются значения /(х,), /(х,) и сравниваются между собой. Если /(х,) < /(хз), то полагают а, = а, Ь, = х,; если же /(х,) > /(х,), то полагают а, = х, Ь, = Ь. Поскольку /(х) унимодальна на [а, Ь], то ясно, что отрезок [ап Ь,] имеет общую точку с множеством Х„ точек минимума /(х) на [а, Ь] и его длина равна Ь, — а, =(Ь вЂ” а — 6)/2+ 6.
Пусть отрезок [а, „Ь„,], имеющий непустое пересечение с Х„, уже известен, и пусть Ь,, — а,, =(Ь вЂ” а-6)/2~ '+6 > 6 (й > 2), Тогда берем точки х„, =(а,,+Ь,,-6)/2, х„=(а,,+Ь„,+6)/2, расположенные на отрезке [а,, „Ь,,], симметрично относительно его середины, и вычисляем значения /(хзь,),/(хз ). Если /(т „,) < /(х ), то полагаем а = а Ь„= х,„; если же /(х,„,) > /(х>,), то полагаем а„= х,„, Ь„= Ь,, Длина получившегося отрезка [а„, Ь,] равна ܄— а =(Ь вЂ” а — 6)/2 +6 > 6 и [а., Ь,]п и Х„~Я. Если количество вычислений значений минимизируемой функции ничем не ограничено, то описанный процесс деления отрезка пополам можно продолжать до тех пор, пока не получится отрезок [а„, Ь„] длины Ь,-а„< е, где е — заданная точность, е > 6. Отсюда имеем, что Ь > 1од,((Ь вЂ” а — 6)/(е— — 6)), Поскольку каждое деление пополам требует двух вычислении значений функции, то для достижения точности Ь„ — а, < е требуется всего п, = 2Ь > 2 1од,((Ь вЂ” а — 6)/(с — 6)) таких вычислений.
После определения отрезка [а„Ь„] в качестве приближения ко множеству Х можно взять точку х =х,„, при /(хз, ~) </(хз„) и х =х,„ при /(х>ь,) > /(л„), а значит /(х„) может служить приближением для !й1 1'(х). При таком выборе приближения для Х„будет допущена *е~о,м погрешность р(х, Х,) < шах(܄— х,' х„— а„)'= (Ь вЂ” а- 6)/2ь. Если не требовать того, чтобы значение функцйи, принимаемое за приближение к /„, было вычислено непременно в той же точке, которая служит приближением к Х., то вместо х„можно взять точку а„= (а, + Ь„)/2 с меньшей погрешностью р(х„, Х ) <(܄— а,)/2=(Ь вЂ” а — 6)/2 ь'+ 6/2 (здесь Ь = и/2 и 6 достаточно мало). Конечно, и в этом случае можно бы провести еще одно дополнительное вычисление значения функции в точке », и принять |(х )=/„. Однако заметим, что на практике нередко встречаются функции, нахождение значения которых в каждой точке связано с большим объемом вычислений или дорогостоящими экспериментами, наблюдениями, — понятно, что здесь приходится дорожить каждым вычислением значения минимизируемой функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
