Метод золотого сечения

l₂l₁

Положим l =1, тогда l₂²= 1 - l₂ , а l₂² + l₂ -1= 0,откуда

где k₁, k₂- коэффициенты золотого сечения.

В методе золотого сечения каждая точка (х₁ и х₂)осуществляет золотое сечение отрезка (рис. 1.6.3-1).

Рис. 1.6.3-1

или

Нетрудно проверить, что точка х₁осуществляет золотое сечение не только отрезка [a;b], но и отрезка [a;х₂]. Точно так же точка х₂осуществляет золотое сечение не только отрезка [a;b], но и отрезка [х₁;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Длина конечного отрезка неопределенности D_n = 0.618ⁿD₀, где D₀= (b-a) – начальная длина отрезка.

Условие окончания процесса итераций D_n e. Отсюда можно найти количество итераций, необходимое для достижения точки минимума:

отсюда логарифмируя,получим

Схема алгоритма метода золотого сечения приведена на рис. 1.6.3-2.

Пример 1.6.3-1. Пусть минимум функции f(x) = x³ – x + e^-x отделен на отрезке [0;1]. Определить количества итераций и конечные длины отрезков неопределенности, необходимые для достижения заданных точностей e=0.1 и e=0.01.

При e = 0.1 x*=0.718847, f(x*)=0.139925.

При e = 0.01 x*=0.704139, f(x*)=0.139516.

1.6.3-2. Схема алгоритма поиска минимума методом золотого сечения