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