билет 12 1 вопрос

Билет 12, вопрос 1

Методы одномерной оптимизации (метод половинного деления, метод золотого сечения)

Оптимизация – нахождение экстремума в некоторой области конечномерного пространства, ограниченного набором линейных/нелинейных равенств/неравенств. Одномерная оптимизация – нахождение экстремума для функции одной переменной.

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

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

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

1.

f(x1)f(x2)

Минимум реализуется на отрезке [ax2].

2.

f(x1)>f(x2)

Минимум реализуется на отрезке [x1b].

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

Здесь

или

(6)

 

Обозначив

получаем

откуда

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

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

1) f(x1)f(x2)

 

 

 

Первый шаг

 

 

 

Второй шаг

 

2) f(x1)≥f(x2)

 

 

 

Первый шаг

 

 

 

Второй шаг

Рис. 5

 

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

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

(7)

 

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

Вычисляется значение функции f(x1), где x1=a+0,382(b-a).

Вычисляется значение функции f(x2), где x1=b+0,382(b-a).

Определяется новый интервал (a,x2) или (x1,b), в котором локализован минимум.

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

Метод половинного деления

Метод половинного деления один из методов решения нелинейных уравнений и основан напоследовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до того времени, пока не будет достигнута заданная точность ɛ.

Пусть задан отрезок [а,b], содержащий один корень уравнения. Предварительно необходимо определить области локализации корней данного уравнения. Если на отрезке [а,b] содержится более одного корня, то метод не работает.

Алгоритм метода:

Разобьем отрезок [а,b] пополам. Определим новое приближение корня х в середине отрезка [а,b]:

х=(а+b)/2.

Найдем значения функции в точках а и х: F(a) и F(x).

Проверим условие F(a)*F(x)

В этом случае необходимо точку b переместить в точку х (b=х). Если условие не выполнено, то корень расположен на отрезке [х,b]. В этом случае необходимо точку а переместить в точку х (а=х).

Перейдем к пункту 1 и вновь поделим отрезок пополам. Алгоритм выполнять до тех пор, пока не будет выполнено условие /F(x)/