Идея метод делить отрезок пополам, отбрасывать ту часть где экстремума быть не может, оставшиеся часть вновь делить по полам и так далее.
Рассматривается унимодальная функция.
После каждого шага отрезок на котором локализуется минимум уменьшается в два раза.
Sk= s/2k<=э вычисления прекращаются
S7=S/27=S/128=0,01
27=24 вычислений
Метод золотого сечения (гармоническое деление или деление в крайнем и среднем отношение)
Здесь исходный отрезок [a, b] делится не на целое число отрезков, а в некотором иррациональном отношение.
В геометрии золотым сечением называется такое деление отрезков на 2 неравные части при котором отношение длины всего отрезка к его большей части равно отношению большей части к меньшей.
s/s1=s1/s2
пусть s=1, тогда s2=1-s1.
1/s1=s1/1-s1=s12(1-s1)1=s12+s1-1=0
S1,2=-1/2+-sqrt(1/4+1)=(-1+sqrt5)/2=0,618
S2=1-s1=0,382
Свойство золотого сечения:
Если в исходном отрезке [a, b] точки x1 и х2 выбрать так, чтобы они находились на расстояние 0,38 от длины отрезка, то в его любом под интервале можно так выбрать положение следующий точке, которое также находится на расстояние 0,38 длины выбранного отрезка и т.д. пока не будет достигнута точность.
Относительная погрешность E= /\ /b-a=1/2*0,62k-3, где k число вычислений. В частности при k=21 получается 0,9*10-4
Здесь точность в 10 раз выше чем в методе локализации.
Метод с использованием чисел Фибоначчи
Числами Фибоначчи последовательностью чисел называются числа определяемые по рекуррентной форме
F0=F=k-1+Fk+2, F0=1, F1=1
K 0 1 2 3 4 5
F0 1 1 2 3 5 6
Эти числа используют при поиске экстремума функции одной переменной.
Если требуется найти в положение экстремума функции f(x) на [a, b] с абсолютной ошибкой не больше, чем /\ = b-a/Fk=S/Fk
То для поиска экстремума достаточно вычислить не более k-значений f(x).
K=21
/\ =b-a/F0-1
E= /\ /(b-a)=L/F21=1/17.371=0,56*10-4
Первые 2 вычисления производятся в точках х1 и х2, и выбираем наименьшее значение. Отрезок на котором локализуется экстремум располагается на отрезке 0,х2.
Далее этот отрезок добавляется точкой х3, который располагается симметрично точки х1 относительно середины отрезка 0,х2.
Эта точка расположена на расстояние Fn-2=Fn-3. В точке х3 вычисляется Fx3 и сравниваются с предыдущем значением и т.д. пока не будут использованы все числа Фибоначчи.
При каждом вычисление длина отрезка локализации минимума при каждом вычислении равна 1-a/Fk.
Число Фибоначчи FN выбирается следующим образом по заданной абсолютной точности дельта выбирают F:=> /\:b-a/ /\ = /\ Fk-1< /\ <FN
Далее определяемый минимальный шаг поиска /\ =b-a.АТБ=допущена
Недостаток: ищет локальный экстремум, для унимодальной функции.
Метод ДСК (Дэвис, Свенн, Кэмпи)
Идея метода проводятся возрастающие по величине шаги до тех пор, пока не будет пройден минимум, а затем выполняется квадратичная интерполяция.
Интерполяция – это приближенное или точное нахождение какой либо величины по известным значениям её или других величин связанных с ней. /\ x- первоначальный шаг.
После того как будет пройден минимум и осуществляется возврат назад на шаг равный предыдущему и оставляют 4 ближайшие точки. Из них отбрасывают самую неблагоприятную. Через 3 оставшихся точки можно провести интерполяционный полином и выразить значение х*через 3 оставшихся точки х*+f(3 ост. точек и значение функций в них). Если х* находится далеко от полученных точек, то процедуры повторяют с новым шагом /\ x! И т.д. пока не будет получена точность.
Совершаются шаги 3 первых шага (с одинаковым шагом) в направление поиска. Вычисляются в них значения f(x) и проводится квадратическое аппроксимация.
Аппроксимация – это замена одних математических объектов другими в том или ином смысле близкими.
Если х* находится на расстояние от х3 меньше чем E, то решение найдено, в противном случае из точки х* с новым шагом меньшим /\ x, осуществляется аналогичный поиск.
Метод ДСК- Пауэлла
Это комбинация 2-х предыдущих, которые их эффективнее обоих. На первом этапе работает ДСК, после того как найден х* работает Пауэлл. Также методы существует на ряду с методом сканирования или прямого поиска и другие методы поиска глобального экстремума: метод ломанных, метод покрытий и другие, которые значительно сложнее предыдущих.
f(x)->extr (max, min)
при больших числах Фибоначчи превращается в золотое сечение.
