12. (29) Методы одномерной оптимизации дихотомии и Фибоначчи.

Метод дихотомии (деления отрезка пополам).

Идея метода состоит в вычислении на каждой очередной итерации двух значений целевой функции в точках, отстоящих на величину α в обе стороны от середины интервала неопределенности. Величина α в этом методе называется константой различимости, такова, что, с одной стороны, величина 2α была близка к желаемому конечному значению интервала неопределенности, с другой, значения оптимизируемой функции на краях интервала 2α были различимы.

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

Введем обозначения: ε – конечная длина интервала, определяющая точность, [a₁, b₁] – начальный интервал неопределённости, k – номер итерации. Пусть на k-м шаге . На этом отрезке выберем две точки.

Точки , выбираются близко от середины интервала на расстоянии 2α > ε от середины [a; b]:

Вычислим значения функции в этих точках и выполним процедуру исключения отрезка, то есть

если , то , иначе .

Таким образом, построим новый отрезок . Длина интервала неопределенности после k-ой итерации

За n итераций последующий отрезок уменьшается примерно в . Для достижения точности ε необходимо

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

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

Последовательность определяется следующим образом:

Пробные точки вычисляются по формулам:

Число итераций выбирается до начала вычислений и обусловлено требуемой точностью .

На k-м шаге имеется интервал , вычисляем по формулам.

Если , то

Если , то

13. (30) Методы одномерной оптимизации, использующие информацию о производной.

Рассмотрим 3 метода:

- метод средней точки

- метод Ньютона (метод касательной)

- метод секущих

Метод средней точки

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

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

Метод Ньютона (метод касательной)

Если функция строго унимодальная и дважды непрерывно дифференцируема, то точку минимума можно найти методом Ньютона.

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

На (k+1)-м шаге по найденной на предыдущем шаге точке x_k можно найти точку .

Для надёжной работы этого метода необходимо, чтобы вторая производная в некоторой окрестности искомой точки сохраняла знак, а начальная точка выбиралась из такой окрестности.

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

Метод секущих

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

Таким образом, можно избежать вычислений производной второго порядка, заменяя её конечной разностью .

Выбор начальной точки . Если на отрезке [a, b] функция имеет знакопостоянную третью производную , то в качестве x₀ выбирают тот конец отрезка, на котором совпадают знаки производных первого и третьего порядков: .

Данный метод имеет такой коэффициент сжатия интервала неопределённости: - отношение золотого сечения.