takya.ru страница 1
скачать файл
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение


высшего профессионального образования

Национальный исследовательский Томский политехнический университет

Институт кибернетики
Направление 230100 «Информатика и вычислительная техника»
Кафедра Информатики и проектирования систем

Методы оптимизации

Лабораторная работа № 2

одномерная оптимизация 1

Выполнил:

студент группы 8В81 Е.А. Мыцко

Руководитель:

Доцент каф. ИПС В.И. Рейзлин
2011

Задание

Найти точку минимума x* функции f(x) на отрезке [a,b] с точностью Ε=10-5 и минимальное значение f(x*).

Подсчитать число итераций и число вычислений функции f(x).

Применить методы:

1. Общего поиска;

2. Деления пополам;

3. Золотого сечения;

f(x)=10x·lnx-x2/2, [0.2;2.2].

Сравнить результаты.

Описание методов сужения интервала неопределенности

Общий поиск

В этом методе интервал [a, b] делится на несколько равных частей с последующим вычислением значений функции в узлах полученной сетки. В качестве минимума принимается абсцисса с минимальным вычисленным значением функции.



В результате интервал неопределенности сужается до двух шагов сетки.



Деление интервала пополам

Разделим интервал [a, b] на две равные части, а затем каждую из частей еще на две равные части.



Это первый этап поиска минимума. На нем после пяти вычислений функции (два - на краях и три - внутри интервала [a, b]) интервал неопределенности сужается вдвое, то есть на этом этапе α =0,5. Новый интервал неопределенности [x4,x5] снова разделим пополам, а затем каждую половину снова пополам. Теперь значения функции по краям и в его середине уже известны. Поэтому для завершения поиска на этом этапе требуется вычислить только два значения функции, после чего интервал неопределенности снова уменьшится вдвое.



Золотое сечение

Деление интервала на неравные части позволяет найти еще более эффективный метод. Вычислим функцию на концах отрезка [a, b] и положим a=x1, b=x2. Вычислим также функцию в двух внутренних точках x3, x4. Сравним все четыре значения функции и выберем среди них наименьшее. Пусть, например, наименьшим оказалось f(x3). Очевидно, минимум находиться в одном из прилегающих к нему отрезков. Поэтому отрезок [x4,b] можно отбросить и оставить отрезок [a,x4].



Первый шаг сделан. На отрезке [a,x4] снова надо выбрать две внутренние точки, вычислив в них и на концах значения функции и сделать следующий шаг. Но на предыдущем шаге вычислений мы уже нашли функцию на концах нового отрезка [a,x4] и в одной его внутренней точке x4. Потому достаточно выбрать внутри [a,x4] еще одну точку x5 определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса. Как выгодно размещать точки? Каждый раз оставшийся отрезок делиться на три части и затем отбрасывается один из крайних отрезков.



Листинг программы

#include

#include

#include


double Fmin = 0;

double xmin = 0;

int fCount = 0;

int iCount = 0;


double f(double x)

{

fCount++;



return 10*x*log(x)-(x*x)/2;

}
double Search(double e,double a,double b)

{

double h = e/2,Fn;



fCount = 0;

iCount = 0;

Fmin = f(a);

xmin = a;


for ( double x = a+h; x < b+h/2; x+=h)

{


Fn = f(x);

if (Fn < Fmin )

{

Fmin = Fn;



xmin = x;

}

}



iCount++;

return xmin;


}
double Bisection(double e,double a,double b)

{

double h = 0;



fCount = 0;

iCount = 0;


xmin = (b+a)/2;

h = (b-a)/4;


double xh1 = a + h,

xh2 = b - h,

Fh1 = f(xh1),

Fh2 = f(xh2);


Fmin = 0;
while( (b - a) > e)

{


iCount++;

if( Fh1 < Fmin)

{

b = xmin;



xmin = xh1;

Fmin = Fh1;

}

else


{

if( Fh2 < Fmin)

{

a = xmin;



xmin = xh2;

Fmin = Fh2;

}

else


{

a = xh1;

b = xh2;

}

}



h = (b-a)/4;

xh1 = a + h;

xh2 = b - h;

Fh1 = f(xh1);

Fh2 = f(xh2);
}

return xmin;


}

double GoldRatio(double e,double a,double b)



{

double h;

fCount = 0;

iCount = 0;


double fi =(sqrt(5)+1)/2;

h = (b-a)/fi;

double xh1 = a + h,

xh2 = b - h,

Fh1 = f(xh1),

Fh2 = f(xh2);


while ((b - a) > e)

{

iCount++;



if (Fh2 < Fh1)

{

Fmin = Fh2;



xmin = xh2;

b = xh1;

h = (b-a)/fi;

xh1 = xh2;

xh2 = b - h;

Fh1 = Fh2;

Fh2 = f(xh2);
}

else


{

xmin = xh1;

a = xh2;

xh2 = xh1;

h = (b-a)/fi;

xh1 = a + h;

Fmin = Fh1;

Fh2 = Fh1;

Fh1 = f(xh1);

}
}

return xmin;
}

int main()

{

double e,a,b;



double yS,yB,yG,xS,xB,xG;

cout<<"enter interval\n";

cin>>a;

cin>>b;
cout<<"enter e:\n";



cin>>e;
cout<<"Method "<<" Calculations "<<" Iterations "<<" Xmin "<<" F(Xmin) "<<"\n";
xS = Search(e,a,b); yS = Fmin;

cout<<"Search "<
xB = Bisection(e,a,b); yB = Fmin;

cout<<"Bisection "<
xG = GoldRatio(e,a,b); yG = Fmin;

cout<<"GoldRatio "<
cout<<"\n";

return 0;

}

Результаты

Рис. 1 Результаты работы программы



Вывод

В данной лабораторной работе была найдена точка минимума для заданной функции с помощью различных методов.



Метод общего поиска является самым простым, однако требует большого количества вычислений функции (более 400000). Метод деления пополам требует намного меньше вычислений функции (38) засчёт того, что интервал неопределённости сужается вдвое. Метод золотого сечения является самым эффективным и находит точку минимума функции, вычислив значение функции 28 раз. Это обусловлено делением интервала неопределённости на неравные части и отбросом «лишних» частей, гарантированно не имеющих точек минимума.
скачать файл



Смотрите также:
Лабораторная работа №2 одномерная оптимизация 1 студент группы 8В81 Е. А. Мыцко
52.49kb.
Лабораторная работа 9-10. Файловые системы. Управление дисками. Использование групповой политики
332.66kb.
Лабораторная работа №1 «Вычисление значений функций» студент 304 гр д/о Иванов Иван Иванович
23kb.
Лабораторная работа №8 по дисциплине «Физика-1» выполнена по методике Козырева А. В. «Общая Физика» студент фдо тусур
102.29kb.
Практическая работа №1 Тема: Плотности оптических полей Вариант №24 студент IV курса 2 группы
44.92kb.
Лабораторная работа № Конструирование таблиц 3 лабораторная работа № Конструирование запросов на выборку 18
904.24kb.
Курсовая работа по дисциплине «автомобильные дороги» Студент группы 4/241 Проверил Торосян Л. Е
45.32kb.
Курсовая работа по Теории государства и права Тема: Система права студент 3 курса,305 группы
197.06kb.
Творческая работа на тему: студент 44 группы физико-математического фа культета Гайсин Шамиль Т. Проверил: д п. н., профессор Тагариев Р. З
245.49kb.
Курсовая Работа Тема: Электрон в слое. Руководитель работы: Климин С. Н. Работу
123.88kb.
Студент группы с-11: Спирин Е. А
47.02kb.
Лабораторная работа №3 (это пример выполнения лаб работы, индивидуальное задание находится в пункте 4) Тема лабораторной работы: Исследование алгоритма нечеткой кластеризации
95.48kb.