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

Метод золотого сечения применяется для поиска минимума функции одного переменного на отрезке. Метод использует следующее свойство непрерывных функций: если точки 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. Т.е. на каждом шаге вычисляется только одно значение функции (и ещё два в самом начале работы).

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

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Реализация алгоритма на AlgoPascal:

unit GoldenSectionUnit;

declaration
function F(X:Real):Real;

interface GoldenSectionOptimize;

implementation

(*********************************************************************
Процедура минимизации значения функции методом золотого сечения.

Оптимизирует функцию одного  переменного F.

Параметры:
    A,B      - отрезок [A,B], на котором ищется минимум функции F.
    N        - число шагов метода

После выхода переменные A и B содержат границы   отрезка,  на  котором
находится решение задачи.

Алгоритм проводит 2+N вычислений функции F.
*********************************************************************)
procedure GoldenSectionOptimize(var A:Real; var B:Real; const N:Integer);
var
    i        : Integer;
    S1       : Real;
    S2       : Real;
    
    U1       : Real;
    U2       : Real;
    
    FU1      : Real;
    FU2      : Real;
begin
    //вычисляем позиции первой и второй секущих точек
    S1 := (3 - Sqrt(5))/2;
    S2 := (Sqrt(5) - 1)/2;
    U1 := A + S1*(B-A);
    U2 := A + S2*(B-A);

    //вычисляем функцию в точках
    FU1 := F(U1);
    FU2 := F(U2);

    //шаги метода
    for i:=1 to N do
    begin
        if FU1<=FU2 then
        begin
            B   := U2;
            U2  := U1;
            FU2 := FU1;
            U1  := A + S1*(B-A);
            FU1 := F(U1);
        end
        else
        begin
            A   := U1;
            U1  := U2;
            FU1 := FU2;
            U2  := A + S2*(B-A);
            FU2 := F(U2);
        end;
    end;
end;

end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU