XIV Аттетков и др. Методы оптимизации (1081420), страница 9
Текст из файла (страница 9)
57 2.2, Писсиииый и послсдоиогсльиый поиск Л У( Л Л Л Л У( Рис. 2.2 Рис. 2.3 Если У(хо) > 7'(х~), то, используя последовательный поиск, вычисляем значения ~(х'„), где и„= хо + (Й вЂ” 1)6, Й = 2, 3..., пока не будет выполнено неравенство 1(х' ) < Дх~), что позволяет принять [ао Ь) = [хгь 2, х~~) (на рис. 2.3 [а, Ь1 = [х!~, хо~), так как точка х„должна быть либо на отрезке [х~2, хЦ, либо на отрезке [х'и хЯ). хо Е Х, что при х > хо функция г (х) сначала убывает., а затем начиная с пока неизвестного значения х = х„б Х возрастает, хотя далее в промежутке Х могут быть расположены и другие участки немонотонного поведения этой функции.
Выберем начальное значение 6 > О приращения аргумента х функции ) [х), в несколько раз меныпее предполагаемого расстояния между точками хо и х„, и вычислим значения 1(хо) и 2 (х1), где х1 = хо+ Йь Может оказаться, что )(хв) < 7(х~).
Тогда за искомый отрезок [и, Ь] можно сразу принять отрезок [хо.. х11. Но можно продолжить вычисления и, используя последовательный поиск, определять значении /'(хь) в точках хь =хо+6/2~ ', Й= 2, 3 ..., до тех пор, пока не будет выполнено неравенство Дхь) < 7! (хо). Тогда следует принять [ск Ь) = [хо, хь 1) (на рис. 2.2 [а, Ь| = = [хо, хз), поскольку точка:с, должна быть либо на отрезке [хо, хз), либо на отРезке [хз, х2)). НаДо сказать, что пРи этом можно ине заметить" по крайней мере еще один отрезок, на котором функция унимодальна (штриховая линия на рис.
2.2). 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 2.3. Оптимальный пассивный поиск Пусть требуется путем пассивного поиска найти точку х„б Е [О, Ц, в которой унимодальная на отрезке [О, Ц функция 1'(х) достигает наименьшего значения Т. = Т (х„). Минииакеный метод поиска, в котором информация о значениях функции, вычисленных в предшествующих точках, не может быть использована, называют опгпимальным пассивным поиском. Рассмотрим алгоритм такого поиска при различном числе Х точек, выбираемых на отрезке [О, Ц. Если %=1, то единственную точку целесообразно выбрать в середи- У(1/2)------- не отрезка, т.е. принять х1 = 1/2 (рис.
2.4). В этом случае вследствие ' 1 , ''.1 ' унимодальности функции Т(х) имеем 1', < 1" (1,12). Поэтому наименьшая О 1/2 1 х возможная длина интервала неопределенмости равна 1,* = 1 и можно гарантировать, что выбор в качестве точки х, Е [О, Ц точки х1 = 1/2 приведет к погрешности не более Ь[ — — 1[/2 = 1/2. При любом ином положении точки х1 погрешность при выборе х, = х1 будет Ь1 ),Ь1, так как в действительности точка х, может лежать на большей части отрезка [О, Ц.
Если при Л = 2 (рис. 2.5) две точки расположить на отрезке [О, Ц так, чтобы они делили его на равные части., т.е, выбрать х1 = 1/3 и хз = 2/3, то точка х„ Е [О, Ц будет найдена с точностью Ь~ — — 1/3, а наименьшая длина интервала неопределенности составит 1з — — 2Ь~ — — 2,13. В самом доле, если 1'(1/3) < 1'(2/3) (рис.
2.5, о), то в силу унимодальности функции Т"(х) отрезок Рис. 2.4 Отметим, что описанный подход не гарантирует нахождения отрезка унимодальности функции. Например., на рис. 2.3 штриховой линией показан график функции, для которой этот подход не позволяет обнаружить искомый отрезок. 59 2.3. Оптиктвльныйт пассивный поиск Х( Л Л л Рис. 2.5 [2/3, Ц можно исключить и считать, что х„Е [От 2/3). Тогда при вьтборс х, = 1/3 наибольтпая погретпнот ть 1тавна т."тя = 1/3 и /[1/3). Если же окажется, что /(1/3) > /[2/3) (рис.
2.5, д), то можно исключить отрезок [О, 1/3) и считать, что х. Е [1/3, Ц. И в этом случае выбор х„= 2/3 приведет к погрешности не более т.'тя = 1/3, а /. — /(2/3). Заметим, что при /(1/3) = /(2/3) можно исключить любой из указанных отрезков, гарантируя ту же точность нахождения точки х, Е [О, Ц. При ином делении отрезка [О, Ц на части двумя точками длина какой-то из его частей будет больше 1/3 и в действительности точка х„ может принадлежать именно этой части, так что получим погрешность Ья > Ь~~ — — 1/3. Рассуждая аналогично, .можно заключить, что при ттт = 3 нужно также выбирать точки равномерно на отрезке [О, Ц: хт = 1/4, хз = 2/4, хз = 3/4, обеспе тив точность Ь* = 1/4 нахождения точки х* Е [О, .Ц и наименьшую длину 1з — — 1/2 интервала неопределенности.
В случае произвольного Х Е ттт' по тем же соображениям надо выбирать точки ха= Е[О,Ц, 1=1,Х, 1с %+1 (2.4) обеспечивая точность т."тд — — 1/(тт'+ 1) нахождения точки х, и наименьшую возможную длину 2 1а = %+1 (2 5) 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 60 интервала неопределенности. Таким образом, оптимальный пассивный поиск состоит в выборе точек, .равномерно расположенных на отрезке.
При этом (2.5) дает оценку скорости сходимости пассивного поиска с ростом числа Ю точек, так как скорость сходимости любого метода прямого поиска можно характеризовать скоростью уменьшения интервала неопределенности с возрастанием ТУ. Пример 2.2. При заданной наибольшей допустимой длине е. = 0,2 интервала неопределенности, испо.льзуя оптимальный пассивный поиск, найдем точку х, е [0,1], в которой унимодвльнэя на отрезке [О, 1] функция Т" (х) = хз — х+ е х достигает наименьшего на этом отрезке значения*.
Из (2.5) следует, что для этого необходимо принять Х = 9 и в соответствии с (2.4) вычислить значения функции Т" (х) в точках хя = б/10, б = 1, 9: х 0,1 0.,2 0,3 0,4 0,5 0,6 0,7 0,.8 0.9 Т"(х) 0,81 0,63 0.,47 0,.33 0,23 0,17 0.,14 0,16 0,18 Из представленных результатов вычислений можно сделать вывод, что интервалом неопределенности является интервал (0,6, 0,8), а х, = 0,7 х 0,1. Отметим, что при е. = 0,01 потребуется принять Х = 199.
Рассуждения, проведенные выше, попутно обосновыван>т процедуру исключения отпрезка, которую используют во всех методах прямого поиска точки минимума унимодальной функции одного переменного. Эта процедура состоит в следующем. Пусть на отрезке [а, б] числовой прямой расположены две точки с и д, а, < с < а < б, и известны (или вычислены) значения Т'[с) и Т(а) унимодальной на [а, б] функции 1(х). Если Т" (с) < Т" (д) (рис. 2.6, а), то в силу унимодальности функции Т" (х) имеем хэ е [а, д], а отрезок [а, .б] можно исключить из дальнейшего рассмотрения. Наоборот, если Т" (с) > )'(а) (рис. 2.6, б), то х, Е [с, б], а отрезок [а, с] далее можно не рассматривать.
*См.: Амосоо А.А., Дубиткиа Ю.А., Кояченова Н.В. 2.4Ь Методы последовательного поиска Рис. 2.6 Таким образом, в результате применения процедуры исключения отрезка получаем новый отрезок, вложенный в рассматриваемый и заведомо содержащий искомую точку х„. В методах пассивного поиска применение атой процедуры позволяет оценить наибольшую возможную погрешность нахождения точки х,.
Все рассмотренные далее методы последоеательного поиска используют процедуру исключения отрезка для выбора нового отрезка на каждом очередном шаге такого поиска. 2.4.Методы последовательного поиска Метод дихотомии. Рассмотрим последоеагпельный поиск точки х„Е [О, Ц, в которой унимодальная на отрезке [О, Ц функция 1[х) достигает наименьшего значения 1„= Дх„). Метод прямого поиска., основанный на делении пополам отрезка, на котором находится точка х,, называют льепьодоль дихотпомии (от греческих слов дь',хо на две части и торг) сечение). Опишем алгоритм зтого метода.
У Пусть известно, что на й-м шапа ге поеледоеагаельного поиска х„ Е 2д Е [аь,бь) С [О, Ц 1на первом шаге при б = 1 имеем а1 = О и б1 = 1). ~ь На отрезке [аю бь) длиной 1ь выберем две точки хы [аь + бьУ2 д О аь ива ига Ьь х и хьг = (аь+бе)/2+д (рис. 2.7), где Рис. 2.7 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 6 > Π— некоторое достаточно малое число. Вычислим значения )(тя1) и 7(хь2) функции т'(т) в этих точках и выполним процедуру исключения отрезки. В результате получим новый отрезок (аь ы, 6ь.ы] С [аы 6ь).
Если длина 1ьы нового отрезка больше заданной наибольшей допустимой длины е„интиеуваяа неопределенности, то алгоритм метода дихотомии переходит к (к+ 1)-му шагу., повторяя все описанные для к-го шага действия. Если же 1ь ы < е„то вычисления прекращают и полагают я, = (ая 1+ 6яч.1)/2. Так как 1я.„1 — — 1ь/2+ б, или 1ь ы — 26 = (1ь — 2б),12, то 11 — 26 2Я Из этого равенства выводим следующую формулу длины 1ь отрезка (аы 6я), получаемого на к-м шаге метода дихотомии: 11 — 2б + 26.
(2.6) Из (2.6) следует, что 1ь — + 2б при й — > сс, .но при этом 1я > 26. Поэтому выполнение неравенства 1я >~ < е„означающее достижение заданной точности нахождения точки т,„, возможно лишь при условии выбора 26 < е,. Кроме того, нужно учитывать неизбежную погрешность, возникающую при вычислении приближенных значений Т" (х) функции Т" (т). Это приводит к дополнительной погрешности Ь„при нахождении точки я, (см. 2.7).
Поэтому выбор значения 6 ограничен и снизу, т.е. (2.7) Ь,<26<с,. Если эти неравенства нарушаются, то знак разности 7'(яы)— — Д(хь2) может не совпаДать со знаком Разности ((ты) — 7(жьз), что приводит к ошибочному выполнению процедуры исключения отрезка. Итак, метод дихотомии это последовательное построение на каждом 6-м шаге поиска точек лы = (ау + 6я)/2 — 6 2.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
