Форум на Исходниках.RU

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

MBo — Fri, 15 Feb 2008 04:52:44 +0000

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

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

Катенька — Thu, 14 Feb 2008 15:53:29 +0000

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

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

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

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

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

MBo — Thu, 14 Feb 2008 15:40:31 +0000

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

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

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

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

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

Катенька — Thu, 14 Feb 2008 14:53:58 +0000

Катенька: 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;

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

experimenter — Mon, 31 Mar 2003 14:56:25 +0000

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

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

shadeofgray — Mon, 31 Mar 2003 14:38:17 +0000

shadeofgray:

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

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

experimenter — Mon, 31 Mar 2003 13:46:02 +0000

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

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

shadeofgray — Mon, 31 Mar 2003 06:24:11 +0000

shadeofgray:

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

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

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

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

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

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

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

tserega — Mon, 31 Mar 2003 05:32:46 +0000

tserega: Если это про поиск минимума (если -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" несколько минимумов (максимумов)!

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

experimenter — Mon, 31 Mar 2003 03:50:27 +0000

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