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

Сначала введем некоторые предварительные определения и сведения. Функция называется унимодальной, если на некотором интервале a < x< b у нее существует единственный экстремум. Рассмотренные далее методы позволяют определить локальный экстремум. Любую функцию можно построить и график полностью покажет ее поведение на конкретном интервале. Поэтому выбор интервала, на котором производится поиск экстремума, следует выполнять осознанно. Далее необходимо определить стратегию его последовательного уменьшения. Это самая сложная проблема. Можно использовать идеи метода дихотомии или выбирать произвольные участки разбиения интервала по x и отслеживать изменение функции. Но эффективность таких расчетов будет очень низкой.

Исходный интервал, на котором производиться поиск экстремума, будем называть первоначальным интервалом неопределенности. Выберем следующую стратегию уменьшения этого интервала. Разделим его на три части так, чтобы расстояние от начала и конца интервала до точек деления совпадали по длине . Эти участки симметричны относительно середины исходного интервала [0, 1]. См. рис. 5.1.

Рис.5.1.

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

Фибоначчи доказал, что, если известно количество итераций, необходимое для расчета экстремума функции, то можно определить начальный интервал неопределенности L₂ . Поскольку разбиение исходного интервала производится симметрично относительно его концов, то L₁=L₂. При этом необходимо соблюдать указанное выше правило: точка расчета функции на первых интервалах неопределенности должна быть использована для последующих расчетов, поэтому на каждом новом интервале неопределенности функция считается лишь один раз.

Число требуемых итераций n используется для определения числа Фибоначчи F_n, которое позволяет определить начальные интервалы неопределенности L₁ и L₂ с учетом заданной точности ε.

Числа Фибоначчи определяются по рекуррентному соотношению , при этом Если знать F_n, то можно получить решение за n-1 итерацию. Но число итераций заранее не известно. Поэтому использовать метод Фибоначчи практически затруднительно.

НоФибоначчи доказал, что уменьшение интервалов неопределенности при больших n происходит умножением текущего интервала на r = 0.618. Эта идея и используется в методе золотого сечения. Начальный интервал [0, 1] делится на два участка (см. рис.5.2) по правилам золотого отношения. Исходный интервал [0, 1] так относится к большему участку [0, r], как больший участок относится к меньшему [0, 1-r]. Это отношение позволяет получить уравнение золотого отношения . Из него и получено число r = 0.618. Если отсчет вести от начала исходного интервала, то к нему добавляется r, а при отсчете с конца, от него вычитается r.

Если f1< f2, то очередной интервал неопределенности равен [1-r, 1]. А если f₁> f₂,, тоочередной интервал неопределенности равен [0, r]. Легко убедиться, что на очередном интервале неопределенности требуется заново считать лишь одно значение функции, поскольку в оставшейся точке значение функции уже посчитано. Но необходимо переприсвоить значения аргумента и функции, чтобы сохранить алгоритм расположения точек, составленный для исходного интервала.

Присваивание значений аргумента и функции показаны в тексте на рис.5.2 и 5.3. На новом интервале неопределенности рис.5.2 считается функция , а на рис. 5.3 считается функция .

Рис. 5.2 Рис. 5.3

Если интервал неопределенности выбран ошибочно, то результатом расчета будет значение функции на границе с минимальным значением функции.

Далее показана программа на MATLAB, реализующая метод золотого сечения:

function [S, E, G]=golden(fungold, a, b, delta, epsilon)

%Вход:

%fungold функция вводится как строка 'fingold'

%[a, b]-начальный интервал поиска минимума

%delta-допустимое отклонение для абсцисс

%epsilon допустимое отклонение для ординат

%Выход:

%S=(p, yp)-абсцисса и ордината минимума

%E=(dp, dy)-грани ошибок по абсциссе и ординате

%G-матрица размером nx4: k-я строка содержит [ak ck dk bk];

%значения a, c, d и b на k-ой итерации

%Обращение из МАTLAB: [S, E, G]=golden('fungold', 0.5, 1.5, 0.001, 0.0001)

r1=(sqrt(5)-1)/2;

r2=r1^2;

h=b-a;

ya=feval('fungold', a);

yb=feval('fungold', b);

c=a+r2*h;

d=a+r1*h;

yc=feval('fungold', c); yd=feval('fungold', d);

k=1;

A(k)=a; B(k)=b; C(k)=c; D(k)=d;

while (abs(yb-ya)> epsilon)|(h> delta)

k=k+1;

if (yc< yd) b=d;

yb=yd;

d=c;

yd=yc;

h=b-a;

c=a+r2*h; yc=feval('fungold', c);

else a=c; ya=yc; c=d; yc=yd; h=b-a; d=a+r1*h; yd=feval('fungold', d); end

A(k)=a; B(k)=b; C(k)=c; D(k)=d;

end

dp=abs(b-a);

dy=abs(yb-ya);

p=a;

yp=ya;

if(yb< ya) p=b; yp==yb; end

G=[A' C' D' B']; S=[p yp]; E=[dp dy];

x=0.5: 0.01: 1.5;

y=x.^2-2*x+1;

plot(x, y)

grid on

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