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