 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Методы одномерной минимизации
|
|
Сначала рассматриваются прямые методы. Первые два из них ориентированы на поиск безусловного минимума, остальные – на поиск минимума на заданном непрерывном интервале.
8.7.1. Метод деления шага пополам
Начальная точка и начальный шаг задаются на основе предварительных знаний о функции. Движение с неизменным шагом в одном направлении продолжается пока значение функции уменьшается. При увеличении значения направление меняется на противоположное и шаг уменьшается в два раза. Поиск заканчивается, когда при очередном шаге значение ухудшилось, а длина шага меньше заданной точности (рис. 8.8). Очевидно, что после прохождения минимума происходят колебания вокруг него с уменьшающейся амплитудой.
Алгоритм.
1. Задать начальную точку x 0, начальный шаг h 0 и точность e; k =0.
2. Вычислить f (xk).
3. xk +1 = xk + hk.
4. Вычислить f (xk +1).
5. Если f (xk +1)< f (xk), то hk +1= hk и идти на 9.
6. Если hk < e, перейти на 10.
7. Если k =0, то hk +1= - hk и идти на 9.
8. hk +1= - hk /2;
9. k = k +1и перейти на 3.
10. Конец.▲
Проверка в п.7 необходима для того, чтобы не уменьшать шаг до достижения окрестности минимума. После окончания алгоритма в качестве оптимального x* может быть взято любое значение между xk и xk +1. При сильной изменчивости функции в окрестности минимума условие п.6 можно заменить на (hk < e) & (f (xk +1) – f (xk)< ef), где ef – точность по функции.
8.7.2. Квадратичная аппроксимация
Для нахождения приближенного минимума исходная функция аппроксимируется функцией второго порядка
, (8.35)
где х 0 – точка отсчета реального диапазона значений x, в частности х 0=0. Для определения коэффициентов, входящих в функцию (8.35), выбираются 3 точки и в них вычисляется значение функции f. Получается простая система 3-х уравнений с 3-мя неизвестными a, b и c:
Стационарная точка функции (8.35) вычисляется из равенства ее производной нулю:
. (8.36)
Она используется в условии останова и как новая точка для аппроксимации.
Алгоритм.
1. Задать первую точку x 1, шаг D х и точность по координате e и функции ef.
2. Определить 2-ю точку: x 2= x 1+D х.
3. Вычислить f (x 1) и f (x 2).
4. Если f (x 2)< f (x 1), принять x 3= x 2+D х, иначе x 3= x 1-D х.
5. Вычислить f (x 3).
6. Вычислить fm =min{ f (x 1), f (x 2), f (x 3)} и определить точку xm, соответствующую fm.
7. По трем точкам и значениям функции в них найти коэффициенты в (8.35).
8. Вычислить xa по формуле (8.36).
9. Если (| fm - f (xa)|< ef) & (| xm - xa |< e), окончить поиск.
10. Если fm < f (xa), взять xm и две ближайшие к ней точки, иначе взять xa и две ближайшие к ней точки. Выбранные точки пронумеровать в порядке возрастания значений, вычислить f в новой точке и перейти на 6.
8.7.3. Метод деления интервала пополам
Этот метод, как и два следующих, относится к методам сокращения интервала неопределенности. Предполагается, что точка минимума находится на заданном интервале [ a, b ].
Рассматриваемый метод также называют трехточечным. Точки выбираются так, что делят интервал на 4 равные части (рис. 8.9):
xm =(a+b)/2, x 1=(a+ xm)/2, x 2=(xm + b)/2.
Функция вычисляется в этих точках и после сравнения ее значений интервал сокращается в 2 раза. С новым интервалом действия повторяются.
Алгоритм.
1. Задать точность по координате e.
2. Вычислить xm и f (xm).
3. Вычислить x 1 и x 2.
4. Вычислить f (x) в этих точках.
5. Если f (x 1) < f (xm), то принять b = xm, xm = x 1. Иначе, если f (x 2) < f (xm), положить a= xm, xm = x 2 , иначе – a= x 1, b = x 2.
6. Если b - a < e, закончить поиск, иначе перейти на 3.
Нетрудно подсчитать, что после n вычислений функции интервал неопределенности уменьшится в 
раз. Доказано, что этот метод эффективнее других прямых методов, использующих равноудаленные точки.
8.7.4. Метод золотого сечения
Золотое сечение – это определенное отношение части к целому. Отрезок АВ делится точкой С в отношении золотого сечения (рис. 8.10), если
. (8.37)
Положим АВ = 1, АС = х, СВ = 1 – х, тогда из (8.37) получаем уравнение
х 2 + х – 1 = 0,
из которого следует
, 
.
Эти отношения используются для выбора двух точек внутри интервала неопределенности. Они располагаются, как показано на рис. 8.11. Каждая из точек делит интервал [ a, b ] в отношении золотого сечения.
В этих точках вычисляется функция. Если f (x 1) > f (x 2), то отбрасывается часть интервала [ a, x 1], если f (x 1) < f (x 2), то отсекается часть [ x 2, b ], а при равенстве значений функции – любая из них. Оставшаяся часть интервала равна 
от величины исходного. Очевидно, что после такого сокращения интервала одна из внутренних точек остается с изменением индекса, а вторая берется на основе золотого сечения или, что одно и то же, симметрично оставшейся (рис. 8.12). Сокращение интервала продолжается до достижения заданной точности.
Алгоритм.
1. Задать точность по координате e.
2. Вычислить 
3. 
Вычислить f (x 1), f (x 2).
4. Если f (x 1)> f (x 2), положить a=x 1, x 1= x 2, 
или x 2= a+b-x 1, иначе – b=x 2, x 2= x 1, или x 1= a+b-x 2.
5. Если (b-a)< e, закончить поиск.
6. Вычислить функцию в новой точке и перейти на 4.▲
Итерации алгоритма графически иллюстрируются на рис. 8.12.
Покажем, что сохраняемая точка (x 1 или x 2) делит сокращенный интервал также в отношении золотого сечения. Пусть на k -й итерации внутренние точки делят интервал [ ak, bk ] в отношении золотого сечения. Обозначив 
= bk - ak, 
имеем
.
Тогда для нового, сокращенного, интервала находим
,
В результате получаем:
.
Благодаря этому свойству, внутренние точки не сливаются при любом числе итераций.
Согласно алгоритму функция вычисляется 2 раза на начальном интервале и по одному разу на всех последующих. Поэтому после n вычислений функции интервал неопределенности составит 
от величины первоначального. При заданной точности можно найти необходимое количество вычислений функции n из условия
8.7.5. Метод Фибоначчи
Схема метода почти полностью совпадает с методом золотого сечения. Отличие в том, что вместо золотого сечения используется отношение чисел Фибоначчи: на k- й итерации доли малого и большого отрезков интервала равны 
и 
соответственно.
Числа Фибоначчи Fn вычисляются по известным соотношениям: F 0= F 1=1, Fn = Fn -1 + Fn -2, n³2.
Точки x 1 и x 2вычисляются по формулам:
, (8.38)
. (8.39)
Как видно, они идентичны приведенным в предыдущем разделе. Однако если при использовании золотого сечения внутренние точки не могут сливаться, то здесь это не так. Действительно, при k = n -1 из (8.38) и (8.39) имеем
, 
.
Но так как F 0/ F 2= F 1/ F 2=1/2, то 
и, следовательно, точки сливаются в середине интервала. Поэтому до начала итераций необходимо определить значение n, гарантирующее достижение минимума с заданной точностью e. После 1-й итерации длина интервала составит 
от величины исходного, после 2-й – (
)(),…, после (n -1)-й –
.
Значит, длина последнего интервала будет равна (b 1- a 1)/ Fn, где [ a 1, b 1] – исходный интервал. Для обеспечения заданной точности требуется, чтобы
или 
. (8.40)
Таким образом, соотношение (8.40) позволяет определить номер числа Фибоначчи по исходным данным. На начальном интервале точки вычисляются по формулам (8.38) и (8.39) при k= 1. На последующих итерациях числа Фибоначчи не требуются, так как одна точка переносится из предшествующей итерации, а вторая берется симметрично ей, то есть лучше использовать вторые формулы из п.4 алгоритма золотого сечения.
После слияния внутренних точек остается неопределенность с положением минимума. Для ее устранения вторая точка берется слева или справа от центра на расстоянии e 1@(0,01¸0,05) e. Для случая сдвига второй точки влево (рис. 8.13) при f (x 1)< f (x 1- e 1) минимум лежит в интервале (2), в противном случае – в интервале (1).
Метод Фибоначчи является самым эффективными из всех прямых методов. Очень близок к нему метод золотого сечения: при n >9 они практически совпадают по эффективности и чем больше n, тем ближе эти методы. А в пределе отношение, используемое в методе Фибоначчи на 1-й итерации, становится равным золотому сечению:
.
Дата публикования: 2015-01-23; Прочитано: 1235 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
