Метод деления интервала пополам.

Рассматриваемый метод позволяет исключать в точности половину интервала на каждой итерации. Иногда этот метод называют трехточечным поиском на равных интервалах, поскольку его реализация основана на выборе трех пробных точек, равномерно распределенных в интервале поиска. Ниже приводится описание основных шагов поисковой процедуры, ориентированных на нахождение точки минимума функции  в интервале (а,b).

Шаг 1. Положить  и L=b—а. Вычислить значение .

Шаг 2. Положить,  и . Заметим, что точки  делят интервал (а, b) на четыре равные части. Вычислить значения  и .

Шаг 3. Сравнить  и .

(1) Если , исключить интервал ( ), положив .

Средней точкой нового интервала поиска становится точка . Следовательно, необходимо положить . Перейти к шагу 5.

(2) Если , перейти к шагу 4.

Шаг 4. Сравнить  и .

(1) Если  исключить интервал ( ), положив . Так как средней точкой нового интервала становится точка  положить . Перейти к шагу 5.

(2) Если , исключить интервалы ( ) и ( ). Положить  и . Заметим, что  продолжает оставаться средней точкой нового интервала. Перейти к шагу 5.

Шаг 5. Вычислить . Если величина  мала, закончить поиск. В противном случае вернуться к шагу 2.

Замечания

1. На каждой итерации алгоритма исключается в точности половина интервала поиска.

2. Средняя точка последовательно получаемых интервалов всегда совпадает с одной из пробных точек  найденных на предыдущей итерации. Следовательно, на каждой итерации требуется не более двух вычислений значения функции.

3. Если проведено п вычислений значения функции, то длина полученного интервала составляет  величины исходного интервала.

4. В работе [2] показано, что из всех методов поиска на равных интервалах (двухточечный, трехточечный, четырехточечный и т. д.) трехточечный поиск, или метод деления интервала пополам, отличается наибольшей эффективностью.

Пример 2.2

Минимизировать функцию  в интервале (60;150) используя Метод деления интервала пополам

Вычислим точки

Здесь .

.

Итерация 1

Таким образом, исключаются интервалы (60,82.5) и (127.5,150). Длина интервала поиска уменьшается с 90 до 45.

Итерация 2

Таким образом, интервал неопределенности равен (93.75, 116.25)

Итерация 3

Таким образом, исключается интервал (105, 116.25). Новый интервал неопределенности равен (93.75, 105), его средняя точка есть 99.375 (точка  на итерации 3). Отметим, что за три итерации (шесть вычислений значения функции) исходный интервал поиска длины 90 уменьшился до величины .

Поиск с помощью метода золотого сечения.

Из проведенного выше обсуждения методов исключения интервалов и минимаксных стратегий поиска можно сделать следующие выводы.

1. Если количество пробных точек принимается равным двум, то их следует размещать на одинаковых расстояниях от середины интервала.

2. В соответствии с общей минимаксной стратегией пробные точки должны размещаться в интервале по симметричной схеме, таким образом, чтобы отношение длины исключаемого подынтервала к величине интервала поиска оставалось постоянным.

Рис. 2.10. Поиск с помощью метода золотого сечения.

3. На каждой итерации процедуры поиска должно вычисляться только одно значение функции в получаемой точке.

Руководствуясь этими выводами, рассмотрим симметричное расположение двух пробных точек па исходном интервале единичной длины, которое показано на Рис. 2.10. (Выбор единичного интервала обусловлен соображениями удобства.) Пробные точки отстоят от граничных точек интервала на расстоянии . При таком симметричном расположении точек длина остающегося после исключения интервала всегда равна  независимо от того, какое из значений функции в пробных точках оказывается меньшим. Предположим, что исключается правый подынтервал. На Рис. 2.11 показано, что оставшийся подынтервал длины  содержит одну пробную точку, расположенную па расстоянии(1- ) от левой граничной точки.

Для того чтобы симметрия поискового образца сохранялась, расстояние (1—т) должно составлять -ю часть длины интервала (которая равна ). При таком выборе  следующая пробная точка размещается на расстоянии, равном -й части длины интервала, от правой граничной точки интервала (Рис. 2.12).

Рис. 2.11. Интервалы, полученные методом золотого сечения.

Отсюда следует, что при выборе  в соответствии с условием  симметрия поискового образца, показанного на Рис. 2.10, сохраняется при переходе к уменьшенному интервалу, который изображен на Рис. 2.12. Решая это квадратное уравнение, получаем

откуда положительное решение =0.61803... . Схема поиска, при которой пробные точки делят интервал в этом отношении, известна под названием поиска с помощью метода золотого сечения.

Рис. 2.12. Симметрия золотого сечения интервала

Заметим, что после первых двух вычислений значений функции каждое последующее вычисление позволяет исключить подынтервал, величина которого составляет (1— )-ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений значений функции, равна . Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффективным способом реализации минимаксной стратегии поиска.

Пример 2.3

Минимизировать функцию  в интервале (60;150), используя Метод золотого сечения

Для того чтобы перейти к интервалу единичной длины, проведем замену переменной, положив . Таким образом, задача принимает следующий вид:

Минимизировать  

при ограничении .

Итерация 1.

. Проведем два первых вычисления значений функции:

Так как  и  интервал  исключается.

Итерация 2.

. Следующее вычисление значения функции проводится в точке

.

Так как  и  интервал  исключается.

Итерация 3.

. Следующее вычисление значения функции проводится в точке, расположенной на расстоянии х (длина полученного интервала) от левой граничной точки интервала, или на расстоянии (1— ) х (длина интервала)от правой граничной точки. Таким образом,

Так как  и , интервал  исключается. В результате получен следующий интервал неопределенности:

 для переменной , или  для переменной х.

Если в процессе поиска проведено шесть вычислений значений функции, то длина результирующего интервала для переменной  равна

,

что соответствует интервалу длины 8.1 для переменной х. Для сравнения напомним, что в аналогичной ситуации метод деления интервала пополам привел к получению интервала длины 11.25.

В общем случае если правая и левая граничные точки интервала неопределенности (обозначим их через XR и XL) известны, то координаты всех последующих пробных точек, получаемых в соответствии с методом золотого сечения, можно вычислить по формулам

 или

в зависимости от того, какой подынтервал был исключен на предыдущей итерации — левый или правый. В приведенных выше формулах через  обозначена п-я степень , где п — количество вычислений значений функции.

Поиск с помощью метода золотого сечения может быть окончен либо исходя из заданного количества вычислений значений функции (и, следовательно, величины интервала неопределенности), либо по достижении относительной точности искомого значения функции. Наиболее предпочтительным является использование обоих критериев одновременно.

Название "золотое сечение" произошло от названия соотношения в уравнении

Видно, что  делится на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т.е. равно так называемому золотому отношению"".

---

Дата добавления: 2018-02-15; просмотров: 1637; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!