Материал: 862

случайным образом.

2.1.Методы поиска экстремума одномерных функций

Кдетерминированным методам поиска экстремума одномерных функций относятся следующие:

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

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

метод золотого сечения;

метод с использованием чисел Фибоначчи.

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

Сущность этого метода заключается в том, что весь рассматриваемый интервал (Хmin – Xmax) разбивается на n одинаковых подынтервалов (рис. 4). На концах интервала и в точках его разбиения вычисляются значения целевой функции. Затем производится сравнение полученных величин друг с другом и из них выбирается наибольшее значение, если определяется max, и наименьшее, если min.

R(x)

R(x0)

x

Рис. 4. Геометрическая интерпретация метода сканирования

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

15

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

1 0,05.

xmax xmin 20

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

На первом этапе решения весь интересующий нас диапазон изменения неизвестной разбивается на крупные подынтервалы (рис. 5, точки х1, х2, х3). Затем вычисляют значение целевой функции

на концах рассматриваемого отрезка и в точках его разбиения и выбирают из них экстремальное, т.е. наибольшее при поиске max и наименьшее при определении min.

R(x)

x

Рис. 5. Геометрическая интерпретация метода локализации экстремума

В рассматриваемом примере определяется минимум целевой функции, а это будет соответствовать точке х1. Интересующую нас точку, имеющую экстремальную величину функции цели, окружают прилегающими подынтервалами таким образом, что рассмотренный интервал сужается до xmin x2, а остальную часть x2 xmax в рассмотрение не берут. Новый интервал xmin x2 разбивают вновь на подынтервалы. Вычисляют значение целевой функции в новых точках разбиения 1 и 2. С учетом значений целевой функции, вычисленных для точек xmin, x1, x2, определенных на предыдущем шаге, находят экстремальное значение функции из всех точек разбиения интервала xmin x2 . Это будет точка 1. Далее точку,

16

имеющую экстремальное значение целевой функции, окружают новыми подынтервалами, которые образуют новый отрезок [x1-x2]. При этом отрезок (xmin – x1) исключается из поля зрения исследователя.

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

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

Предположим, что S=21, тогда относительная ошибка определения экстремума рассматриваемой функции составит

2 10 0,001.

xmax xmin

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

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

Воснове этого метода лежит геометрическое соотношение или закон золотого сечения. Если весь отрезок обозначить через а, большую его часть - b, меньшую - с, то закон золотого сечения устанавливает следующую связь:

Определим, при каких условиях возможно выполнение соотношения (13). Для этого рассмотрим отрезок единичной длины

(рис. 6) .

Z 1 Z

Рис. 6. Деление отрезка по закону золотого сечения

Большую его часть обозначим через Z, а меньшую (1-Z); исходя из этого, имеем согласно соотношению (12)

Отсюда получаем Z=0,618.

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

При этом выдерживаются следующие соотношения:

На рис. 7 дана геометрическая интерпретация рассматриваемого метода. Далее определяется величина целевой функции на концах отрезка и в точках разбиения. Полученные результаты сравниваются между собой и из них выбирается наилучшая точка, соответствующая экстремальному значению критерия оптимальности, которую окружают прилегающими подынтервалами. Скажем, в рассматриваемом примере пусть будут точками разбиения точки Х1 и Х2 и в точке Х2 функция достигает своего наименьшего значения. Тогда отрезок (Х1 Xmax) исключается из дальнейшего рассмотрения. Таким образом, рассматриваемый участок будет (Xmin–Х1), который

18

вновь разбивается по закону золотого сечения с использованием формул (16) – (18).

R(x)

x

Рис. 7. Геометрическая интерпретация метода золотого сечения

При этом нетрудно видеть, что новый участок в рассматриваемом примере (Xmin–Х1)=Z a, отсюда необходимо дополнительно определить координаты только одной точки и величину функции отклика при ней. Шаговый метод повторяется до тех пор, пока величина интервала не будет меньше или равной заданной точности поиска.

Метод золотого сечения обеспечивает следующую точность поиска:

где S – количество точек, в которых вычисляется целевая функция. Для сравнения данного метода с методом локализации

экстремума предположим, что число точек, в которых вычисляется целевая функция, S=21, тогда точность поиска составит

0,5 0,6218 0,9 10 4.

xmax xmin

На этой основе можно сделать вывод: метод золотого сечения обеспечивает более высокую точность поиска по сравнению с методом локализации экстремума.

19