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