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

кто-нибудь может на пальцах рассказать метод золотого сечения на пальцах, плиз?
благодарен заранее.

Если это про поиск минимума (если -f(x), то макчимума) функции, то пожалуйста:

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

Пусть fi = (sqrt(5) - 1) / 2

Есть у нас функция и числовая ось:
      \       /
       \    /
        +-+
     a  b c  d
Минимум лежит между "a" и "d" - это очевидно. Для проверки нам нужна третья и четвертая точки. Координата точки b = a + (d - a)*fi, а точки c = a + (d - a)*(1 - fi).
Короче, так мы сужаем интервал (как в методе деления отрезка пополам), но одну из крайних точек интервала берем уже вычисленную (к примеру, "b"). Тогда уже одна внутренняя точка (в данном случае "c") уже посчитана на предыдущем шаге!!!
То есть производится меньше вычислений функции (для сложных функций это существенный выйгрыш в скорости)

PS: пишу по памяти, как когда-то сам программил. Возможны мелкие недочеты, но идея такая  ;)
PPS: Глучно может быть, если на интервале от "a" до "b" несколько минимумов (максимумов)!

Цитата tserega, 31.03.03, 09:32:46

Идея вот в чём - если функция F унимодальна, т.е. на отрезке [a,b] существует такое X, что на [a,X] F строго убывает, а на [X,b] строго возврастает, и есть значения функции в двух внутренних точках a<U1<U2<b, то можно сказать, на каком из отрезков [a,U2] или [U1,b] находится точка X.
Если F(U1)<F(U2), то X на [a,U2], иначе X на [U1,b].
Так вот, уменьшив размер зоны поиска, можно провести процедуру ещё раз. Остается вопрос выбора точек - можно выбирать точки U1=(a+b)/2-epsilon, U2=(a+b)/2+epsilon и уполовинивать область поиска, но на каждом шагу придётся расчитывать значение функции два раза. А можно делить отрезок на части золотым сечением и на каждом шаге использовать значения функции, вычисленные на предвдущем шагу.

Скажем, выбрали отрезок [a,U2], тогда за вторую точку берём U1, а за первую - симметричную U1 относительно центра нового отрезка. И на каждом шаге вычисляем значение функции только один раз.

Цитата tserega, 31.03.03, 09:32:46

PPS: Глучно может быть, если на интервале от "a" до "b" несколько минимумов (максимумов)!

Верно. Но метод разработан как раз для функций определённого типа, хотя и применяется на практике в более общем случае, скажем когда надо просто уменьшить значение функции.

спасибо, мужики, обоим. не могли бы вы пояснить еще как использовать значения
ф-ии на предыдущем шаге. все пучком, когда выбираем интервал
[a,U2]  - там, как я понимаю U1 используется, а когда [U1,b] чего делать с U2?
и почему именно используется
(sqrt(5) - 1) /2 а не чего-нибудь близкое, но рациональное?

Цитата EXPERIMENTER, 31.03.03, 17:46:02

пояснить еще как использовать значения ф-ии на предыдущем шаге. все пучком, когда выбираем интервал
[a,U2]  - там, как я понимаю U1 используется, а когда [U1,b] чего делать с U2?

использовать U2 в качестве левой точки, а правой брать симметричную ей. Вообще, если интересна реализация, посмотри http://shadeofgray.narod.ru/, там в нижней части страницы, в разделе "Примеры программ"\"Золотое сечение" в html формате приведён алгоритм золотого сечения. Детали реализации можно будет выяснить именно там.

Цитата EXPERIMENTER, 31.03.03, 17:46:02

и почему именно используется
(sqrt(5) - 1) /2 а не чего-нибудь близкое, но рациональное?

Сначала рассмотрим метод с точки зрения чистой математики, а потом применим его к компам. Золотое сечение - симметричный метод, т.е. на каждом шаге новая точка выбирается симметрично к одной из ранее построенных (симм. к U1, если на интервале [a,U2] и симм. к U2, если на интервале [U1,b]). Проблема в том, что если в начале делить отрезок точками почти пополам (т.е. отступая от середины на epsilon в обе стороны), то на первом шаге отрезок почти уполовинивается. Но на втором шаге от отрезка будет откушен лишь маленький кусочек в 2*epsilon длиной. А на следующем - опять в 2*epsilon, и опять и опять... Если же точки выбирать по указанной формуле, то на каждом шаге они будут делить отрезок в одних и тех же пропорциях.

Теперь о рациональных числах: хотя в курсе методов оптимизации точки выбираются из соображений симметрии, но на компе золотое сечение в принципе нельзя провести точно, и если выбирать новую точку действительно, как симметричную, т.е. U3 = U1 + (b-U2), то на первых шагах всё будет ОК, но через некоторое время из-за погрешностей в расчётах точки станут разъезжаться к краям отрезка и скорость сходимости упадёт. Поэтому при реализации на компе на каждом шаге явно проводится золотое сечение отрезка, т.е. U3 = U1 + (b-U1)*(sqrt(5)-1)/2,
что позволяет удерживать точки близкими к идеальному золотому сечению.
Т.е. можно было бы выбрать и что-то более рациональное, чем всякие корни, но
а)математически более удобно исследовать сходимость симметричного метода
б)нутром чую, что чем ближе к золотому сечению, тем лучше сходится - а доказывать лень.

Сообщение отредактировано: shadeofgray - 31.03.03, 14:39

ага, спасибо. ;D

shadeofgray, скажите, пожалуйста, что за код такой ? Вот отсюда http://alglib.sources.ru/optimization/goldensection.php

(*************************************************************************
Процедура минимизации значения функции методом золотого сечения.
 
Оптимизирует функцию одного  переменного F.
 
Параметры:
    A,B      - отрезок [A,B], на котором ищется минимум функции F.
    N        - число шагов метода
 
После выхода переменные A и B содержат границы   отрезка,  на  котором
находится решение задачи.
 
Алгоритм проводит 2+N вычислений функции F.
*************************************************************************)
procedure GoldenSectionOptimize(var A : Double;
     var B : Double;
     const N : Integer);
var
    i : Integer;
    S1 : Double;
    S2 : Double;
    U1 : Double;
    U2 : Double;
    FU1 : Double;
    FU2 : Double;
begin
    S1 := (3-Sqrt(5))/2;
    S2 := (Sqrt(5)-1)/2;
    U1 := A+S1*(B-A);
    U2 := A+S2*(B-A);
    FU1 := F(U1); <--- как это понимать ?  :unsure:
    FU2 := F(U2);
    i:=1;
    while i<=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;
        Inc(i);
    end;
end;

FU1 := F(U1); <--- как это понимать ?

Это значит, что нужно использовать свою функцию, минимум которой ищется
например

function F(x: Double): Double;
begin
Result := Sin(x);
end;

A := Pi;
B := 2 * Pi;
GoldenSectionOptimize(A, B, 100);

Сообщение отредактировано: MBo - 14.02.08, 15:42

\\ нужно использовать свою функцию

аа понятно, спасибо .

Добавлено 14.02.08, 16:35
\\ нужно использовать свою функцию

да это понятно, но вот всё таки не пойму, нужно использовать функцию, которая ищет именно минимум числа ? Всё таки не понятно .

>да это понятно, но вот всё таки не пойму, нужно использовать функцию, которая ищет именно минимум числа ? Всё таки не понятно
Задача оптимизации - найти минимум заданнной функции на определенном отрезке.
Вот исследуемую функцию и надо использовать