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

Пусть f(x) – кусочно-непрерывна функция на a £ x £ b и имеет на [ a, b ] только один локальный минимум.

Алгоритм метода золотого сечения

Шаг 1.

Задаем функцию f(x);

задаем интервал (x₀, x₁);

задаем погрешность e.

Выбираем внутренние точки на интервале:

x₂=x₀+x(x₁ - x₀), x₃=x₁-x(x₁ - x₀),

где (для метода золотого сечения ).

Шаг 2.

Для шага t: x_i, x_j, x_k, x_l.

Определяем min{f(x_i), f(x_j), f(x_k), f(x_l)}:

пусть f(x_i) < f(x_j), f(x_k), f(x_l).

Отбрасываем ту точку, которая наиболее удалена от x_i:

| x_l - x_i |>| x_j - x_i |,| x_k - x_i |.

Определяем порядок расположения точек на числовой прямой:

x_k<x_i<x_j.

Выбираем новую точку x = x_j + x_k-x_i и присваиваем ей очередной номер.

Шаг 3.

Если max || x_j^(t) - x_k^(t) || £ e, то = (x_j+x_k).

Иначе t = t +1, и переходим на шаг 2.

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

Если на отрезке [ a, b ] несколько локальных минимумов, то он сойдется к одному из них, но не обязательно к наименьшему.