Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

При построении процесса оптимизации стараются сократить объем вычислений и время поиска. Этого достигают обычно путем сокращения количества вычислений значений целевой функции f(x). Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод золотого сечения.

Если известно, что функция f(x) унимодальная на отрезке [a,b], то положение точки минимума можно уточнить, вычислив f(x) в двух внутренних точках отрезка. При этом возможны две ситуации:

	f(x1)<f(x2) Минимум реализуется на отрезке [a, x2].
f(x1)>f(x2) Минимум реализуется на отрезке [x1, b].

Рис. 4.

В методе золотого сечения каждая из точек x ₁ и x₂ делит исходный интервал на две части так, что отношение целого к большей части равно отношении большей части к меньшей, т.е. равно так называемому "золотому отношению". Это соответствует следующему простому геометрическому представлению:

Здесь

или

(6)

Обозначив

получаем

откуда

Итак, длины отрезков [a,x₁] и [x₂,b] одинаковы и составляют 0,382 от длины (a,b). Значениям f(x₁) и f(x₂) определяется новей интервал (a,x₂) или (x₁,b), в котором локализован минимум. Найденный интервал снова делится двумя точками в том же отношении, причем одна из новых точек деления совпадает с уже использованной на предыдущем шаге.

Взаимное расположение точек первых трех вычислений можно показать следующим образом:

1) f(x₁)<f(x₂)

Первый шаг
Второй шаг

2) f(x₁)≥f(x₂)

Первый шаг
Второй шаг

Рис. 5

Таким образом, длина интервала неопределенности на каждом шаге сжимается с коэффициентом 0,618. На первом шаге необходимы два вычисления функции, на каждом последующем - одно.

Длина интервала неопределенности после S вычислений значений f(x) составляет:

(7)

Алгоритм метода золотого сечения для минимизации функции f(x) складывается из следующих этапов:

1. Вычисляется значение функции f(x₁), где x₁=a+0,382(b-a).
2. Вычисляется значение функции f(x₂), где x₁=b+0,382(b-a).
3. Определяется новый интервал (a,x2) или (x1,b), в котором локализован минимум.
4. Внутри полученного интервала находится новая точка (x₁ в случае 1) или (x₂ в случае 2), отстоящая от его конца на расстоянии, составляющем 0,382 от его длины. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 3, до тех пор, пока величина интервала неопределенности станет меньше или равна ε, где ε - заданное сколь угодно малое положительное число.

Блок-схема алгоритма поиска минимума функции f(x) методом золотого сечения.

Рис. 6.

Пример.

Используя метод золотого сечения, минимизировать функцию f(х)=x²+2х на интервале (-3,5). Длина конечного интервала не­определенности не должна превосходить 0,2.

Решение.

Первый шаг. a=-3, b = 5, b-a = 8.

x₁= -3 + 0,362∙8 = 0,056;

x₂ = 5 - 0,382∙8 = 1,944;

f(x₁)= 0,056² +2∙0,056 =0,115;

f(x₂)= I,944² + 2∙1,944=7,667;

f(x₁)<f(x₂). Новый отрезок [-3; 1,944].

Второй шаг. a=-3, b = 1,944, b-a =4,944.

x₁ = -3+ 0,382∙4,944 = -1.112;

x₂= 0,056;

f(x₁)= (-1,112)² + 2∙(-1,112) = -0.987;

f(x₂)=0,115;

f(x₁)<f(x₂). Новый отрезок [-3; 0,056].

Дальнейшие вычисления оформим в виде таблицы. Значения функции f(x₂), вычисленные на каждом шаге, помечены звездочкой.

После восьми шагов, содержащих девять вычислений функции, интервал неопределенности равен (-1,112; -0,936), его длина 0,176 <0,2. В качестве точки минимума может быть взята середина этого интервала -1,024; при этом f(-1,024)=-0,999. Заметим, что точкой точного минимума является -1,0; f(-1,0)=-1.

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

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

Если важно добиться надежной работы алгоритма, то целесообразно выбрать метод золотого сечения.