Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 9
Текст из файла (страница 9)
В работе 1128] показывается, что метод ломаных близок к оптимальным методам на классе функций, удовлетворяющих условию (1). Оптимальные методы поиска минимума строго унимодальных функций, удовлетворяющих условию (1), рассмотрены в [328). К недостаткам метода ломаных следует отнести то, что с увеличением числа шагов п растет требуемый объем памяти Ч2 МГтОДЫ МИНПМПЗлЦПИ ЮШ?КЦИИ ОДНОИ ПГГКМКННОИ 1ГЛ. т ЭВМ для хранения координат вершин ломаной р„(и). В у 7 будет рассмотрен другой метод, по своей пдее близкий к методу ломаных, но предъявляющий менее жесткие требования к объему памяти и более удобный для реализации на ЭВМ. Следует также отметить, что метод ломаных невозможно реализовать без знания постоянной Х пз условия (1).
На практике оценку для Х получают, вычисляя угловые коэффициенты некоторого числа хорд, соединяющих точки графика минимизируемой функции. Здесь полезно иметь в виду, что если и < и < и, то ]У(ш) — У(и) ]/(ш — и) < < шах[)У(ш) — У(п) )/(ш — и); )У(п) — У(и) )/(и — и)], (7) т. е.
при добавлении новой точка на отрезке )'и, ш] появляется новая хорда с пеменыпим углояьзм коэффициентом. Для доказательства (7) нужно рассмотреть два случая, когда неравенство У(п) ~(У(ш) — У(п) ) (и — и)/(ш — и)+ У(и) выполняется и когда оно не выполняется. Если У(ш)> У(и) и (8) выполняется, то (У(п) — У(и) ) /(и — и) ~ (У (ш) — У(и) ) / /(ш — и) ~ О; если У(ш) ~ У(и) и (8) не выполняется, то (У(ш) — У(п) ) /(ш — и) « (У(ш) — У(и) ) /(ш — и) ~ О.
Аналогично доказывается (7) в случае У(ш) < У(и). Пусть а=и,<и,«...п =Ь; обозначим Х = шах ]У(пе) — У(и1,) ~ [пе — п1,Г'. Ясно, что Х,„< Х,. Пусть ьмелм при каждом т ) 1 величина Л„ь, вычисляется по точкам а = ш, < ш, «... ш е, =Ь, полученным добавлением к точкам пю пп ..., п„одной новой точки. Тогда согласно (7) имеем Х < Х д < Х (и ~ 1) . Это значит, что с возрастанием и величины Х все лучше и лучше приближают Х снизу. Если шах ]и; — пе ь]-ь О при т-эоо, то ]ип Х =Х.
Приведенные екз<т ю соображения могут помочь в получении оценки для Х. При определении Х могут быть полезны теоремы 1, 2. Следует заметить, что использование завышенной оценки для Х ухудшает скорость сходимости метода ломаных, приводит к излишне большому количеству вычислений значений минимиаируемой функции. Если же пользоваться заниженной оценкой для Ь, то метод может привести к неправильному определению приближения минимального значения. Уп ра ж яе ая я. 1.
Привести пример функции, удовлетворяющей ус. ловлю 11), яо яе лвляющейсл уякмодальяой. 2. Можно ля утверждать, что всякая уклмодзльпая на отрезке [а, Ь] функция удовлетворяет условию (1) па [а, Ь]? Рассмотреть пример функцяи /(и) = )'и аа [О, 1]. зз МЕТОДЫ ПОКРЫТИЙ 3.
Рассмотреть первые шесть шагов метода ломаных для функции 1(и) = [[иа — 1[ — 1[ на отрезке [ — 2, 2) прн рззлнчном выборе начальной точкн иь 4. Выяснить, как ведет себя метод ломаных прн минимизации фунпцнн 1(и) = 1 нз отрезке [О, Ц. Ь. Пусть 1(и) = а и" +... + аси+ аа — многочлен п-й стспспн нз отрезке [а, Ь], где 0 ( а < Ь. Обозначим Ат=(Ссб<С<п,ас)0), А =(с:0<с<п,ас<0), 1 (и) = ~~Э~ а.ис 1 (и) = ~ (а, [ и СеА+ анА Доказать, что 1(и) = 1т(и) — 1 (и), з в качестве постоянной 1. нз условна (1) для функции 1(и) нз [а, Ь) можно взять величину шзх [1+ (Ь)— — 1 (а); (1+ (а) — 1 (Ь) )) (106). 3 7.
Методы покрытий 1. Обозначим через с)(г') класс функций, удовлетворяющих условию Лнпшнца (6.1) на отрезке [а, Ь1 с одной и той же для всех функций этого класса постоянной Х ) О. Для функций / = 1(и) ш г/(Л) будем рассматривать задачу минимизации первого типа, когда ищется величина Уе = 1п1 У(и). Для решения ин)а,ь) этой задачи будем пользоваться методами р„, которые заключаются в выборе точек и„..., и„(а < и, «... и„< Ь), вычислении значений функции 1(ис), ..., 1(и„) и определении величины У(из) = ш(п л'(ис), принимаемой за приближение к Уе. гасап Возникает вопрос: как выбрать метод р =(и„..., и„), чтобы ш(п У(ис)(~Хе+ е стХ(и)яс,)(/), (1) гасив где е ) 0 — заданная точность? Ниже будет изложено несколько методов решения поставленной задачи (1). В каждом нз этих методов определенным образом строится некоторая система отрезков, покрывающих исходный отрезок [а, Ь1, и вычисляются значения функции в подходящим образом выбранных точках этих отрезков.
Поэтому излагаемые ниже методы принято называть методами покрытий. 2. Простейшим методом р для решения задачи (1) может служить метод равномерного перебора, когда точки ии ..., и„ выбираются по правилу и, = а + й/2, и, = и, + й, ..., иы, = ис+ й = и, + сй, и„, = и,+(и — 2)й, и„= ппп(и, +(п — 1)й; М, (2) где й = 2е// — шаг метода, а число п определяется условпем и, < Ь вЂ” й/2 < и, + (и — 1) й. Т е о р е м а 1. Метод равномерного перебора (2) решает задачу (1) на классе ч)(л ).
Если й ) 2е/Ь, то существует фупкс)ил 1(и)ш ()(й), для которой лсетод (2) не решает задачу (1). 34 мгтоды ыггнггггггзлцгггг в~гнкцгги одноп пггвхгвгпгои Д о к а з а т е л ь с т в о. Пусть У = У(и) — произвольная функ- ция из (7(У). С учетом неравенства (6.2) для любого и гн ги [иг — Ь/2, и,+ Ы2] имеем Х(и))Х(иг) — У ~и — иг))Х(иг)— — ЬЬ/2) шгп Х(и;) — е при всех г=1, ..., и. Поскольку снгвгвь стема отрезков [и,— Ь/2, иг+Ь/2] (г=1, ..., и) покрывает весь отрезок [а, Ь], т.
е. всякая точна и из [а, Ь] принадлежит одному из отрезнов этой системы, то пз предыдущего неравенст- ва следует, чтоХ(и)) ппп Х(и;) — е для всех иве [а, Ь]. Погегвв этому Х„) ппп Х(иг) — е для любой функции У = У(и)ги (7(У), 1<гвп что равносильно неравенству (1). Если Ь > 2е/Ь, то, напри- мер, для функции У(и)= Уи метод (2) дает шгп (Уиг) — Уа = 1<гав = Удг/2 ) е. 3.
Метод равномерного перебора (2) относится к пассивным методам, когда точки и„..., и„задаются все одновременно до начала вычислений значении функции. На классе ггг(у) можно предложить такой же простой, но более эффектнвнып последо- вательный метод перебора, когда выбор точки иг при каждом г>2 производится с учетом вычислений значения функции в предыдущих точках и„..., иг о и задачу (1) удается решить, вообще говоря, за меньшее количество вычислений значеггий функции, чем методом (2). Л именно, следуя работе «139], по- ложим и, = а+ Ы2, ичг = иг+ /г+(У(и;) — Р,)//, г= 1, „и — 2, (3) и„= впп(и„, + /г+ (У(и„,) — Р„,) /У; Ь), где Ь= 2е,'У,Рг = ш1п Х(из), а число и определяется условием гв/ 'г и„, ( Ь вЂ” /г/2 ( и„, + /г+(У(и,,) — Р„,)/У. Те о р е м а 2.
Метод последовательного перебора (3) решает задачу (1) на классе (7(У). Д о к а з а т е л ь с т в о. Пусть У = У(и) — произвольная функция из г/(У). С учетом неравенства (6.2) для всех иги«и„и,+ + Ы2+(У(иг) — Р)/Ц имеем У(и)» У(иг) — й(Ь/2+(У(и )— — Р,)/У)= Р, — УЫ2» Є— е. Лналогнчно для всех и ш [и,— — Ы2, иг] получим У(и)» У(и,) — У/г/2» Р— е. Поскольку система отрезков [иг — Ы2, иг+ Ы2+(У(иг) — Р,)//.] (г = 1, ..., гг) покрывает весь отрезок «а, Ь], то из предыдущих неравеггстгг следует, что У(и)» 7' — е при всех и ги [а, Ь].
Тогда Хе )~ ) У'„— е прп всех У= У(и)гн 77(У), что равносильно неравенству (1). В худшем случае, когда, например, функция У(и) постоянна или монотонно убывает на [а, Ь] и, следовательно, Рг = = ппн Х(и;) =Х(и;), метод (3) превращается в метод (2), и гв/вг МЕТОДЫ ПОКРЫТИЙ 35 для решения задачи (1) тогда потребуется /У, =(Ь вЂ” а)У/(2е) вычислений значений функции.
В самом лучшем случае, когда У(и) = А + В (и — В), где А,  — постоянные и, следовательно, Р; = У(и,), и< = и, + (2' ' — 1) й (1 = 1, ..., п — 2), для решения задачи (1) понадобится всего Л', = 1 + 1од. (Ь вЂ” а) У/(2е) вычислений значений фуннции. И вообще, если У(и;)) Р; при каком-либо 1, то иы, — и, ) Ь, и поэтому число п вычислений значений функции, необходимое для решения задачк (1), будет, вообще говоря, меныпе Л', и больше Х,. Заметим танисе, что метод (3) идейно примыкает н погоду ломаных пз з 6, но метод (3) выгодно отличается простотой реализации и не требует большой машинной памяти. Недостатком метода (3), нак и метода ломаных, является необходимость априорного знания постоянной Л нз условия (6.1).
4. Следуя (141, 231], изложим еще один метод покрытий для решения задачи (1). Сначала определим минимальное целое число и из условия (4) (Ь вЂ” а)/2"ь' ~ еИ, и ) О, и на отрезке (а, Ь] введем точки с„= а + ) (Ь вЂ” а) /2' () = = О, 1, ..., 2'), где О (/с < и.
Систему отрезков Цго, с,ео], 1= = О, 1, ..., 2' — 1) будем называть разбиением отрезка (а, Ь] й-го уровня. Таким образом, исходный отрезок будет иметь нулевой уровень. Отрезками первого уровня являются две половины исходного отрезка. И вообще, отрезки /с+ 1-го уровня получаются из отрезков /г-го уровня делением пополам. На первом шаге метода берем исходный отрезок (ао Ь,] = =(а, Ь], полагаем Ь, =(Ь, — а,)/2, и, =(а, + Ь,)/2, вышсляем У(и,)=Р,. Если и=О, то процесс закончен и, как увидим ниже, число Р, — искомое приближение для Ув. Допустим, что и ) О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
