Файл: Метод Фибоначчи.docx

Значения аргумента в точках расчёт определяется по следующей формуле:. Крайние точки отрезка получаются прии. Из полученных значений функции выбирается наименьшее значение. Номер наименьшего значения и определяет оценку положения экстремума с точностью не хуже, чем заданная величина.

Пример

Пусть определена на отрезке. Найтис точностью. Рассчитаем необходимое число точек, для этого вычислим выражение. Округлив до ближайшего целого получаем. Реализуемая точность равна, что лучше заданной точности.

Рассчитаем значение аргумента в 9 точках по формуле: .

	1	2	3	4	5	6	7	8	9
	1	1.5	2	2.5	3	3.5	4	4.5	5

Рассчитаем значения функции в каждой точке:

	1	2	3	4	5	6	7	8	9
	1	1.5	2	2.5	3	3.5	4	4.5	5
	9	6.25	4	2.25	1	0.25	0	0.25	1

---

Сравнивая значения функции в 9 точках, находим: .

---

Правило исключения интервалов

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

Пусть на замкнутом интервале функцияунимодальна, а её минимум достигается в точке. Рассмотрим точкии, расположенные на интервале таким образом, что. Сравнивая значения функции в точкахи, можно сделать следующие выводы:

• если , то точка минимумане лежит в интервале, т.е.

• если , то точка минимумане лежит в интервале, т.е.

• если , то можно исключить оба крайних интервалаи. При этом точка минимума должна располагаться в интервале, т.е.

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

---

В процессе применения методов исключения интервалов можно выделить два этапа:

• Установление границ интервала, содержащего экстремум. В поисковых задачах оптимизации отрезок, на котором располагается точка минимума, называют интервалом неопределённости.

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

Унимодальность

В общем виде задача оптимизации формулируется следующим образом: минимизировать функцию , для всех, принадлежащих допустимой области. Если ограничения отсутствуют, то областьрасширяется до открытого действительного пространства, и задача называется задачей безусловной оптимизации. Учёт дополнительной информации о функции может сделать поиск экстремума (обычно будем подразумевать поиск минимума) более эффективным. Например, о функции может быть известно, что она имеет только один экстремум, или что она монотонна, или что её вторая производная всюду сохраняет знак и т.п.

Среди возможных дополнительных сведений о функции наиболее ценным и наименее обременительным является её свойство унимодальности (одноэкстремальности).

Определение: функция является унимодальной на отрезкев том и только в том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки.

Иначе говоря, если - единственная точка минимума функциина отрезке, тооказывается унимодальной на этом интервале тогда и только тогда, когда для точеки:

---

• из следует, что

• из следует, что

Надо отметить, что унимодальная функция не обязательно должна быть непрерывной. Унимодальность функций является исключительно важным свойством, которое широко используется в оптимизационных исследованиях.

ШАГИ АЛГОРИТМА ПАУЭЛЛА

~~~~~~~~~~~~~~~~~~~~~~

ШАГ 1: ВЫЧИСЛИТЬ X2 = x1 + d, F2 = F(X2), F1 = F(X1)

ШАГ 2: ЕСЛИ F1 > F2, ПОЛОЖИТЬ X3 = X2 + d

ЕСЛИ F1 <=F2, ПОЛОЖИТЬ X3 = X1 - d. ВЫЧИСЛИТЬ F3 = F(X3)

ШАГ 3: НАЙТИ Fmin = min [F1,F2,F3] И СООТВЕТСТВУЮЩЕЕ Xmin

ШАГ 4: ПО ТОЧКАМ 1,2,3 ВЫЧИСЛИТЬ ЭКСТРЕМУМ АППРОКСИМ.ПОЛИНОМА ПО

ФОРМУЛАМ (2),(3),(4)

ШАГ 5: ПРОВЕРИТЬ, ВЫПОЛНЯЕТСЯ ЛИ УСЛОВИЕ:

- -

|Fmin - F | <= E1 |Xmin - X | <= E2

ГДЕ E1 И E2 - ТОЧНОСТЬ РЕШЕНИЯ ПО ФУНКЦИИ И АРГУМЕНТУ.

ЕСЛИ УСЛОВИЯ ВЫПОЛНЕНЫ -ЗАКОНЧИТЬ ПОИСК.ЗА X* ПРИНЯТЬ ЛУЧШУЮ

-

ИЗ Xmin И X .ЕСЛИ НЕТ - ПЕРЕЙТИ К ШАГУ 6. -

ШАГ 6: ВЫБРАТЬ "ХУДШУЮ" ИЗ ТРЕХ ТОЧЕК, ПРИСВОИТЬ ЕЙ ЗНАЧЕНИЕ X ,

ОСТАВИВ ПРЕЖНИЙ ИНДЕКС.ПЕРЕЙТИ К ШАГУ 4.

7. МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

~~~~~~~~~~~~~~~~~~~~~~~~~~

МЕТОД ЗОЛОТОГО СЕЧЕНИЯ СОСТОИТ В ПОСТРОЕНИИ ПОСЛЕДОВАТЕЛЬНОСТИ

ОТРЕЗКОВ [a0,b0], [a1,b1], ..., СТЯГИВАЮЩИХСЯ К ТОЧКЕ МИНИМУМА ФУН-

КЦИИ F(X). НА КАЖДОМ ШАГЕ, ЗА ИСКЛЮЧЕНИЕМ ПЕРВОГО, ВЫЧИСЛЕНИЕ ЗНАЧЕ-

НИЯ ФУНКЦИИ ПРОИЗВОДИТСЯ ЛИШЬ В ОДНОЙ ТОЧКЕ. ЭТА ТОЧКА, НАЗЫВАЕМАЯ

"ЗОЛОТЫМ СЕЧЕНИЕМ", ВЫБИРАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ.

ПУСТЬ ДЛИНА ИСХОДНОГО ИНТЕРВАЛА НЕОПРЕДЕЛЕННОСТИ РАВНА L,

А ТОЧКА ДЕЛИТ ЕГО НА ДВЕ ЧАСТИ: L1 И L2 , ПРИЧЕМ L1 > L2 И

L1 + L2 = L.

"ЗОЛОТОЕ СЕЧЕНИЕ" ИНТЕРВАЛА НЕОПРЕДЕЛЕННОСТИ ВЫБИРАЕТСЯ

ТАК, ЧТОБЫ ОТНОШЕНИЕ ДЛИНЫ БОЛЬШЕГО ОТРЕЗКА К ДЛИНЕ ВСЕГО ИН-

ТЕРВАЛА РАВНЯЛОСЬ ОТНОШЕНИЮ ДЛИНЫ МЕНЬШЕГО ОТРЕЗКА К ДЛИНЕ БОЛЬ-

ШЕГО ОТРЕЗКА: L1/L = L2/L1 ...(*).

ИЗ ЭТОГО СООТНОШЕНИЯ НАЙДЕМ ТОЧКУ ДЕЛЕНИЯ.

ОБОЗНАЧИМ ОТНОШЕНИЕ L2/L1 ЧЕРЕЗ T. ПОДСТАВИМ ЕГО

В УРАВНЕНИЕ (*). ПОЛУЧИМ:

L1/(L1 + T*L1) = T

СОКРАТИВ ДРОБЬ НА L1 , ПОЛУЧИМ: T*T + T - 1 = 0

РЕШЕНИЕ ЭТОГО УРАВНЕНИЯ ДАЕТ :

T = 0.5 *(-1 + SQR(5)) = 0.61804...

ТАКИМ ОБРАЗОМ, ПРИ ЗОЛОТОМ СЕЧЕНИИ ДЛИНА БОЛЬШЕГО

---