Метод локализации экстремума

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

Рис.1.4.9. Интервал поиска [xmin, xmax] разбивается на несколько частей

Весь интервал поиска [xmin, xmax], как и в методе сканирования, разбивается на несколько частей (подынтервалов) точками x1, x2 и x3, но более крупных размеров.

Вычисляется значение критерия R(x) во всех точках разбиения и в точках xmin, xmax.

Все значения R(x) сравниваются между собой и из них выбирается наименьшее, если ищем минимум, и наибольшее, если ищем максимум. Далее выбирается новый интервал поиска, равный двум подынтервалам, с наименьшим (наибольшим) вычисленным значением R на их общей границе (на рисунке это соответствует интервалу [xmin, x2].

Этот интервал меньше исходного и в нем локализован экстремум. Затем поступают следующим образом. Интервал, в котором локализован экстремум, делят на несколько подынтервалов (на рисунке точками 1 и 2) и снова вычисляют значения критерия оптимальности в точках деления. Сравнивают их между собой, находят наименьшее, локализуют экстремум в меньшем интервале (на рисунке в интервале 1–2) и т.д. до тех пор, пока экстремум не будет локализован в интервале, размер которого соответствует заданной точности поиска.

Наилучшие результаты поиска получаются в том случае, когда первоначальный интервал [xmin, xmax] разбивается на четыре равных поди нтервала (n = 4). При этом каждый последующий подинтервал делится пополам и вычислять значение функции нужно только в двух новых точках, так как ее значения на концах нового интервала и в его середине известны из предыдущих расчетов.

Абсолютная ошибка в нахождении экстремума

в этом случае определяется выражением:

s – количество точек, в которых вычисляется значение критерия оптимальности.Так, при s = 21, относительная ошибка составит:

 

Метод Золотого сечения

1. Дан отрезок [a;b] (рис.1.4.10) на котором определена функция f(x) и точность e. Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек x1=a и x4=b и вычислим Z=(3-√5)/2.

2. Делим отрезок на три части и определяем точку x2=x1+Z(x4-x1) и точку x3=x4-Z(x4-x1). Вычисляем значения функции в этих точках F2=f(x2) F3=f(x3).

3. Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как x1=x1, x4=x3, x3=x2, F3=F2 x2=x1+z(x4-x1) F2=f(x2) иначе x1=x2, x4=x4, x2=x3 F2=F3 x3=x4-z(x4-x1)
F3= f(x3).

4. Проверяем условие окончания итерационного процесса | x4-x1 | £ 2e. Если оно выполняется, то определим решение, как x=(x4+x1)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 3.

Введем понятие эффективности, как отношение доли сокращения отрезка к количеству вычисления функции на одной итерации тогда Q=0,3819/1≈0,3819

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

D D d d L x1 x2 x3 x4 x4 x3 x2 x1

Рис.1.4.10. Разбиение отрезка

делим на

Заменяем

Решая получим

 

 Шаговые методы