1.7.2. Метод дихотомии ( половинного деления.).

Если мы вычислим значения f в двух точках x₁,x₂ , то станет возможным исключение из рассмотрения некоторого множества точек, на котором гарантировано нет минимума, то есть имея измерения в двух точках можем сократить интервал поиска.

Как лучше выбирать точки, чтобы процесс быстрее сходился?

В методе дихотомии предлагается (отрезок [0,1] ).

Остается один из интервалов:. Выберем 3-й и 4-й эксперимент на-пару в середине оставшегося интервала. После n (n-четно) экспериментов min функции лежит в интервале .

Здесь каждый раз два эксперимента, но можно один, а в качестве другого брать один из предыдущих.

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

Интервал [a,b], вычислить функцию в точках .

На интервале [a,b] расположен минимум функции.

, где F₁ и F₂ некоторые числа 0<F₁<1, 0<F₂<1.

Анализируем перегибы функции внутри интервала, и также, как раньше, заменяем отрезок [a, b] на или. Идея метода в том, чтобы после замены, необходимо было вычислить только одну точку при гарантированном уменьшении длины отрезка, т.е.

, так как

(после замены отрезок уменьшится в 1/ F₂ = 

В новом отрезке должно быть(по правилу «золотого» сечения): так как

Тогда так как ,, то.

Таким образом, уменьшение интервала в 1/ F₂ =  раз достигается с помощью вычисления функции в одной новой точке (см. процедуру выполнения). После n экспериментов имеем интервал неопределенности:

.

В пересчете на одно измерение этот метод лучше дихотомии.

Процедура выполнения:

Рассмотрим [a, b], вычислить функцию в точках .

1. 

2. 

В выражениях 1) и 2) появилась только одна новая точка. И так далее, пока длина отрезка [a, b] не станет меньше заданной величины.

1.7.4. Метод Фибоначчи.

Пусть у нас существует ограничение на количество вычисляемых точек N. Как выбирать средние точки , чтобы максимально уменьшить интервал, внутри которого лежит точка min?

, к- номер итерации.

F_j - числа Фибоначчи, обладающие свойством.

F_k+2 = F_k+1+ F_k

Два первых: 1;1

Как метод Фибоначчи связан с методом «золотого» сечения?

.

То есть асимптотически один метод переходит в другой. Окончательный интервал в методе «золотого» сечения всего на 17% больше чем в методе Фибоначчи. Если количество измерений не задано, то используется метод «золотого» сечения, если задано - то Фибоначчи.

2. Условная минимизация.

2.1 Задача нелинейного программирования.

Решается задача минимизации функции f на множестве X, заданном набором ограничений g.

Множество- называется допустимым множеством.

g_i- некоторые гладкие функции.

2.1.1. Ограничения типа равенства.

Рассмотрим следующий пример: найти.

Пусть g разрешима относительно x₁, то есть g(x₁,x₂)=0 x₁= (x₂), x₁,x₂.

Тогда

Функции f,  - дифференцируемы. Запишем условие экстремальности: . Так как

Обозначим

Тогда:

, из определения 

Таким образом, в точке минимума выполняются эти соотношения. Получить эти необходимые условия можно, используя функцию Лагранжа:

F(x,)=f+g.

Тогда необходимое условие min функции f(x₁,x₂) при наличии ограничений может быть записано следующим образом:

Таким образом, задача условной минимизации сведена к задаче безусловной минимизации. Для решения последней задачи можно использовать ранее описанные методы.