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