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