Minimum функции

← →
romychk (2003-01-02 00:07) [0]

Уважаемые мастера, где можна найти алгоритм поиска минимума функции одной переменной, или нескольких. Как можна найти все минимумы функции?

← →
Andryk (2003-01-02 01:47) [1]

Ну вообще-то если мне не изменяет память,
Точки экстремума - это точки в который первая производная равняется нулю. А минимум это или максимум можно определить очень просто:
- если в точке х первая производная меняет знак с минуса на плюс, то это минимум
- если в точке х первая производная меняет знак с плюса на минус, то зто максимум
- если производная не меняет знака, то это просто экстремум.

Ну а численых методов вычисления производных есть очень много, один вытекает собственно говоря из определения производной.

← →
romychk (2003-01-02 11:22) [2]

Меня интересуют численные методы.

← →
romychk (2003-01-02 11:40) [3]

Может кто видел поиск всех минимумов

← →
romychk (2003-01-02 13:09) [4]

Помогите же кто нибудь П О Ж А Л У Й С Т А!!!!

← →
Andryk (2003-01-02 13:20) [5]

Ну как я уже написал, один метод вытекает из самого определения производной,
Определение если говорить простым языком:
это предел отношения приращения функции к приращению аргумента.
т.е
f(x) - f(x+dx) lim --------------- dx->0 dx

ну и все алгоритм очень простой выбираешь dx достаточно малым и просто пробегаешь по некоторому диапазону, и приравниваешь к нулю, естественно точно нулю она вряд ли будет равна, поэтому там тоже надо сделать некоторую дельта окрестность, простым языком точность.
Ну а более сложные и более точные методы это тебе надо взять учебник по численым методам, и посмотреть там.

← →
romychk (2003-01-03 00:03) [6]

Мне нужен более точный метод, можна и просто пройтись по всему отрезку и найти минумум, но это не то :) учебника под рукрй нет, да и вряд ли появится в ближайшее время, я живу в маленьком городке, и таких книг в бибилиотеке нет :)

← →
Мазут Береговой (2003-01-03 01:35) [7]

Если тебе надо это все запрограммировать, то алгоритм такой:
1. Имеется массив значений. Заводишь цикл. Кладешь в некую переменную значение первого элемента и сверяешь его со всеми остальными (начиная со второго);
2. Если по пути находиться какой-то элемент меньшего значения, то вместо первого запоминаешь найденный и продолжаешь до конца массива;
3. Каждый раз встречая меньшее значение выполняешь пункт 2;

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

← →
Мазут Береговой (2003-01-03 01:37) [8]

Кажется, я не то ляпнул...

← →
Andryk (2003-01-03 02:40) [9]

Ну у меня тоже по рукой нет учебника по ЧМ. Но в принципе производную тебе все равно именно по этой формуле надо будет находить.
Единственное что могу посоветовать, ну скажем что на ум приходит,
это поиск корня уравнения методом хорд(хотя может он и по другому называется). Сразу скажу что пишу для одной переменной.

Пусть e - это точность с которой мы находим корень
1. берем точку х
2. вычисляем в ней производную
3. сравниваем с модуль производной с e, если меньше то это точка экстремума, переходим к процедуре проверки на минимум максимум.
4. прибавляем к x = x + dx
5. вычисляем производную
6. сравниваем с модуль производной с e, если меньше то это точка экстремума, переходим к процедуре проверки на минимум максимум.
6. если знак производной поменялся, то dx = -dx/2 и переходим к 4, иначе просто переходим к 4.

В приципе сходимость этого метода довольно неплохая.

← →
romychk (2003-01-03 12:21) [10]

Беда в том, что мне надо найти глобальный минимум, я гдето встречал такой алгоритм, а теперь на ум ничего не приходит (он был какойто статистический, автор кажется Стронгин), если кто видел или алгоритм, или готовую программу.

← →
Ru (2003-01-03 12:34) [11]

ну ты и не угомонный.
1. ищешь по описаным выше алгоритмам первый минимум
2. запоминаешь минимум
3. ищешь по описаным выше алгоритмам второй минимум
4. сравниваешь
5. Если второй минимальнее, то 2. иначе 3. если функция закончилась выход.

← →
romychk (2003-01-03 13:10) [12]

Надо знать на каком отрезке искать (или выбирать другую первую точку), надо знать сколько их есть...

Я думаю достаточно причин не выдумивать велосипед а найти алгоритм придуманый умными людьми.

← →
sosv (2003-01-03 14:53) [13]

Функция задана аналитически?
Область задания функции ограничена?

← →
Pingo (2003-01-03 18:01) [14]

Минимум или есть или функция стремится к минус бесконечности по вертикальной асимптоме (что значит все точки минимума???).
Для этого Вам достаточно найти область опреления и первую и вторую производные. Таким образом Вы получаете точки перегибов и максимум/минимум, область возрастания/убывания функции, но это без программирования...
P.S. Или я чего-то очень не понимаю в условии задачи.

← →
romychk (2003-01-03 20:14) [15]

Надо численно решить задачу: найти Min функции f(x) на отрезке [a, b], но дело в том, что на этом отрезке может быть несколько локальных минимумов, мне надо найти самый минимальный ;). а в большинстве методов все зависит от начальной точки.

← →
_vitek_ (2003-01-03 20:52) [16]

http://www.srcc.msu.su/num_anal/lib_na/cat/cat94.htm

← →
p77 (2003-01-03 21:00) [17]

Однако там нет того, о чем человек спрашивает.
>romychk
Лучше всего возьмите книгу по числ. методам и разберитесь сами - это будет Вам лучшей наукой.

← →
_vitek_ (2003-01-03 22:27) [18]

Приведу примеры программ для нахождения минимума
функции одной переменной

1.Метод половинного деления

const k=0.1;
var
a,b,c,d,d1,e,x1,x2,y1,y2:real;

function f(x:real):real;
begin
f:=2*x*x-ln(x)...// ваша ф-я
end;

begin
read(a,b); // отрезок
read(e); // точность
repeat
d:=b-a;
c:=(a+b)/2;
d1:=k*(b-a)/2;
x1:=c-d1;
x2:=c+d1;
y1:=f(x1);
y2:=f(x2);
if y1<y2 then b:=x2;
if y1>y2 then a:=x1;
if y1=y2 then begin a:=x1; b:=x2; end;
until d < e;
writeln("минимум ",a," погешность=",d);
end.

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

var
a,b,d,d2,e,x1,x2,y1,y2:real;

function f(x:real):real;
begin
f:=...;
end;

procedure beginning;
var
k,c,d1:real;
begin
k:=sqrt(5)-2;
c:=(a+b)/2;
d1:=k*(b-a)/2;
x1:=c-d1;
x2:=c+d1;
y1:=f(x1);
y2:=f(x2);
end;

begin
read(a,b);
read(e);
beginning;
repeat
d:=b-a;
d2:=x2-x1;
if y1<y2 then
begin
b:=x2; x2:=x1; y2:=y1; x1:=a+d2; y1:=f(x1);
end else
begin
if y1>y2 then
begin
a:=x1; x1:=x2; y1:=y2; x2:=b-d2; y2:=f(x2);
end else begin a:=x1; b:=x2; beginning; end;
end;
until d<e;
writeln("min=",a," greh=",d);
end.

3.Метод сканирования

const k=4;
var
a:bool; d,e,h,x,x1,y,y1:real;

function f(x:real):real;
begin
f:=...;
end;

begin
read(x);
read(e);
h:=0.2; x1:=x; y:=f(x);
repeat
d:=abs(h); x1:=x1+h; y1:=f(x1); a:=(y1>=y);
if a then h:=-h/k;
x:=x1; y:=y1;
until a and (d<e);
x:=x+h*k;
writeln("min=",x," pogr=",d);
end.

← →
romychk (2003-01-04 01:34) [19]

_vitek_

1) не правильный показывает минимум
sin(100*x-0.15)*10*x*x*exp(cos(x)*x)+25

2) не правильный показывает минимум
sin(100*x-0.15)*10*x*x*exp(cos(x)*x)+25

3) не правильный показывает минимум
sin(100*x-0.15)*10*x*x*exp(cos(x)*x)+25

Эти методы годятся когда на отрезке ЕСТЬ ОДИН минимум ;)

← →
romychk (2003-01-04 10:22) [20]

Может, кто знает какието числительные методы поиска всех минимумов.

← →
spb (2003-01-04 10:41) [21]

А в чем проблема? Вычисляешь последовательно F(x(i)) для x(0)=a, x(1)=x(0)+h, x(2)=x(1)+h, ..., x(n)=b. Для всех отрезков [x(i),x(i+2)], где F(x(i) > F(x(i+1) & F(x(i+1)) < F(x(i+2)) применяешь в качестве уточняющего любой из методов нахождения ОДНОГО минимума. После того как найдешь все минимумы, выбираешь из них наименьший. Здесь все дело в том, чтобы правильно выбрать h. При слишком большом h есть риск пропуска одного из минимумов, при слишком маленьком будет долго считать.

← →
romychk (2003-01-04 11:08) [22]

Дело в том, что мне надо какой нибудь научный метод, а вот его я найти не могу.

← →
Alx2 (2003-01-04 11:27) [23]

>romychk (04.01.03 11:08)
Точного общего метода поиска глобальных экстремумов нет.
Некоторую уверенность, что найден именно глобальный экстремум, может дать применение генетических алгоритмов (www.basegroup.ru)

← →
Roger (2003-01-04 11:36) [24]

Единственный способ найти минимумы функции, это взять первую производную функции и приравнять её к нулю. Найди корни этого уравнения и ты получишь АБСОЛЮТНО ВСЕ!!!!! экстремумы данной функции (если они вообще есть). После этого берёшь вторую производную своей функции в найденных точках (в точках экстремума) и смотришь на её знак. Если результат >0 то это МИНИМУМ, если <0, то МАКСИМУМ. Это всё. Повторяю что это ЕДИНСТВЕННЫЙ (кроме прямого перебора значений) всегда верный способ нахождения экстемумов функции.
Исходя из вышесказанного можно утверждать, что если ты не ставишь перед собой задачу создать программу вычисляющую производные двух порядков от любой функции (что в принципе возможно, и об этом писал > Andryk © (02.01.03 13:20)
) то остаётся другой ТОЧНЫЙ (в пределах возможности компьютера) способ о котором уже говорил > Мазут Береговой (03.01.03 01:35)
это метод прямого перебора значений функции на заданном интервале. перебирай все значения и выбери из них наименьшее.

← →
Alx2 (2003-01-04 12:17) [25]

← →
Roger (2003-01-04 12:22) [26]

Если я допустил ошибку, то поправьТЕ, а ко мне обращаться можно и нужно на ты (я же помладше) :-)

← →
Alx2 (2003-01-04 12:37) [27]

>Roger © (04.01.03 12:22)

>Единственный способ найти минимумы функции, это взять первую
>производную функции и приравнять её к нулю.

Не единственный. И далеко не всегда возможно взять производную. А если можно взять, то не всегда можно найти все ее нули (пример автора из этой серии: в данном случае вычислительная погрешность неаналитически (потому-что аналитических нулей здесь не получится, кроме точки x=0) найденных нулей первой производной играет огромную роль.)

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

Способ "особенно эффективен", когда интервал, например, неограниченный. Или когда каждое значение функции вычисляется очень дорого.

С целью поиска глобального экстремума (для произвольных непрерывных "плохих" функций на компактах) чаще используют либо аппроксимации, если функция "хорошо" аппроксимируется, либо метод случайного поиска с некоторыми эвристиками (Монте-Карло, генетические алгоритмы). После получения кандидата на глобальный экстремум, для улучшения результата еще "обшаривают" его окрестности. Но все это еще не дает оснований утверждать, что будет найден именно глобальный экстремум.

← →
romychk (2003-01-04 13:02) [28]

Поиск всех корней производной, можна сказать та же задача. Но мне обещали дать книгу Стронгина где описан статистический метод поиска глобального минимума, но я получил только лист на котором есть только приблизительная схема на которой нет всех формул ;(.

← →
Alx2 (2003-01-04 13:10) [29]

>romychk (04.01.03 13:02)
sin(100*x-0.15)*10*x*x*exp(cos(x)*x)+25 - именно эта функция исследуется?
Или интересует подход "вообще"?

← →
romychk (2003-01-05 01:45) [30]

Иследуется не именно эта функция, я должен запрограмировать алгоритм поиска глобального экстремума любой ;) функции, любого количества переменных, для того чтобы можна было использовать любую функию я использую простенький интерпретатор функций (идею интерпретатора нашел в инете), в связи с этим много вычислений проводить тоже не могу, так как разница в быстродействии - порядок. Меня несколько дней не будет, а потом, я наверно снова верну эту ветку к жизни. ;) Посмотрю генетических алгоритм, может он чем то поможет ;) Пока что всем спасибо.
С Рождеством Вас.

← →
spb (2003-01-05 10:34) [31]

>romychk

> запрограмировать алгоритм поиска глобального экстремума
> любой ;) функции, любого количества переменных

Да чего гадать-то? Простой запрос на Яндексе "методы поиска глобального экстремума" дал у меня такой результат: "страниц - 492, серверов - не менее 146". Целые монографии существуют с таким названием! Я уж не говорю про статьи, описывающие поиск экстремума на сетке кода Грея, запудренный в генетический алгоритм. Выбираешь то что нравится - и вперед!

← →
ghg (2003-01-05 13:16) [32]

По моему вы все еще забываете о концах отрезкаю
Они ведь тоже могут быть более минимальны, чем точки экстремумов.

С наилучшими ...

Minimum функции Найти похожие ветки