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

Метод сканирования

Метод заключается в последовательном переборе всех значений с шагом (погрешность решения) с вычислением крите­рия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х *. Достоинство метода в том, что можно найти глобальный мак­симум критерия, если R(x) — многоэкстремальная функция. К недостаткам данного метода относится значительное число вычислений R(x), что в случае сложной функции R(x) требует существенных затрат времени.

Метод основан на (рис.1) делении текущего отрезка [a, b], где содер­жится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точ­ках, отстоящих от середины отрезка на / 2, где — погрешность решения задачи оптимизации. Если R(x + /2) > R(x - /2), то максимум располагается на пра­вой половине текущего отрезка [а, b],

Рис.1.

противном случае — на левой (рис.2).

Рис.2.

Процесс поиска завершается при достижении отрезком [a, b] величины заданной погрешности .К недостаткам метода относится его работоспособность толь­ко для одноэкстремальных функций R(x) (т.е. таких, которые со­держат один экстремум того типа, который мы ищем в задаче),так как в других случаях при сравнении двух критериев в сосед­них точках невозможно правильно выбрать следующий интервал, где находится максимум. Пример. Дана функция R(x) = 100*sin(x+1). Найти макси­мум на интервале: [-1, 2]. Ошибка задается по х: =0,05.Результаты расчетов. Середина отрезка х= 0,5, значение критерия R =99.75, значение R(0,5 -/2) =R(0,475) = 97.92, значение R(0,5 +/2) =R(0,525) =99.89. Следо­вательно, искомый максимум лежит в правой половине отрезка, т.е. теперь отрезком является [0,5, 2J.

3.2.3. Метод золотого сечения

Метод основан на делении текущего отрезка [a, b] , где содер­жится искомый экстремум, на две неравные части, подчиняющие­ся правилу золотого сечения, для определения следующего отрез­ка, содержащего максимум.

Рис. 3. Иллюстрация метода золотого сечения.

Золотое сечение определяется по правилу: отношение всего отрезка к большей его части равно отношению большей части от­резка к меньшей. Ему удовлетворяют две точки с и d, располо­женные симметрично относительно середины отрезка.

Если ab=1, ad=x, тогда x=0.38197

Путем сравнения R(c) и R(d) определяют следующий отрезок, где содержится максимум. Если R(d) > R(c), то в качестве сле­дующего отрезка выбирается отрезок [a, c],

Рис.4.

Если же R(d) < R(c), то — отрезок [a, c].

Рис.5.

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка c и в том и другом случаях входит в интервал поиска. Поэтому на

каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно зна­чение критерия оптимальности.

Существуют аналитические формулы для расчета новой точ­ки на отрезке, где находится максимальное значение R(x), кото­рую нетрудно получить:

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

Пример. Дана функция R(x)=sin(x+1). Найти макси­мум на интервале: [-1,2]. Ошибка задается по х: e =0,05.

Результаты расчетов. Для "запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]: x1 =0,146, x2 =0,854.

Значения критериев в этих точках соответственно R(x1) =0,911, R(x2 =0,960. Следовательно, новым отрезком яв­ляется [0,146,2], внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрез­ка будет x3 =0,583, a R(x3) =0,999