2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Метод дробления шага
Сообщение25.12.2014, 09:42 
Аватара пользователя


14/09/12
181
Уфа
Здравствуйте. Мне нужно реализовать метод дробления шага для нахождения минимума двух функций. Я нашел информацию по методу градиентного спуска с дроблением шага, но я не уверен что это то, что мне нужно. Где можно почитать про этот метод? В чем суть метода?

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение25.12.2014, 12:41 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск

(Оффтоп)

netang в сообщении #951935 писал(а):
Мне нужно реализовать метод дробления шага для нахождения минимума двух функций.

Значица так. Дробим шаг пополам. На первой половине шага ищем минимум одной функции, а на второй - другой. :-)

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение25.12.2014, 16:32 
Аватара пользователя


14/09/12
181
Уфа
Цитата:
для нахождения минимума двух функций

:facepalm:

Вернее будет так: для нахождения минимума функции двух переменных

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение26.12.2014, 12:29 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Суть в том, что градиент указывает направление наибольшего возрастания. Если ищешь минимум - ходи против градиента. Проблема лишь в том, какими шагами ходить. От этого зависит (в конкретных условиях), как долго ходить и не будет ли это пустою забавою. Описания есть везде. Вот, к примеру
http://www.machinelearning.ru/wiki/inde ... 0.B3.D0.B0

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение26.12.2014, 14:31 
Аватара пользователя


14/09/12
181
Уфа
Спасибо, стало яснее :idea: Пойду попробую реализовать это дело :arrow:

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение04.01.2015, 20:13 
Аватара пользователя


14/09/12
181
Уфа
Оставлю здесь. Может кому-нибудь пригодится.
Код:
#include <iostream>
using namespace std;
double f(double x, double y)
{
   return 3*x*x-6*x*y+4*y*y+12*x-18*y+21;
}
double gradX(double x, double y)
{
   return 6*x-6*y+12;
}
double gradY(double x, double y)
{
   return -6*x+8*y-18;
}
int main()
{
   double L = 1.0;
   double x = 4, y = -4;
   while(L > 0.005)
   {
      if( f(x - L*gradX(x, y), y - L*gradY(x, y)) <= (f(x, y) - 0.5*L*(gradX(x, y)*gradX(x, y) + gradY(x, y)*gradY(x, y))) )
      {
         x = x - L*gradX(x, y);
         y = y - L*gradY(x, y);
      }
      else
      {
         L = L * 0.5;
      }
   }
   cout << x << "   "  << y << endl;
   return 0;
}

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение05.01.2015, 01:25 
Аватара пользователя


26/05/12
1534
приходит весна?
Очень нерационально производятся вычисления: по нескольку раз одно и то же считается. Компилятор может быть и соптимизирует, а может и нет. Лучше сразу сделать хорошо:
Код:
#include <iostream>
using namespace std;
double f(double x, double y)
{
   return 3*x*x-6*x*y+4*y*y+12*x-18*y+21;
}
double gradX(double x, double y)
{
   return 6*x-6*y+12;
}
double gradY(double x, double y)
{
   return -6*x+8*y-18;
}
int main()
{
   double L = 1.0;
   double x = 4, y = -4;
   double fv = f(x, y);
   while(L > 0.005)
   {
      double gx = gradX(x, y);
      double gy = gradY(x, y);
      double nx = x - L*gx;
      double ny = y - L*gy;
      double nf = f(nx, ny);
      if( nf <= (fv - 0.5*L*(gx*gx + gy*gy)) )
      {
         x = nx;
         y = ny;
         fv = nf;
      }
      else
      {
         L = L * 0.5;
      }
   }
   cout << x << "   "  << y << endl;
   return 0;
}

За одно и понятнее стало, что происходит. Можно и дальше соптимизировать: переносить в следующую итерацию старое значение функции, чтобы не считать его лишний раз. Не удержался, сделал сам. Это особенно полезно, если сама функция вычисляется неявным образом с помощью численной процедуры.

 Профиль  
                  
 
 Re: Метод дробления шага
Сообщение14.01.2015, 08:53 
Аватара пользователя


14/09/12
181
Уфа
Цитата:
Очень нерационально производятся вычисления

Я понимаю что гораздо лучше gradX(x, y) вычислить один раз (в каждом цикле) и занести данные в переменную, но я специально так написал, чтобы было наглядней как в формуле. Когда делал, я не гнался за оптимальностью, но с Вами полностью согласен.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group