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

Размещено на http://www.allbest.ru

Министерство образования и науки Российской Федерации

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО

Кафедра дискретной математики и информационных технологий

РЕФЕРАТ

На тему: «Методы оптимизации»

Студента 2 курса, 221гр.

дневного отделения факультета КНиИТ

Барышева Андрея Вячеславовича

Преподаватель: Тананко И. Е.

Саратов, 2013



Задание

Дана функция f(x) = x3 - 3*sin(x), необходимо определить минимум данной функции на отрезке [0, 1] методами перебора, поразрядного поиска, дихотомии, золотого сечения, парабол и найти нули функции методом Ньютона. Своё минимальное значение f(x) = -1.64213 функция принимает при x = 0.824132.

график функция парабола



1. Метод перебора

Реализация метода на C++

#include <iostream>

#include <math.h>

using namespace std;

double func(double x)

{

return pow(x, 3) - 3*sin(x);

}

int main()

{

double a=0, b=1;

double x, y;

int n;

cout << "n = ";

cin >> n;

y=func(a);

for (int i=1; i<=n; i++)

{

x=a+i*(b-a)/(n+1);

if(func(x)<y)

y=func(x);

}

cout << endl;

cout << "e = " << (b-a)/(n+1) << endl;

cout << "x = " << x << endl;

cout << "y = " << y << endl;

return 0;

}

При e=0.001 (n=1000) программа выводит x=0.999 y=-1.64213.

2. Метод поразрядного поиска

Реализация метода на C++

#include <iostream>

#include <math.h>

#include <stdlib.h>

using namespace std;

double func(double x)

{

return pow(x, 3) - 3*sin(x);

}

int main()

{

double a=0, b=1;

double x, y, sh, x0, x1, f0, f1, e;

cout << "e = ";

cin >> e;

sh=(b-a)/4;

x0=a;

f0=func(x0);

label:

x1=x0+sh;

f1=func(x1);

if(f0>=f1)

{

x0=x1;

f0=f1;

if(a<=x0 && x0<=b)

goto label;

}

if(fabs(sh)<=e)

{

x=x0;

y=func(x0);

}

else

{

x0=x1;

f0=f1;

sh=-sh/4;

goto label;

}

cout << endl;

cout << "x = " << x << endl;

cout << "y = " << y << endl;

return 0;

}

При e=0.001 программа выводит x=0.824219 y=-1.64213.

3. Метод дихотомии

Реализация метода на C++

#include <iostream>

#include <math.h>

using namespace std;

double func(double x)

{

return pow(x, 3) - 3*sin(x);

}

int main()

{

double a=0, b=1, s=0.0001;

double x1, x2, e, en, x, y;

cout << "e = ";

cin >> e;

do

{

x1=(b+a-s)/2;

x2=(b+a+s)/2;

if(func(x1)<=func(x2))

b=x2;

else

a=x1;

en=(b-a)/2;

}

while(en>e);

x=(a+b)/2;

y=func(x);

cout << endl;

cout << "x = " << x << endl;

cout << "y = " << y << endl;

return 0;

}

При e=0.001 программа выводит x=0.8236 y=-1.64213.

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

Реализация метода на C++

#include <iostream>

#include <math.h>

using namespace std;

double func(double x)

{

return pow(x, 3) - 3*sin(x);

}

int main()

{

double a=0, b=1;

double x1, x2, fx1, fx2, t, e, en, x, y;

cout << "e = ";

cin >> e;

x1=a+(3-sqrt(5))*(b-a)/2;

x2=a+(sqrt(5)-1)*(b-a)/2;

fx1=func(x1);

fx2=func(x2);

t=(sqrt(5)-1)/2;

en=(b-a)/2;

while(en>e)

{

if(fx1<=fx2)

{

b=x2;

x2=x1;

fx2=fx1;

x1=b-t*(b-a);

fx1=func(x1);

}

else

{

a=x1;

x1=x2;

fx1=fx2;

x2=b-t*(b-a);

fx2=func(x2);

}

en=t*en;

}

x=(a+b)/2;

y=func(x);

cout << endl;

cout << "x = " << x << endl;

cout << "y = " << y << endl;

return 0;

}

При e=0.001 программа выводит x=0.5 y=-1.31334.



5. Метод парабол

Реализация метода на C++

#include <iostream>

#include <math.h>

#include <stdlib.h>

using namespace std;

double func(double x)

{

return pow(x, 3) - 3*sin(x);

}

int main()

{

double a=0, b=1;

double x1, x2, x3, f1, f2, f3, a1, a2, x, fx, xp, e;

cout << "e = ";

cin >> e;

x1=a;

x2=(a+b)/2;

x3=b;

x=0;

f1=func(x1);

f2=func(x2);

f3=func(x3);

do

{

xp=x;

a1=(f2-f1)/(x2-x1);

a2=(1/(x3-x2))*( (f3-f1)/(x3-x1) - (f2-f1)/(x2-x1) );

x=0.5*(x1+x2-(a1/a2));

fx=func(x);

if(x1<x<x2<x3)

if(fx>=f2)

{

x1=x;

f1=func(x1);

}

else

{

x3=x2;

x2=x;

f2=func(x2);

f3=func(x3);

}

else if(x1<x2<x<x3)

if(fx>=f2)

{

x3=x;

f3=func(x3);

}

else

{

x1=x2;

x2=x;

f1=func(x1);

f2=func(x2);

}

}

while(abs(xp-x)>e);

cout << endl;

cout << "x = " << x << endl;

cout << "y = " << fx << endl;

return 0;

}

При e=0.001 программа выводит x=0.845785 y=-1.64044.

6. Метод Ньютона нахождения нулей функции

Реализация метода на C++

#include <iostream>

#include <math.h>

#include <stdlib.h>

using namespace std;

double func(double x)

{

return pow(x, 3) - 3*sin(x);

}

double dfunc(double x) //производная функции func()

{

return 3*pow(x, 2) - 3*cos(x);

}

int main()

{

double a=0, b=1;

double x, x0, e;

cout << "x0 = ";

cin >> x0; //начальное приближение

cout << "e = ";

cin >> e; //

x=x0;

while(abs(func(x))>e)

x=x-func(x)/dfunc(x);

cout << endl;

cout << "x = " << x << endl;

return 0;

}

При x=0.1 e=0.001 программа выводит x=0.1.

Размещено на www.allbest.