Методы оптимизации
Министерство
образования и науки Российской Федерации
САРАТОВСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ
Н.Г. ЧЕРНЫШЕВСКОГО
Кафедра
дискретной математики и информационных технологий
РЕФЕРАТ
На
тему: «Методы оптимизации»
Студента 2 курса,
221гр.
дневного отделения
факультета КНиИТ
Барышева Андрея
Вячеславовича
Преподаватель:
Тананко И. Е.
Саратов,
2013
Задание
Дана функция f(x) = x3 - 3*sin(x), необходимо
определить минимум данной функции на отрезке [0, 1] методами перебора,
поразрядного поиска, дихотомии, золотого сечения, парабол и найти нули функции
методом Ньютона. Своё минимальное значение f(x) = -1.64213 функция принимает
при x = 0.824132.
график функция парабола
. Метод перебора
Реализация метода на C++
#include <iostream>
#include <math.h>namespace
std;func(double x)
{pow(x, 3) - 3*sin(x);
}main()
{a=0, b=1;x, y;n;<< "n =
"; >> n;=func(a);(int i=1; i<=n; i++)
{=a+i*(b-a)/(n+1);(func(x)<y)=func(x);
}<< endl;<< "e =
" << (b-a)/(n+1) << endl;<< "x = " << x
<< endl;<< "y = " << y << endl;
0;
}
При e=0.001 (n=1000) программа выводит x=0.999
y=-1.64213.
. Метод поразрядного поиска
Реализация метода на C++
#include <iostream>
#include <math.h>
#include <stdlib.h>namespace
std;func(double x)
{pow(x, 3) - 3*sin(x);
}main()
{a=0, b=1;x, y, sh, x0, x1, f0, f1,
e;<< "e = "; >>
e;=(b-a)/4;=a;=func(x0);:=x0+sh;=func(x1);(f0>=f1)
{=x1;=f1;(a<=x0 &&
x0<=b)label;
}(fabs(sh)<=e)
{=x0;=func(x0);
}
{=x1;=f1;=-sh/4;label;
}<< endl;<< "x =
" << x << endl;<< "y = " << y <<
endl;0;
}
При e=0.001 программа выводит x=0.824219
y=-1.64213.
. Метод дихотомии
Реализация метода на C++
#include <iostream>
#include <math.h>namespace
std;func(double x)
{pow(x, 3) - 3*sin(x);
}main()
{a=0, b=1, s=0.0001;x1, x2, e, en,
x, y;<< "e = "; >> e;
{=(b+a-s)/2;=(b+a+s)/2;(func(x1)<=func(x2))=x2;=x1;=(b-a)/2;
}(en>e);=(a+b)/2;=func(x);
<< endl;<< "x =
" << x << endl;<< "y = " << y <<
endl;
0;
}
При e=0.001 программа выводит x=0.8236
y=-1.64213.
. Метод золотого сечения
Реализация метода на C++
#include <iostream>
#include <math.h>namespace
std;func(double x)
{pow(x, 3) - 3*sin(x);
}main()
{a=0, b=1;x1, x2, fx1, fx2, t, e,
en, x, y;<< "e = "; >> e;=a+(3-sqrt(5))*(b-a)/2;=a+(sqrt(5)-1)*(b-a)/2;=func(x1);=func(x2);=(sqrt(5)-1)/2;=(b-a)/2;(en>e)
{(fx1<=fx2)
{=x2;=x1;=fx1;=b-t*(b-a);=func(x1);
}
{=x1;=x2;=fx2;=b-t*(b-a);=func(x2);
}=t*en;
}=(a+b)/2;=func(x);<<
endl;<< "x = " << x << endl;<< "y =
" << y << endl;0;
}
При e=0.001 программа выводит x=0.5 y=-1.31334.
5. Метод парабол
#include <iostream>
#include <math.h>
#include <stdlib.h>namespace
std;func(double x)
{pow(x, 3) - 3*sin(x);
}main()
{a=0, b=1;x1, x2, x3, f1, f2, f3,
a1, a2, x, fx, xp, e;<< "e = "; >>
e;=a;=(a+b)/2;=b;=0;=func(x1);=func(x2);=func(x3);
{=x;=(f2-f1)/(x2-x1);=(1/(x3-x2))*(
(f3-f1)/(x3-x1) - (f2-f1)/(x2-x1)
);=0.5*(x1+x2-(a1/a2));=func(x);(x1<x<x2<x3)(fx>=f2)
{=x;=func(x1);
}
{=x2;=x;=func(x2);=func(x3);
}if(x1<x2<x<x3)(fx>=f2)
{=x;=func(x3);
}
{=x2;=x;=func(x1);=func(x2);
}
}(abs(xp-x)>e);<<
endl;<< "x = " << x << endl;<< "y =
" << fx << endl;0;
}
При e=0.001 программа выводит x=0.845785
y=-1.64044.
. Метод Ньютона нахождения нулей функции
Реализация метода на C++
#include <iostream>
#include <math.h>
#include <stdlib.h>namespace
std;func(double x)
{pow(x, 3) - 3*sin(x);
}dfunc(double x) //производная
функции
func()
{3*pow(x, 2) - 3*cos(x);
}main()
{a=0, b=1;x, x0, e;<< "x0
= ";
cin >> x0; //начальное приближение<<
"e = ";
cin >> e;
//=x0;(abs(func(x))>e)=x-func(x)/dfunc(x);<< endl;<< "x =
" << x << endl;
return 0;
}
При x=0.1 e=0.001 программа выводит x=0.1.