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

Отличается от дихотомического метода способом выбора промежуточных точек y_k, z_k (где y_k < z_k), который определяется следующими условиями:

1) одна из точек y_k, z_k становится концом нового отрезка [a_k+1, b_k+1], а другая – его промежуточной точкой;

2) на каждой итерации сжатие отрезка поиска производится с одним и тем же коэффициентом λ (λ > 0):

.

Исходя из этих условий получим:

· точки y_k, z_k следует выбирать симметричными относительно середины отрезка [a_k, b_k];

· при a_k+1 = a_k, b_k+1 = z_k, будет z_k+1 = y_k;

при a_k+1 = y_k, b_k+1 = b_k, будет y_k+1 = z_k.

Вычисление коэффициента сжатия λ.

Подставим , в следующее равенство:

, k = 0,1,2,… (7)

Получим уравнение относительно λ:

λ² + λ – 1 = 0.

Единственный подходящий корень .

Свойство. При каждая из точек y_k, z_k осуществляет следующее сечение отрезка [a_k, b_k]:

Схема метода.

Шаг 0. Вычислим точки y₀, z₀ при :

y₀ = a₀ + ₂ = b₀ – λ ₀,

z₀ = b₀ – ₂ = a₀ + λ ₀,

и значения целевой функции f(y₀), f(z₀).

Шаг k (k ≥ 1). Определим новый отрезок поиска [a_k, b_k]. Для этого сравним значения f(y_k–1) и f(z_k–1):

· если f(y_k–1) ≤ f(z_k–1) a_k = a_k–1, b_k = z_k–1, z_k = y_k–1;

вычислим _k+2 по формуле (7),

y_k = a_k + _k+2, значение функции f(y_k);

· если f(y_k–1) > f(z_k–1) a_k = y_k–1, b_k = b_k–1, y_k = z_k–1;

вычислим _k+2 по формуле (7),

z_k = b_k – _k+2, значение функции f(z_k).

Проверка на окончание процедуры поиска.

Количество шагов процедуры k = 1,2,…,n определяется условием точности:

_n = b_n – a_n ≤ ε, ε > 0 – заданное число.

Выбор решения.

В качестве приближения для x_min может быть выбрана оставшаяся промежуточная точка последнего отрезка [a_n, b_n], для которой уже вычислено значение функции (т. е. = y_n или = z_n).

В этом случае: 1) погрешность

| – x_min| ≤ λ∙ _n ≤ λε;

2) степень близости полученного приближенного значения целевой функции и минимума этой функции на [a, b] определяется неравенством:

|f(x_min) – f()| ≤ L∙|x_min – | ≤ L∙ λ∙ _n ≤ Lλε.

Анализ метода.

Длины _k, k = 0,1,2,…, можно вычислить заранее.

Лемма 2. Пусть _k, k = 0,1,2,…, определяются следующими равенствами:

₀ > 0, ₁ = λ∙ ₀, _k+2 = _k – _k+1. (8)

Тогда справедлива формула

_k = _k (λ) = (–1)^k–1(F_kλ – F_k–1) ₀, k = 2,3,…, (9)

где F_k – числа Фибоначчи:

F₁ = F₂ = 1, F_k+1 = F_k + F_k–1

Формула Бинэ:

, k = 1,2,…

Данная формула позволяет вычислить любое число Фибоначчи

Оценка n. Число n шагов процесса, гарантирующее определение x_min с заданной точностью ε > 0, выбирается как наименьшее положительное целое, удовлетворяющее неравенству:

_n = b_n – a_n ≤ ε,

отсюда, с учетом постоянного коэффициента сжатия на каждом шаге

, ,

получим

_n = λⁿ ₀ ≤ ε λⁿ ≤ ε/ ₀ .

Свойство. Из формулы _n = λⁿ ₀ при

_n → 0 при n → ∞,

т. е. метод золотого сечения порождает бесконечную последовательность вложенных отрезков [a_k, b_k], стягивающихся к точке x_min.

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

m = n + 1.

Коэффициент сжатия γ (величина отношения длин конечного и начального отрезков поиска) при данном алгоритме поиска после m вычислений значений функции равен γ = λ^m–1 при .

Например, коэффициент сжатия γ после m = 10 вычислений значений функции равен:

· для дихотомического метода = (1/2)^m/2 = (1/2)⁵ = 0,03125;

(5 итераций)

· для метода золотого сечения γ = λ^m–1 ≈ (0,618)⁹ ≈ 0,013156.

(9 итераций)

т. е. в 2,375 раза длина конечного отрезка поиска для метода золотого сечения меньше, чем для дихотомического метода.

Дата добавления: 2015-07-02