Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 6
Текст из файла (страница 6)
Пусть уже сделано и — 1 шагов (и) 2) и найдены отрезок [а ь Ь ~] и точка и« ~(а~ ~ < и„-~ < Ь«-~) с вычисленным значением /(и, ~), причем й„~ чь (а ~+ Ь,)/2. Тогда на следующем з-м шаге берется точка и, = а«, + Ь„, — И, ь расположенная внутри [а, ь Ь„,], симметрично точке и, относительно середины этого отрезка — отсюда происходит название методов. Затем вычисляется значение /(и«) и сравнивается с /(э» ~). Пусть для определенпости и« ~ < и„ (случай и < д, рассматривается аналогично).
Тогда при /(и«,) < Х(и«) полагается а« = а«ь Ь, = и, й«й б если же /(и«,) ) Х(и ), то а« = = й ь Ь« = Ь ь и„= и . Если й« ~ (а + Ь )/2, то процесс может быть продолжен дальше. Может оказаться, что й = (а + Ь )/2,— в атом случае процесс заканчивается; прн необходимости на [а„, Ь«] можно продолжать поиск минимума аналогичным методом, начиная с выбора новой начальной точки й«Ф (а + Ь )/2.
Из описания симметричного метода видно, что всякий симметричный метод полностью определяется заданием отрезка [а, Ь] и первой точки и~ (а < и~ < Ь). Отсюда следует, что в качестве другой характеристики симметричного метода можно взять длины б отрезков [а, Ь ] (и = 1, 2, ...), где б| = Ь вЂ” а, пз = шах(Ь вЂ” ик и~ — а). Очевидно, й «~ ~~ й /2 при всех з 'л« 1. Как видим, симметричные методы весьма просты и, пожалуй, даже взящны. Однако все эти методы страдают тем яге недостатком, что и метод золотого сечения: погрешность» допущенная в заданли первой точки иь приводит к быстрому вакаплпззнвю погрешностей па дальнейших шагах, и уже при не очень больших п результаты будут сильно отличаться от тех, которые могли бы получиться при точной реализации симметричного метода с точными исходными данными.
Если симметричный метод таков, что для б« = Ь« — а«выполнено условие /1 /2 < б .ц ( 24»/3, и = 1, ..., /у, (4) прп некотором /у ) 1, то В будут удовлетворять конечно-разностному ураввению (1) при л = 2, ..., /У, и исследование поведения погрешностей в этом случае может быть проведено так же, как это было сделано выше для метода аолотого сечения. Чтобы избежать слишком быстрого роста погрешностей в симметричных методах со свойством (4), ва каждом отрезве [а, Ь,] (и = 2, .. «д/), содержащем точку и с предыдущего шага, следующую точку и„„~ нужно определять не по формуле и +~ — — а«+ Ь вЂ” й«, а лучше принять за и«+1 ту иа точек а +ч(Ь« — а ), а + (1 — г)(Ь» — а«)(г = (б, + б)/Ь|), которая наиболее удалена от и,. У и р аж н е н и я.
1. Найти наименыпее к, начиная с которого точность метода золотого сечения больше точности метода деления отрезка пополам в 2 раза; в 10 раа. 2. Написать конечно-разностные уравнения для длин б«отрезков [а, Ь ], получаемых симметричным методом, для случая, когда на какихто шагах метода нарушается условие (4). 5 5. Об оптимильных методах 1.
В тех случаях, когда вычисление значений функции связлно со значительными затратами, большую ценность приобретают экономичные или, как их еще пазывают, о1гтимальныз методы, позволяющие решить задачу минимизации с требуемой точностью на основе вычислений значений минимизируемой функции как можно в меньшем числе точек, а также тесно связанные с ними методы, гарантирующие наилучшую точность при жестко заданном количестве вычислений значений миними- й 51 ОБ ОПТИМАЛЬНЫХ МГТОДАХ 23 эируемой функции. В связи с этим возникают вопросы, что такое оптимальные методы, существуют лн такие методы, как их строить? Абсолютно наилучший метод, пригодный для минимизации всех функций, вряд ли существует, и на поставленные вопросы можно попытаться ответить лишь при определенных Ограничениях на рассматриваемые методы, функции и постановки задач минимизации.
Предположим, что нам задан некоторый класс функций Д, зафиксирована какая-либо постановка задачи минимизации функций из этого класса (например, задача первого или второго типа из 2 1) и указано множество методов Р, позволяющих решить поставленную задачу минимизации. Пусть А(У, р) — погрешность решения рассматриваемой задачи минимизации для функции л = л (и) ш ~ с помощью метода р ш Р. Ясно, что, минимизируя одним и тем же методом р различные функции из Ч, мы будем получать, вообще говоря, различные погрешности: для некоторых «хороших» функций из Д эта погрешность может Оназаться равной нулю, а для других «плохих» функций из Д погрешность может быть значительной. Имеет смысл считать метод р, ~БР лучше метода р>ш Р, если погрешность метода р, даже для самых «плохих> (для р,) функций из (л будет меньше погрешности метода р, для «плохих» (для р,) функций пз «,л.
В связи с этим представляется разумным ввести величину 6(р) = зпрй(Х, р), выражающую собой погрешность метода лыс р прп минимизации самой «плохой» (для р) функции из Ч. Определение 1. Величину 6(р) = зцрй(Х, р) навалы о вем гарантированной точностью метода ршр на классе функций Ч. Скажем, что метод р, ш Р лучше метода р,«н Р на классе ф, если 6(р~)<6(р«) й1етод р,„'е Р назовем оптимальным методом на классе Д, если 6(р») = ш1 6(р) = 6», а величину »ыг 6 — наилучшей гарантированной точностью методов Р на классе (л. Если для некоторого метода р, ш Р выполняется неравенство 6(р») ((6» + е, то метод р, назовем е-оптимальным на классе (л.
Вопросы существования оптимальных и е-оптимальных методов, возможности их построения для различных множеств методов Р, классов функций 9 и постановок задач минимизации, а также другие возможные подходы к проблеме выбора оптимальных методов изучались, например, в (11, 21, 81, 83, 95, 106, 109, 228, 241, 266, 282, 288, 291, 298, 328, 332$ 2.
Здесь ыы кратко остановимся на оптимальных методах решеввя задачи минимизации функций вз класса О, состоящего вз всех уввмодальных фуппцпй ва отрезке (а, ь). Ограничимся рассмотрением множества Р методе» ыпзпмэзацпп, пспопьзующпх лишь звачеппя функции, считая прп атом, что чпспо и вычислений»начепвй минимизируемой функция заранее задано. Будем ередпелагать, что з описание каждого метода Р иэ Р входим 24 ынтоды минимизлции Функций ОднОЙ пепкминнОЙ (Гл. 1 задание нравлла выоора точен иь ..., и» из отрезка [а, Ь], вычисление аначений 1(и«)...» 1(и„) минимизируемой функции 1(и) ш(«, выделение из точек и«, ..., и такой точки и, для которой 1(и„) = ш(п 1 (из), и та1ап оиределепие отрезка [а», Ь ], где в качестве а„, Ь берутся ближайшие глава или справа к й точки среди иь ..., и, а, Ь (возможности и = а илн и„= Ь пе исключаются).
Таким образом, применяя конкретный ыетод р„зн Р к конкретной функции 1(и) щ(), в результате получаем отрезок [а, Ь„] и точку й„щ ви [а, Ь»] с вычисленным значением 1(ип) = ш«п 1(и;). Пз определета1»» ния унимодальной функции н построения отрезка [а, Ь„] следует нера венство 1(и) Рл 1(й ) при всех и ш [а, Ь]1,[а„, Ь„], так что 1»= 1п( 1(з) = (п( 1(и), Уз () [а, Ь„]~(й. (() ааиаЬ а»а»аз, В качестве прнближенпл для 1» обычно берут велпчпну 1(и,), а в качестве приближения к множеству («з можно взять любую точку и„из отрезка [а, Ь ] — па практике часто принимают и» = ип или ип = (а»+ Ь»)/2. Отрезок [а„, Ь„] принято называть отрезном лонализапии минимума функции 1(и) ва отрезке [а, Ь]. Из (() следует„что расстолние от л«ооой точки ип» зп [а„, Ьп] до множества У не превышает длины отрезка локализации ܄— а»л р(и„, П ) = «п( ] и„~ — и]< ܄— а„.
(2) Величину а(1, р„) = ܄— а можно прпнлть за погрел«ность решения задачи минимизации функции 1(и) ш («методом р, ш Р. Согласно (2) чщ« меньша погрешность а(1, р ), тем точнее будет определено приближение и„к Уз ««, следовательно, теы чучше метод р,. Для точного определения наилучшего или близкого к неыу метода нам остается еще уточнить правило выбора точек и«, ..., и, в которых вычисляются значения минимизируемой функцки. Здесь принято различать два типа методов: пассивные методы и последовательные методы. Если все точки ии ..., и„ метода р„ выбираются одновременно до начала вычислений и в дальнещпем уже не меняются, то такой метод называют пассивным. Если в методе р„ точки и«, ..., и выбираются последовательно отдельными порциями, причем при выборе каждой очередлой порции учитываются результаты предыдущих вычислений и проводится уточнение отрезка локализации ыпнимума, то такой ыетод называется пас,«вдовагвльным.
Примером пассивного метода являетсл метод равномерного перебора. В этом методе точки и„.. » и выбираются по правилу". и» = и, + «й (« = 1, ..., и), где Ь ) Π— шаг метода, и« вЂ” заданнал точка из [а, Ь], и« вЂ” а ( Ь (наприыер, и« = а или и« = а+ Ь«2), и, кроме того, пй ( ( Ь вЂ” и«( (и+ () Ь. Примерами последовательного метода служат методы деления отрезка пополам, золотого сечения. Пассивный метод является частным случаем последовательного кето да, когда все и точек выбира«отса сразу в первой «ке порции.
Поэтому нетрудно попять, что последовательные методы, вообще говоря, обладатот болыпей гибкостью и гораздо точнее пассивных методов. Однако отсюда не следует, что пассивные ыетоды вовсе не находят приыененил. Такие методы весьма полезны, когда можно вести параллельные вычисления, испольауя, например, ыногопроцессорные ЭВЫ.
В тех случалх, когда значения минимизируемой функция определяютсл иа физического аксперимента, условил проведении таких экспериментов также могут сделать необходимым применение пассивных методов. ОБ ОПТИМАЛЬНЫХ 11КТОДАХ 25 Таким образом, и-точечные (т. е. использующие вычисление значений функции в и точках) последовательные и пасспвныо методы описаны. Если теперь в определении 1 принять, что Π— класс унпмодальиых функций на отрезке [а, Ь), Р = Р— множество всех и-точечных последовательных (или пассивных) методов, 6(У, р„) = ܄— а„— длина отрезка локализации минимума, полученного методом р для функции У = У(и) ш Ч, то придем к определениям гарантированной точности. оптимального п е-оптимального последовательного (пассивпого) метода для унпмодальных функции.
Кратко рассмотрим вопросы существования и построения оптпмальных методов для таких функций. 3. Сначала остановимся на пассивных методах. Пусть р„= [иь..., и„)— какой-либо пассивный метод, а = и, < иг «... и„< Ь = и +ь Применяя его к какой-либо функции У(и) ш О, получаем отрезок [иг ь иго~) локализации мияямума этой функции. так что погрешность метода р здесь будет равна 6(У, р ) = иоы — ие 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
