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

Метод золотого сечения применяется для поиска минимума функции одного переменного на отрезке. Метод использует следующее свойство непрерывных функций: если точки g и h (g < h) расположены на (a, b) и f(g) ≤ f(h), то на отрезке [a, h] есть хотя бы один минимум функции. Аналогично, если f(g) ≥ f(h), то на отрезке [g, b] есть хотя бы один минимум.

Метод золотого сечения выбирает на отрезке две симметричные точки: g = A+(B-A)•(3-Sqrt(5))/2 и h = A+(B-A)•(Sqrt(5)-1)/2. Применяется указанная выше процедура, приводящая к отрезку [A, h] или [g, B] (для определенности рассмотрим первый вариант). Если повторить указанную процедуру, то можно опять уменьшить отрезок. Важным свойством алгоритма является то, что на каждом шаге можно использовать одно значение функции из предыдущего шага, т.к. при новом разбиении отрезка [A, h] точками h' и g', мы увидим, что h' = g. Т.е. на каждом шаге вычисляется только одно значение функции (и ещё два в самом начале работы).

Метод обладает стабильной линейной скоростью сходимости, не зависящей от рельефа функции.

Золотым сечением отрезка называют деление отрезка на две части так, что отношение длины
всего отрезка к длине большей его части равно отношению длины большей части к меньшей.
Золотое сечение отрезка [c,d] производят две симметрично расположенные точки x1,x2:
x1=c+(1-v)*(d-c), x2=c+v*(d-c), где v=(-1+sqrt(5))/2=0.6180339. При этом x1 производит
золотое сечение [c,x2], а x2 - золотое сечение [x1,d].
При составлении подпрограммы метода золотого сечения в качестве параметров
подпрограммы желательно указать следующие:
Входные параметры:
c, d - граничные точки отрезка, внутри которого содержится только один экстремум;
f - имя функции;
eps - точность вычисления абциссы экстремума;
Выходные параметры:
x0 - абцисса точки экстремума;
m - переменная, по значению которой можно судить, является ли найденный экстремум
max или min : m=1 соответствует max, а m=-1 - min;
ier - код ошибки; ier=0 если экстремум найден; ier=1 если экстремума на [c,d] нет.
Опишем возможный алгоритм поиска max функции m*f(x) на участке [c,d] (m={1,-1}). a)
выполним проверку наличия экстремума на [c,d]: если [f(c+t)-f(c)] * [f(d+t)-f(d)]>0, то ier=1 и
осуществляется возврат в вызывающую программу; в противном случае ier=0 и
осуществляется поиск экстремума;
b) для сохранения исходных значений c, d определим новые переменные: c1=c,d1=d.
c) вычислим значение m: если f(c1+t)-f(c1)>0, то m=1, иначе m=-1.
d) вычислим значения x1, x2: x1=c1+(1-v)*(d1-c1), x2=c1+v*(d1-c1).
e) вычислим значения функции в точках x1, x2: y=m*f(x1), z=m*f(x2).
f) если yeps повторяем (f).
h) за точку max функции m*f(x) принимаем точку x0=(d1+c1)/2.
При вычислении G=max|f(x)| надо иметь в виду, что функция f(x) может достигать max
(min) либо в точках экстремумов, либо на концах отрезка [a,b].

Powered by Drupal - Design by artinet