При построении процесса оптимизации стараются сократить объем вычислений и время поиска. Этого достигают обычно путем сокращения количества вычислений значений целевой функции f(x). Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод золотого сечения.
Если известно, что функция f(x) унимодальная на отрезке [a,b], то положение точки минимума можно уточнить, вычислив f(x) в двух внутренних точках отрезка. При этом возможны две ситуации:
| f(x1)<f(x2) Минимум реализуется на отрезке [a, x2]. |
| f(x1)>f(x2) Минимум реализуется на отрезке [x1, b]. |
Рис. 4.
В методе золотого сечения каждая из точек x 1 и 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. На первом шаге необходимы два вычисления функции, на каждом последующем - одно.
Длина интервала неопределенности после S вычислений значений f(x) составляет:
| (7) |
Алгоритм метода золотого сечения для минимизации функции f(x) складывается из следующих этапов:
1. Вычисляется значение функции f(x1), где x1=a+0,382(b-a).
2. Вычисляется значение функции f(x2), где x1=b+0,382(b-a).
3. Определяется новый интервал (a,x2) или (x1,b), в котором локализован минимум.
4. Внутри полученного интервала находится новая точка (x1 в случае 1) или (x2 в случае 2), отстоящая от его конца на расстоянии, составляющем 0,382 от его длины. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 3, до тех пор, пока величина интервала неопределенности станет меньше или равна ε, где ε - заданное сколь угодно малое положительное число.
Блок-схема алгоритма поиска минимума функции f(x) методом золотого сечения.
Рис. 6.
Пример.
Используя метод золотого сечения, минимизировать функцию f(х)=x2+2х на интервале (-3,5). Алина конечного интервала неопределенности не должна превосходить 0,2.
Решение.
Первый шаг. a=-3, b = 5, b-a = 8.
x1= -3 + 0,362∙8 = 0,056;
x2 = 5 - 0,382∙8 = 1,944;
f(x1)= 0,0562 +2∙0,056 =0,115;
f(x2)= I,9442 + 2∙1,944=7,667;
f(x1)<f(x2). Новый отрезок [-3; 1,944].
Второй шаг. a=-3, b = 1,944, b-a =4,944.
x1 = -3+ 0,382∙4,944 = -1.112;
x2= 0,056;
f(x1)= (-1,112)2 + 2∙(-1,112) = -0.987;
f(x2)=0,115;
f(x1)<f(x2). Новый отрезок [-3; 0,056].
Дальнейшие вычисления оформим в виде таблицы. Значения функции f(x2), вычисленные на каждом шаге, помечены звездочкой.
| Таблица 1 | |||||||
| № шага | a | b | b-a | x1 | x2 | f(x1) | f(x2) |
| -3,000 | 5,000 | 8,000 | 0,056 | 1,944 | 0,115* | 7,667* | |
| -3,000 | 1,944 | 4,944 | -1,112 | 0,056 | -0,987* | 0,115 | |
| -3,000 | 0,056 | 3,056 | -1,832 | -1,112 | -0,308* | -0,987 | |
| -1,832 | 0,056 | 1,888 | -1,112 | -0,664 | -0,987 | -0,887* | |
| -1,832 | -0,664 | 1,168 | -1,384 | -1,112 | -0,853* | -0,987 | |
| -1,384 | -0,664 | 0,720 | -1,112 | -0,936 | -0,987 | -0,996* | |
| -1,384 | -0,936 | 0,448 | -1,208 | -1,112 | -0,957* | -0,987 | |
| -1,208 | -0,936 | 0,272 | -1,112 | -1,032 | -0,987 | -0,999* | |
| -1,112 | -0,936 | 0,176 |
После восьми шагов, содержащих девять вычислений функции, интервал неопределенности равен (-1,112; -0,936), его длина 0,176 <0,2. В качестве точки минимума может быть взята середина этого интервала -1,024; при этом f(-1,024)=-0,999. Заметим, что точкой точного минимума является -1,0; f(-1,0)=-1.
Методы дихотомии
| Содержание · 1 Введение · 2 Метод половинного деления o 2.1 Метод половинного деления как метод поиска корней функции § 2.1.1 Изложение метода § 2.1.2 Реализация метода на С++ и числовой пример o 2.2 Метод половинного деления как метод оптимизации · 3 Метод хорд o 3.1 Изложение метода · 4 Комбинация метода хорд и метода половинного деления · 5 Список литературы · 6 См. также |
Введение
Существует довольно очевидная теорема: "Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)". На базе этой теоремы построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется дихотомией, т.е. делением отрезка на две части. Обобщенный алгоритм выглядит так:
1. Задать начальный интервал 
;
2. Убедиться, что на концах функция имеет разный знак;
3. Повторять
§ выбрать внутри интервала точку 
;
§ сравнить знак функции в точке со знаком функции в одном из концов;
§ если совпадает, то переместить этот конец интервала в точку ,
§ иначе переместить в точку другой конец интервала;
пока не будет достигнута нужная точность.
Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд.
Метод половинного деления
Метод половинного деления известен также как метод бисекции. В данном методе интервал делится ровно пополам.
Такой подход обеспечивает гарантированную сходимость метода независимо от сложности функции - и это весьма важное свойство. Недостатком метода является то же самое - метод никогда не сойдется быстрее, т.е. сходимость метода всегда равна сходимости в наихудшем случае.
Метод половинного деления:
1. Один из простых способов поиска корней функции одного аргумента.
2. Применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).