Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++] Поиск минимума функции методом Ньютона, Реализовать программу за деньги 
:(
    Опции темы
MrNull
Дата 21.12.2007, 01:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 21.12.2007
Где: +7 906 059-05-56

Репутация: нет
Всего: нет



Так и не смог понять, разрешается ли на этом форуме помощь за деньги или нет, модеры, не ругайте сильно.

Задание: Реализовать программу на C++ поиска минимума функции методом Ньютона. Программу написать наиболее просто, без использования ссылок, указателей и т.д., так будет легче в ней разобраться. Задание и описание метода прикладываю к сообщению.

Немного подробнее о функции штрафа:

Код


//вот так задаётся:
double Shtraf(double X[],int n,double alfa)
{
  double ogr1=X[0]+X[1]-5;
  double ogr2=-X[0]+2*X[1]-6;
  double ogr3=-X[1]-2;
  ogr1=Max(ogr1);
  ogr2=Max(ogr2);
  ogr3=Max(ogr3);

  return (alfa*(ogr1*ogr1+ogr2*ogr2+ogr3*ogr3));  //штрафная функция
}

// А потом просто прибавляется к самой функции:
 double f(double X[], int n, double alfa)

{
  double f=2.0*(X[0]-3)*(X[0]-3)+(X[1]-2)*(X[1]-2)+Shtraf(X,n,alfa);
  return f;
}


Код

//И работать должна вот так:

double Max(double z)
{
  double rez;
  if(z>0)
    rez=z;
  else
    rez=0;
  return rez;
}


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

Картинка функции с ограничениями:
user posted image

Срок исполнения: 23.12.2007

Оплата: от 1000 рублей и выше на твоё усмотрение

Это сообщение отредактировал(а) MrNull - 21.12.2007, 01:34

Присоединённый файл ( Кол-во скачиваний: 16 )
Присоединённый файл  task_and_method.rar 60,11 Kb
PM MAIL ICQ   Вверх
ST1
Дата 22.12.2007, 18:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 20.7.2005
Где: Уфа

Репутация: 1
Всего: 1



Возьмусь за задание. Дай свой ответ


Это сообщение отредактировал(а) ST1 - 22.12.2007, 18:07
PM MAIL WWW ICQ   Вверх
MrNull
Дата 22.12.2007, 18:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 21.12.2007
Где: +7 906 059-05-56

Репутация: нет
Всего: нет



спасибо! стучись мне в аську 269-743-146 или звони +7 906 059-05-56.

ответ: глобальный минимум в точке x=2, y=3, на картинке это хорошо видно. Условный минимум (с учётом ограничений) совпадает с глобальным.
PM MAIL ICQ   Вверх
MrNull
Дата 23.12.2007, 15:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 21.12.2007
Где: +7 906 059-05-56

Репутация: нет
Всего: нет



Делюсь с остальными:

Программа поиска безусловного минимума функции f(x1, x2) = 2 * (x1 - 3)^2 + (x2 - 2)^2
 
    Алгоритм расчета: методом Ньютона решается система 
            |F1(x1, x2) = df/dx1 = 0|    
    (1)        |                        |    
            |F2(x1, x2) = df/dx2 = 0|,
    состоящая из равенства нулю частных производных исходной функции
    (необходимое условие экстремума). 
 
    Алгоритм метода Ньютона:
        Шаг 1. Задается начальное приближение для x1, x2,...xn (в нашем случае n = 2)
        Шаг 2. Вычисляется невязка fvec (вектор правых частей системы (1))
               Проверяется сходимость (сумма модулей координат fvec меньше некоторого малого eps > 0)
               Если достигнута сходимость, цикл завершается. Иначе переход к следующему шагу.
        Шаг 3. Вычисляются элементы матрицы Якобиана системы (1):

                     |dF1(x1, x2)/dx1    dF1(x1, x2)/dx2|
               J  =  |                                   |
                     |dF2(x1, x2)/dx1    dF2(x1, x2)/dx2| 
            
        Шаг 4. Методом Гаусса решается система J * (dx) = - fvec, где dx = (dx1, dx2) - вектор смещений
        Шаг 5. Рассчитывается следующее приближение переменных:
               x1 = x1 + dx1,    x2 = x2 + dx2
        Шаг 6. Переход к следующей итерации (Шаг 1.) если не превышено максимальное число итераций

    Метод Гаусса решения линейных систем:
        Элементарными преобразованиями над строками  
        матрицы она приводится к верхнетреугольному виду (прямой ход метода Гаусса);
        полученная система с треугольной матрицей решается в явном виде 
        методом последовательного исключения неизвестных в порядке dxn,...,dx1
        (обратный ход метода Гаусса)

Код

int main()
{        
    const int n = 2;            //размерность вектора    
    double x[n];                //вектор координат исходного минимума
    const int ntrial = 10;        //максимально число шагов для метода Ньютона
    const double eps = 1.e-6;    //точность (см. Шаг 2)
    int iter;                    //номер итерационного шага в методе Ньютона
    int i, j, k;                //переменные циклов
    double tmp;                    //временная переменная
    double fvec[n];                //вектор для хранения частных производных (см. Шаг 2)
    double p[n];                //вектор для хранения вектора смещений (см. Шаг 4)
    double fjac[n][n];            //матрица Якобиана (см. Шаг 3)
    
    //Создаем файл для вывода результатов расчета (указать полный путь)
    const char *logname = "C:\\Log.txt";
    ofstream os(logname);
    if (!os) {
        cout << "Cannot create log file " << logname << "\n";
        return 0;
    }

//Для вывода на экран
#define stream cout
//Для вывода в файл
//#define stream os

    //Шаг 1
    //Можно задать любое начальное приближение
    x[0] = 123;
    x[1] = 321;

    //Итерационный процесс метода Ньютона
    for (iter = 1; iter <= ntrial; iter++) {
        stream << "\n========================== " << iter << " iteration";
        
        stream << "\n\nInfo: Current vector x:";
        for (i = 0; i < n; i++)
            stream << "\nx[" << i << "] = " << x[i];

        //Шаг 2  

        fvec[0] = 4 * (x[0] - 3);    //df/dx1 = 4 * (x1 - 3)
        fvec[1] = 2 * (x[1] - 2);    //df/dx2 = 2 * (x2 - 2)
                 
        tmp = 0.; 
        for (i = 0; i < n; i++) { 
            tmp += fabs(fvec[i]);
        }
        if (tmp <= eps) 
            break;
        
        //Шаг 3

        fjac[0][0] = 4;        //dF1(x1, x2)/dx1 = 4        
        fjac[0][1] = 0.;    //dF1(x1, x2)/dx1 = 0
        fjac[1][0] = 0.;    //dF1(x1, x2)/dx1 = 0    
        fjac[1][1] = 2.;    //dF1(x1, x2)/dx2 = 2

        stream << "\n\nInfo: Current Jacobean matrix at vector x:\n";
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                stream << fjac[i][j] << "\t";
            }            
            stream << "\n";
        }

        //Шаг 4

        //Правая часть линейной системы 
        for (i = 0; i < n; i++) 
            p[i] = - fvec[i]; 

        //Прямой ход метода Гаусса
        for (i = 0; i < n - 1; i++) {
            tmp = fjac[i][i];
            
            if (tmp == 0.) {
                stream << "Error: Zero element at main diagonal in Jacobean matrix\n";
                return 0;
            }
            
            // рабочий элемент корректен - обрабатываем все нижлежащие строки
            for (j = i + 1; j < n; j++) {
                p[j] -= p[i] / tmp;
                for (k = n - 1; k >= i; k--) {
                    fjac[j][k] -= fjac[i][k] * fjac[j][i] / tmp;
                }
            }            
        }

        //Нахождение вектора смещений (обратный ход метода Гаусса)
        for (i = n - 1; i >= 0; i--) {
            tmp = 0;
            for (j = i + 1; j < n; j++) {
                tmp += fjac[i][j] * p[j];
            }
            p[i] = (p[i] - tmp) / fjac[i][i];
        }
        
        //Шаг 5
        for (i = 0; i < n; i++) { 
            x[i] += p[i];
        }
        
        //Шаг 6
    }

    if (iter < ntrial) {
        stream << "\n\n========================== The minimum location\n";
        stream << "(" << x[0] << ", " << x[1] << ")\n";
        return 0;
    }    
    stream << "\nError: Maximum number of iterations exceed\n";
    return 0;
}

PM MAIL ICQ   Вверх
iceberglife177
Дата 2.6.2017, 17:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 2.5.2017

Репутация: нет
Всего: нет



Цитата(MrNull @ 23.12.2007,  15:42)
Делюсь с остальными:

Программа поиска безусловного минимума функции f(x1, x2) = 2 * (x1 - 3)^2 + (x2 - 2)^2
 
    Алгоритм расчета: методом Ньютона решается система 
            |F1(x1, x2) = df/dx1 = 0|    
    (1)        |                        |    
            |F2(x1, x2) = df/dx2 = 0|,
    состоящая из равенства нулю частных производных исходной функции
    (необходимое условие экстремума). 
 
    Алгоритм метода Ньютона:
        Шаг 1. Задается начальное приближение для x1, x2,...xn (в нашем случае n = 2)
        Шаг 2. Вычисляется невязка fvec (вектор правых частей системы (1))
               Проверяется сходимость (сумма модулей координат fvec меньше некоторого малого eps > 0)
               Если достигнута сходимость, цикл завершается. Иначе переход к следующему шагу.
        Шаг 3. Вычисляются элементы матрицы Якобиана системы (1):

                     |dF1(x1, x2)/dx1    dF1(x1, x2)/dx2|
               J  =  |                                   |
                     |dF2(x1, x2)/dx1    dF2(x1, x2)/dx2| 
            
        Шаг 4. Методом Гаусса решается система J * (dx) = - fvec, где dx = (dx1, dx2) - вектор смещений
        Шаг 5. Рассчитывается следующее приближение переменных:
               x1 = x1 + dx1,    x2 = x2 + dx2
        Шаг 6. Переход к следующей итерации (Шаг 1.) если не превышено максимальное число итераций

    Метод Гаусса решения линейных систем:
        Элементарными преобразованиями над строками  
        матрицы она приводится к верхнетреугольному виду (прямой ход метода Гаусса);
        полученная система с треугольной матрицей решается в явном виде 
        методом последовательного исключения неизвестных в порядке dxn,...,dx1
        (обратный ход метода Гаусса)

Код

int main()
{        
    const int n = 2;            //размерность вектора    
    double x[n];                //вектор координат исходного минимума
    const int ntrial = 10;        //максимально число шагов для метода Ньютона
    const double eps = 1.e-6;    //точность (см. Шаг 2)
    int iter;                    //номер итерационного шага в методе Ньютона
    int i, j, k;                //переменные циклов
    double tmp;                    //временная переменная
    double fvec[n];                //вектор для хранения частных производных (см. Шаг 2)
    double p[n];                //вектор для хранения вектора смещений (см. Шаг 4)
    double fjac[n][n];            //матрица Якобиана (см. Шаг 3)
    
    //Создаем файл для вывода результатов расчета (указать полный путь)
    const char *logname = "C:\\Log.txt";
    ofstream os(logname);
    if (!os) {
        cout << "Cannot create log file " << logname << "\n";
        return 0;
    }

//Для вывода на экран
#define stream cout
//Для вывода в файл
//#define stream os

    //Шаг 1
    //Можно задать любое начальное приближение
    x[0] = 123;
    x[1] = 321;

    //Итерационный процесс метода Ньютона
    for (iter = 1; iter <= ntrial; iter++) {
        stream << "\n========================== " << iter << " iteration";
        
        stream << "\n\nInfo: Current vector x:";
        for (i = 0; i < n; i++)
            stream << "\nx[" << i << "] = " << x[i];

        //Шаг 2  

        fvec[0] = 4 * (x[0] - 3);    //df/dx1 = 4 * (x1 - 3)
        fvec[1] = 2 * (x[1] - 2);    //df/dx2 = 2 * (x2 - 2)
                 
        tmp = 0.; 
        for (i = 0; i < n; i++) { 
            tmp += fabs(fvec[i]);
        }
        if (tmp <= eps) 
            break;
        
        //Шаг 3

        fjac[0][0] = 4;        //dF1(x1, x2)/dx1 = 4        
        fjac[0][1] = 0.;    //dF1(x1, x2)/dx1 = 0
        fjac[1][0] = 0.;    //dF1(x1, x2)/dx1 = 0    
        fjac[1][1] = 2.;    //dF1(x1, x2)/dx2 = 2

        stream << "\n\nInfo: Current Jacobean matrix at vector x:\n";
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                stream << fjac[i][j] << "\t";
            }            
            stream << "\n";
        }

        //Шаг 4

        //Правая часть линейной системы 
        for (i = 0; i < n; i++) 
            p[i] = - fvec[i]; 

        //Прямой ход метода Гаусса
        for (i = 0; i < n - 1; i++) {
            tmp = fjac[i][i];
            
            if (tmp == 0.) {
                stream << "Error: Zero element at main diagonal in Jacobean matrix\n";
                return 0;
            }
            
            // рабочий элемент корректен - обрабатываем все нижлежащие строки
            for (j = i + 1; j < n; j++) {
                p[j] -= p[i] / tmp;
                for (k = n - 1; k >= i; k--) {
                    fjac[j][k] -= fjac[i][k] * fjac[j][i] / tmp;
                }
            }            
        }

        //Нахождение вектора смещений (обратный ход метода Гаусса)
        for (i = n - 1; i >= 0; i--) {
            tmp = 0;
            for (j = i + 1; j < n; j++) {
                tmp += fjac[i][j] * p[j];
            }
            p[i] = (p[i] - tmp) / fjac[i][i];
        }
        
        //Шаг 5
        for (i = 0; i < n; i++) { 
            x[i] += p[i];
        }
        
        //Шаг 6
    }

    if (iter < ntrial) {
        stream << "\n\n========================== The minimum location\n";
        stream << "(" << x[0] << ", " << x[1] << ")\n";
        return 0;
    }    
    stream << "\nError: Maximum number of iterations exceed\n";
    return 0;
}

а функцию розенброка можно вашим методом считать?
PM MAIL   Вверх
Noubpoeno
Дата 10.12.2022, 05:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 32
Регистрация: 9.12.2022

Репутация: нет
Всего: нет




Модератор: Сообщение скрыто.

PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »


 




[ Время генерации скрипта: 0.1414 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.