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