reforef.ru 1
Содержание



1 Задание 1

2 Блок-схемы 2


2.1 Блок-схема алгоритма пассивного оптимального метода. 2

2.2 Блок-схема алгоритма блочного метода 3

2.3 Блок-схема алгоритма метода дихотомии 4

2.4 Блок-схема алгоритма метода деления отрезков пополам. 5

2.5 Блок-схема алгоритма метода золотого сечения 6

2.6 Блок-схема алгоритма метода чисел Фибоначчи 7

2.7 Блок-схема алгоритма метода касательных 8

2.8 Блок-схема алгоритма метода парабол 9

3 Текст программы 10

4 Сравнение результатов 19



1 Задание


Вариант № 5: вычислить минимум функции на интервале [-2,0] с точностью 10-3.



Рисунок 1 – График функции на интервале [-2,0].

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

  1. пассивный оптимальный алгоритм;

  2. алгоритм блочного равномерного поиска;

  3. алгоритм деления интервала пополам;

  4. метод дихотомии;

  5. метод золотого сечения;

  6. метод Фибоначчи;

  7. метод касательных;

  8. метод парабол.


2 Блок-схемы

2.1 Блок-схема алгоритма пассивного оптимального метода.


2.2 Блок-схема алгоритма блочного метода


2.3 Блок-схема алгоритма метода дихотомии




2.4 Блок-схема алгоритма метода деления отрезков пополам.




2.5 Блок-схема алгоритма метода золотого сечения




2.6 Блок-схема алгоритма метода чисел Фибоначчи



2.7 Блок-схема алгоритма метода касательных




2.8 Блок-схема алгоритма метода парабол



3 Текст программы


#include

#include

#pragma hdrstop
#include "Unit1.h"

#include "Unit2.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

double A=-2,B=0;

double E=0.001;

double f(double x)

{

return x*x + 8*exp(0.55*x);

}

double p(double x)

{

return 2*x+4.4*exp(0.55*x);

}

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{
}

//---------------------------------------------------------------------------


void __fastcall TForm1::FormCreate(TObject *Sender)

{

Tab->Cells[0][0]="N";

Tab->Cells[1][0]="x*";


Tab->Cells[2][0]="y*";

}
//---------------------------------------------------------------------------

void __fastcall TForm1::Edit1Change(TObject *Sender)

{
try {

A=StrToFloat(Edit1->Text);

}

catch(Exception &exception){

Edit1->Text=FloatToStr(A);

}
}

//---------------------------------------------------------------------------

void __fastcall TForm1::Edit2Change(TObject *Sender)

{

try {

B=StrToFloat(Edit2->Text);

}

catch(Exception &exception){

Edit2->Text=FloatToStr(B);

};

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Edit3Change(TObject *Sender)

{

try {

E=StrToFloat(Edit3->Text);

}

catch(Exception &exception){

Edit3->Text=FloatToStr(E);

};

}

//----------------------------Блочный метод---------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

double a=A,b=B;

int n,N=0;

n=StrToFloat(Edit4->Text);

if (n<2)

{ Application->MessageBox("Задано недопустимое число n",

"Ошибка", MB_OK | MB_ICONWARNING);

}

else

{

double *x,*y;

x=new double[n+2];

y=new double[n+2];

double yl;

int l;

if(n%2==0)

{

int k=n/2;

double d=E/100;

do{

for (int j=1;j<=k;j++)

{

x[2*j] = a+j*((b-a)/(k+1));

x[2*j-1]=x[2*j]-d;

}

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

{

y[i]=f(x[i]);


}

N=N+n;

x[0]=a;

x[n+1]=b;

yl=y[1];

l=1;

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

if(y[i]
{

yl=y[i];

l=i;

}

a=x[l-1];

b=x[l+1];

}while(b-a>2*E);

double x0=(b+a)/2;

double y0=f(x0);

Tab->Cells[0][1]=FloatToStr(N);

Tab->Cells[1][1]=FloatToStr(x0);

Tab->Cells[2][1]=FloatToStr(y0);

}

else

{

int k=(n+1)/2;

x[k]=(a+b)/2;

y[k]=f(x[k]);

N=1;

do{

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

if(i!=k)

{

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

y[i] = f(x[i]);

}
N=N+n-1;

x[0]=a;

x[n+1]=b;

yl=y[1];

l=1;

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

if(y[i]
{

yl=y[i];

l=i;

}

a=x[l-1];

b=x[l+1];

x[k]=x[l];

y[k]=y[l];

}while(b-a>2*E);

double x0=x[l];

double y0=y[l];

Tab->Cells[0][1]=FloatToStr(N);

Tab->Cells[1][1]=FloatToStr(x0);

Tab->Cells[2][1]=FloatToStr(y0);

}

delete[]x;

delete[]y;

}

}

void __fastcall TForm1::Button3Click(TObject *Sender)

{

Close();

}

//-----------------------Чисел Фибоначчи----------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)

{

double a=A,b=B,d=E/100;

int Fn=(b-a)/(2*E), F1=1, F2=1, N=2,i=0;

while( (F1+F2) < Fn )

{

F1=F1+F2;

F2=F1+F2;

N+=2;

}

Fn=F1+F2;

double x1,x2,y1,y2;

x1=a+((b-a)/Fn)*F1; y1=f(x1);

x2=a+((b-a)/Fn)*F2; y2=f(x2);

i=2;

do{

if (y1
{

b=x2;x2=x1;y2=y1;

x1=a+b-x2;

y1=f(x1);

i++;

}else

{

a=x1;x1=x2;y1=y2;

x2=a+b-x1;

y2=f(x2);

i++;

}

}while(i
if(y1
{

b=x2;x2=x1;y2=y1;

}else a=x1;

x1=x2-d;

y1=f(x1);

if(y1 double x0=(a+b)/2,y0=f(x0);

Tab->Cells[0][2]=FloatToStr(N);

Tab->Cells[1][2]=FloatToStr(x0);

Tab->Cells[2][2]=FloatToStr(y0);

}

//-----------метод золотого сечения----------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)

{

double t;

t=(1+sqrt(5.0))/2;

double x1,x2,y1,y2;

double a=A,b=B;

x1=a+(b-a)/(t*t); y1=f(x1);

x2=a+(b-a)/t; y2=f(x2);

int N=2;

do{

if(y1
{

b=x2;

x2=x1;

y2=y1;

x1=a+b-x2;

y1=f(x1);

N++;

}

else

{

a=x1;

x1=x2;

y1=y2;

x2=a+b-x1;

y2=f(x2);

N++;

}

}while((b-a)/t>2*E);

double x0,y0;

if (y1
x0=(a+b)/2;

y0=f(x0);

Tab->Cells[0][3]=FloatToStr(N);

Tab->Cells[1][3]=FloatToStr(x0);

Tab->Cells[2][3]=FloatToStr(y0);
}

//----------------метод касательных-------------------------------------------

void __fastcall TForm1::Button5Click(TObject *Sender)


{
double a=A, b=B, N=4;

double y1=f(a), y2=f(b), z1=p(a), z2=p(b);

double s,y,z;

if(z1<0 && z2>0)

{

do{

s=((z2*b-z1*a)-(y2-y1))/(z2-z1);

y=f(s);

z=p(s);

N=N+2;

if(z==0){

Tab->Cells[0][4]=FloatToStr(N);

Tab->Cells[1][4]=FloatToStr(s);

Tab->Cells[2][4]=FloatToStr(y);

return;

}else

{

if(z>0){

b=s;

y2=y;

z2=z;

}else

{

a=s;

y1=y;

z1=z;

}

}

}while(b-a>2*E);

Tab->Cells[0][4]=FloatToStr(N);

double x0=(a+b)/2;

Tab->Cells[1][4]=FloatToStr(x0);

Tab->Cells[2][4]=FloatToStr(f(x0));

}else {

Tab->Cells[0][4]="Этот метод не подходит";

Tab->Cells[1][4]="";

Tab->Cells[2][4]="";

}

}

//--------------метод парабол-----------------------------------------
void __fastcall TForm1::Button6Click(TObject *Sender)

{

double a=A,b=B,c,ya,yb,yc,yt,t;

int N=0;

c=StrToFloat(Edit5->Text);

ya=f(a);

yb=f(b);

yc=f(c);

if(!((c>a)&&(c
{

Application->MessageBox("Задано недопустимое число с",

"Ошибка", MB_OK | MB_ICONWARNING);

}

N=3;

double S;

do{
S=c+0.5*((b-c)*(b-c)*(ya-yc)-(c-a)*(c-a)*(yb-yc))/((b-c)*(ya-yc)+(c-a)*(yb-yc));
if (S!=c)t=S; else t=(a+c)/2;

yt=f(t);N++;

if(t
{

if(yt
{

b=c;

yb=yc;

c=t;

yc=yt;

}else

{

if(yt>yc)


{

a=t;

ya=yt;

}else

{

a=t;

ya=yt;

b=c;

yb=yc;

c=(a+b)/2;

yc=f(c);

N++;

}

}

}else//t>c

{

if(yt
{

a=c;

ya=yc;

c=t;

yc=yt;

}else

{

if(yt>yc)

{

b=t;

yb=yt;

}else

{

a=c;

ya=yc;

b=t;

yb=yt;

c=(t+c)/2;

yc=f(c);

N++;

}

}

}

}while(b-a>E);

double x0=t, y0=yt;

N++;

Tab->Cells[0][5]=FloatToStr(N);

Tab->Cells[1][5]=FloatToStr(x0);

Tab->Cells[2][5]=FloatToStr(y0);

}

//-----------------метод деления интервала пополам----------------------
void __fastcall TForm1::Button7Click(TObject *Sender)

{

double a=A, b=B, N=0;

double x[5],y[5],yl;

int l;

x[2]=(a+b)/2;

y[2]=f(x[2]);

N++;

do{

x[0]=a;

x[4]=b;

x[1]=(a+x[2])/2;

y[1]=f(x[1]);

x[3]=(b+x[2])/2;

y[3]=f(x[3]);

N=N+2;

yl=y[1];

l=1;

for(int i=2;i<=3;i++)

if(yl>y[i]){

yl=y[i];

l=i;

}

a=x[l-1];

b=x[l+1];

x[2]=x[l];

y[2]=y[l];

}while(b-a>2*E);

Tab->Cells[0][6]=FloatToStr(N);

Tab->Cells[1][6]=FloatToStr(x[2]);

Tab->Cells[2][6]=FloatToStr(y[2]);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button8Click(TObject *Sender)


{

Form2->Show();

}

//-------метод дихотомии--------------------------------------
void __fastcall TForm1::Button9Click(TObject *Sender)

{

double a=A, b=B, d=E/100, N=0;

double x, y1, y2;

do{

x=(a+b)/2;

y1=f(x-d);

y2=f(x+d);

if(y1
else{

if(y1>y2){a=x-d;}

else{

a=x-d;

b=x+d;

}

}

N=N+2;

}while(b-a>2*E);

x=(a+b)/2;

y1=f(x);

Tab->Cells[0][7]=FloatToStr(N);

Tab->Cells[1][7]=FloatToStr(x);

Tab->Cells[2][7]=FloatToStr(y1);

}

//--------------Пассивный метод----------------------
void __fastcall TForm1::Button10Click(TObject *Sender)

{

double a=A,b=B;

int N1,N2;

double x,y, miny, minx;

N1=((b-a)/E)-1;

int N=N1;

if (N%2==0) N1=N+1;else N1=N+2;

N2=((b-a)/E)-2;

N=N2;

if (N%2==0) N2=N+2; else N2=N+1;

if(N1
{

x=a+(b-a)/(N1+1);

minx=x;

miny=f(x);

for(int i=2;i<=N1;i++)

{

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

y=f(x);

if(y
{

miny=y;

minx=x;

}

}

Tab->Cells[0][1]=FloatToStr(N1);

Tab->Cells[1][1]=FloatToStr(minx);

Tab->Cells[2][1]=FloatToStr(miny);

}

else

{

double d=E/10;

int k=N2/2;

x=a+((b-a)/(k+1));

minx=x;

miny=f(x);

x=x-d;

y=f(x);

if(y
{

miny=y;

minx=x;

}

for(int i=2;i<=k;i++)


{

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

y=f(x);

if(y
{

miny=y;

minx=x;

}

x=x-d;

y=f(x);

if(y
{

miny=y;

minx=x;

}

}

Tab->Cells[0][8]=FloatToStr(N2);

Tab->Cells[1][8]=FloatToStr(minx);

Tab->Cells[2][8]=FloatToStr(miny);

}

}

4 Сравнение результатов





Рисунок 2 – результаты реализации алгоритмов
Вывод:

В ходе лабораторной работы была сделана программная реализация алгоритмов одномерной оптимизации.

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