Реферат
В работе реализуетсянахождение решения одной задачи на тему максимизации функций многих переменных.При этом рассматриваются методы дихотомии и покоординатного спуска.
Пояснительная записка ккурсовой работе состоит из двух основных частей: теоретической и практической.
В теоретической части рассматриваетсяпоиск максимума одной функции многих переменных методом покоординатного спускаи с помощью метода дихотомии.
Практическая частьсодержит разработку программного обеспечения для решения заданной задачи вышеуказанными методами, реализованную на языке С++.
Объем пояснительнойзаписки: 1
Количество рисунков: 3
Количество используемыхисточников: 3
СодержаниеВведение
1. Постановка задачи
2. Решение задачи с использованиемметода дихотомии
2.1 Описание метода дихотомии
2.2 Алгоритм решения
3. Решение задачи с использованиемметода покоординатного спуска
3.1 Описание метода покоординатногоспуска
3.2 Алгоритм решения
Заключение
Список используемой литературы
Приложение 1. Листинг программы№1
Приложение 2. Листинг программы №2
Приложение 3. Листинг программы №3
Приложение 4. Результаты работыпрограммы №1
Приложение 5. Результаты работыпрограммы №3
Введение
В работе рассмотреныспособы нахождения таких значений аргументов, при которых исходная функциямаксимальна, а вспомогательная (от которой зависит исходная) – минимальна. Впараграфе 2 изложено решение задачи с использованием метода дихотомии. Впараграфе 3 произведено исследование задачи методом покоординатного спуска.
1.Постановка задачи
Исходная функция имеетвид:
/>, где:
xi/>R –– параметры исходной функции;
p, q/>R –– некоторые параметры удовлетворяющие условию 1q
с=c(x1…xn) ––вспомогательная функция, записанная в неявном виде
/>→min.
Задача:
Найти xi*, />: f(x1*…xn*)=/>f(x1…xn).
Выполним следующуюзамену: xi=axi+b, />. При этомзначение функции не изменится:
/>
/>
Таким образом, исходнуюобласть определения функции можно сузить до xi/>R[0;1]. Так как знаменатель не должен бытьравным нулю, то xi≠xj/>i≠j. Но тогда все параметры можно расположить по возрастанию: x1/>x2/>…/>xi/>xi+1/>…/>xn, а выбором a и b можно привести x1=0, xn=1.
Далее будем рассматриватьзадачу от n-2 переменных, т.к. x1 и xnявляются константами.
2. Решениезадачи с использованием метода дихотомии
2.1 Описаниеметода дихотомии
Данный метод применяетсядля решения нелинейных уравнений. Если нелинейное уравнение достаточно сложное,то найти точно его корни удается весьма редко. Важное значение приобретаютспособы приближенного нахождения корней уравнения и оценка степени их точности.
Пусть f(x)=0 (1)
Где f(x)определена и непрерывна в некотором конечном ибесконечном интервале a. Требуется найти все или некоторые корни уравнения (1).Всякое значение />, обращающее функцию f(x)в нуль, называется корнем уравнения (1). Поставленнаязадача распадается на несколько этапов:
1. Отделениекорней, т.е. установление возможно более тесных промежутков [/>,/>], в которыхсодержится только по одному корню.
2. Нахождениеприближенных (грубых) значений корней.
3. Вычисление корнейс требуемой точностью.
Первая ивторая задача решаются аналитическими и графическими методами.
Отделениекорней
Еслиуравнение f(x)= 0 имеет только действительные корни, то полезносоставить таблицу значений функции f(x).Если в двух соседних точках /> и /> функцияимеет разные знаки, то между этими точками лежит по меньшей мере один корень.Корень будет заведомо единственным, если /> определенана отрезке [/>,/>]и сохраняетпостоянный знак.
Графическиеметоды
Действительныекорни уравнения f(x)= 0 приближенно можноопределить как абсциссы точек пересечения графика функции f(x)с осью x.
Приближенныезначения корней, найденные грубо, в дальнейшем уточняют с помощью какого-либоитерационного метода.
Методдихотомии
Дихотомияозначает деление пополам. Пусть нашли такие точки /> и />,что /> 0, т.е. на [/>,/>] лежит по меньшей мереодин корень. Найдем середину отрезка [/>,/>]. Получаем />. Если f(x2) = 0, то /> еслиf(/>)/>0, то из двух половинотрезка выберем ту, для которой выполняется условие /> 0, т.к. корень лежит на этой половине. Затем вновь делим выбранный отрезокпополам и выбираем ту половину, на концах которой функция имеет разные знаки.
Еслитребуется найти корень с точностью />, топродолжим деление пополам (если конечно функция в середине какого-либо отрезкане обращается в нуль), пока длина очередного отрезка не станет . Тогда серединапоследующего отрезка установит значение с требуемой точностью. Метод дихотомиипрост и очень надежен. Он сходится для любых непрерывных функций f(x), в том числе не дифференцируемых.
Методустойчив к ошибкам округления, но скорость сходимости невелика. К недостаткамметода следует отнести сходимость к неизвестно какому корню (если корни неотделены). Но указанный недостаток имеется у всех итерационных методов.Дихотомия применяется тогда, когда требуется высокая надежность счета, аскорость сходимости малосущественна. Метод иногда применяется для грубогонахождения корней с последующим уточнением по другому методу с большейскоростью сходимости.
Этотметод относится к двусторонним (или к двух шаговым) методам, т.к. длявычисления очередного приближения необходимо знать два предыдущих.
2.2 Алгоритмрешения
Для нахождения максимумафункции будем перебирать всевозможные переменные xi, />,с шагом необходимой длины.
Затем будем находитьзначение функции с(/>) методомдихотомии.
Для этого вычислимпроизводную функции />, зависящей от с,и приравняем ее к 0.
/>
/>
Найдем корень /> этого нелинейногоуравнения методом дихотомии.
Подставим конкретныйнабор /> и при нем найденное /> в исходную функцию, иполучим ее значение.
Перебирая все xi, найдем максимум функции.
Перебирая всевозможныепараметры p и q, получим некоторые наборы />(взависимости от p и q) на которых функция достигает максимума.
3. Решениезадачи с использованием метода покоординатного спуска
3.1 Описаниеметода покоординатного спуска
Изложим этотметод на примере функции трех переменных />.
Выберемнулевое приближение />. Фиксируемзначения двух координат />. Тогдафункция будет зависеть только от одной переменной />;обозначим ее через />. Найдем минимумфункции одной переменной /> иобозначим его через />. Мы сделали шагиз точки /> в точку /> по направлению,параллельному оси />; на этом шагезначение функции уменьшилось.
Затем изновой точки сделаем спуск по направлению, параллельному оси />, т. е. рассмотрим />, найдем ее минимум иобозначим его через />. Второй шагприводит нас в точку />. Из этой точкиделаем третий шаг – спуск параллельно оси /> инаходим минимум функции />.Приход в точку /> завершает циклспусков.
Будемповторять циклы. На каждом спуске функция не возрастает, и при этом значенияфункции ограничены снизу ее значением в минимуме />.Следовательно, итерации сходятся к некоторому пределу />. Будет ли здесь иметьместо равенство, т. е. сойдутся ли спуски к минимуму и как быстро?
Это зависитот функции и выбора нулевого приближения.
Метод спускапо координатам несложен и легко программируется на ЭВМ. Но сходится онмедленно. Поэтому его используют в качестве первой попытки при нахождении минимума.
3.2 Алгоритмрешения
Будем перебирать сс шагом какой-либо малой длины.
Зададим нулевоеприближение, например:
/>
Найдем частныепроизводные />.
/>
Пусть при каком-то j />
Тогда k-ое приближение считаем по формулам:
/>
Шаг t будем выбирать таким образом, чтобы
/> и />.
В результате, закончивпроцесс по критерию />/> />, где />-заданная точность мыпридем к набору/>, при которомфункция f максимальна.
Подставим найденный набор/> и соответствующее /> в функцию f1=/>иперебрав все с, выберем те />, прикоторых f1 минимальна.
Заключение
В ходе решенияпоставленной задачи рассмотрены случаи, когда n=4,5,6. Были найдены две основные области наборов />:
1) xi=0 или 1(количество 0 и 1 одинаково)
2) xi=0.5, />.
Причем участок 1>p /> –– из первой области, при q≈p /> –– из второй области, а при p→∞ область делилась междуними примерно пополам.
На участке p>2 появлялись области вида:
i xi=0;
i>n-k =>xi=1;
k-1xi=0.5.
На участке 22 существует область, в котороймаксимум достигается при /> вида:
xi=a => xn-i=1-a, 0
Списокиспользованных источников
1. Амосов А.А.,Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Высшаяшкола, 1994. 543с.
2. Березин И.С. иЖидков Н. П. Методы вычислений. т.1. М.: “Наука”, 1965. 633c.
3. Подбельский В.В.и Фомин С.С. Программирование на языке Си. М.: “Финансы и статистика”, 2000.599с.
Приложение1. Листинг программы №1
//вывод на экран областеймаксимума функции
#include«stdafx.h»
#include«KE2.h»
#include«math.h»
#include«KE2Doc.h»
#include«KE2View.h»
#ifdef _DEBUG
#define newDEBUG_NEW
#undefTHIS_FILE
static charTHIS_FILE[] = __FILE__;
#endif
IMPLEMENT_DYNCREATE(CKE2View,CView)
BEGIN_MESSAGE_MAP(CKE2View,CView)
//{{AFX_MSG_MAP(CKE2View)
//NOTE — the ClassWizard will add and remove mapping macros here.
//DO NOT EDIT what you see in these blocks of generated code!
//}}AFX_MSG_MAP
//Standard printing commands
ON_COMMAND(ID_FILE_PRINT,CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_DIRECT,CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_PREVIEW,CView::OnFilePrintPreview)
END_MESSAGE_MAP()
CKE2View::CKE2View()
{
}
CKE2View::~CKE2View()
{
}
BOOLCKE2View::PreCreateWindow(CREATESTRUCT& cs)
{
returnCView::PreCreateWindow(cs);
}
voidCKE2View::OnDraw(CDC* pDC)
{
CKE2Doc*pDoc = GetDocument();
ASSERT_VALID(pDoc);
drawPoint(pDC);
//TODO: add draw code for native data here
}
BOOLCKE2View::OnPreparePrinting(CPrintInfo* pInfo)
{
//default preparation
returnDoPreparePrinting(pInfo);
}
voidCKE2View::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
//TODO: add extra initialization before printing
}
voidCKE2View::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
//TODO: add cleanup after printing
}
#ifdef _DEBUG
voidCKE2View::AssertValid() const
{
CView::AssertValid();
}
voidCKE2View::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CKE2Doc*CKE2View::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CKE2Doc)));
return(CKE2Doc*)m_pDocument;
}
#endif//_DEBUG
int sgn(floata)
{
int sg;
if (a>0)sg=1;
if (a==0)sg=0;
if (a
return(sg);
}
#define n 6
voidCKE2View::drawPoint(CDC *pDC)
{
double**c,*f1,*f,*x,*w,*e,max,p=2,q=2,xx,yy;
inti=0,j=0,k,m,a,b,*l,bb=0;
c=newdouble*[10000];
for(i=0;i
{
c[i]=newdouble[3];
memset(c[i],0,sizeof(double)*3);
}
f=newdouble[10000];
e=newdouble[10000];
w=newdouble[10000];
f1=newdouble[10000];
x=newdouble[n];
l=newint[10000];
for(xx=0.5;xx
for(yy=xx;yy
{
p=1./(1.-xx);
q=1./(1.-yy);
memset(w,0,sizeof(double)*10000);
memset(e,0,sizeof(double)*10000);
memset(f1,0,sizeof(double)*10000);
memset(x,0,sizeof(double)*n);
x[n-1]=1;
j=0;
for(i=0;i
{j=0;
f1[i]=1;c[i][0]=0;c[i][1]=1;c[i][2]=0.5;
while(fabs(f1[i])>0.00000001)
{
f1[i]=0;
for(k=0;k
{f1[i]+=pow((fabs(x[k]-c[i][2])),(p-1))*sgn(x[k]-c[i][2]);}
if(f1[i]
{max=c[i][2];c[i][2]=c[i][2]-(fabs(c[i][2]-c[i][1])/2.0);c[i][1]=max;}
if(f1[i]>0.00000001)
{max=c[i][2];c[i][2]=c[i][2]+(fabs(c[i][2]-c[i][1])/2.0);c[i][1]=max;}
if(fabs(f1[i])
{c[i][0]=c[i][2];gotoB;}
}
B:
c[i][0]=c[i][2];
for(a=0;a
{
for(b=0;b
w[i]+=pow((fabs(x[a]-x[b])),q);
e[i]+=pow((fabs(x[a]-c[i][0])),p);
}
f[i]=pow((e[i]/n),(1./p))/pow((w[i]/(n*n)),(1./q));
x[n-2]+=0.1;
for(k=2;k
{
if(x[n-k]>1.04)
{
x[n-k-1]+=0.1;
x[n-k]=x[n-k-1];
for(m=2;m
x[n-m]=x[n-k-1];
}
if (x[0]!=0)goto A;
}
}
A:
max=f[0];k=0;
for(m=0;m
{
if(fabs(max-f[m])
if(max
}
for(a=0;a
x[a]=0;
for(a=0;a
{
x[n-2]+=0.1;
for(k=2;k
if(x[n-k]>1.04)
{
x[n-k-1]+=0.1;
x[n-k]=x[n-k-1];
for(m=2;m
x[n-m]=x[n-k-1];
}
}
b=0;
for(k=0;k
{
if((x[k]==0)||(fabs(x[k]-1)
else
{
if(fabs(x[k]-0.5)
elseb=-n;
}
}
b-=n;
if (b
if (b==0)b=58;
if(b==bb)continue;
bb=b;
c=%f\n",p,q,l[0],l[k],k+1,max,c[l[0]][0]);
COLORREFcr(RGB((b%3)*127,(b%4)*85,(b%5)*63));
CBrush r(cr);
CPenrp(PS_SOLID,0,cr);
pDC->SelectObject(&rp);
pDC->SelectObject(&r);
CPointr1[3]={CPoint(0,360),CPoint(int(720./p),-int(720./q)+360),CPoint(int(720./p),360)};
pDC->Polygon(r1,3);
}
}
Приложение 2. Листингпрограммы №2.
//Покоординатный спуск
#include
#include
#include
#include
#include
#define n 4
void main()
{
//doubleff(double v,double vv);
intsgn(float a);
double*aa,**x,*f1,f,e,w,w1,e1,q=7,p=7,*r,*z,f2,*r1,max,m=0,c,f20,f21;
intbb,i,MAX,k,j,a,b,mm,ss;
x=newdouble*[n];
for(i=0;i
x[i]=newdouble[2];
z=newdouble[3];
aa=newdouble[n-2];
r=newdouble[n];
r1=newdouble[n];
//f2=newdouble[n];
f1=new double[n];
for(i=1;i
x[i][0]=0.1;//
x[n-1][0]=1;x[n-1][1]=1;x[0][1]=0;x[0][0]=0;x[1][0]=0.9;//x[2][0]=0;//x[3][0]=0;x[4][0]=1;//начальноеприближение
for(c=0.5;c
{
bb=0;
for(k=1;;k++)//Цикл по k
{
// for(i=0;i
// cerr
// cerr
w=0;e=0;w1=0;e1=0;
for(a=0;a
r[a]=0;
for(a=0;a
{
for(b=0;b
{
w+=pow((fabs(x[a][0]-x[b][0])),q);
r[a]+=pow((fabs(x[a][0]-x[b][0])),q-1)*sgn(x[a][0]-x[b][0]);
}
e+=pow((fabs(x[a][0]-c)),p);
}
w=pow(w/(n*n),1./q);//знаменательисх ф-ции
e=pow(e/n,1./p);//числительисх ф-ции
f=e/w;
//cerr
f1[0]=0;f1[n-1]=0;
MAX=0;
for(j=1;j
{
f1[j]=pow(n,(2./q-1./p))*(pow(e,(1./p-1))*pow(fabs(x[j][0]-c),(p-1))*w
*sgn(x[j][0]-c)-2.*pow(w,(1./q-1))*r[j])/(w*w);//производная исх. функции по x[j][0] в точке с координатами x[i][0] i=0..n-1на k-ом приближении
// cerr
for(a=0;a
if(aa[a]==j)break;
if(a!=bb)continue;
if(fabs(f1[j])>fabs(f1[MAX])) MAX=j;
}
//т.к. x[0]=0 и x[n-1]=1 — cosnt
mm=0;ss=0;
for(i=0;;i++)
{
if(mm==0) z[0]=100000000./pow(1.2,i);//шаг
if(mm==1)
{
z[0]=-1000000000./pow(1.2,ss);
ss++;
}
/*if(z[0]
{
z[0]=-0.5/pow(1.5,mm);
mm++;
}*/
for(a=0;a
r1[a]=0;
w1=0;e1=0;
for(a=0;a
{
if(a==MAX)
{
for(b=0;b
{
w1+=pow(fabs(x[a][0]+f1[a]*z[0]-(x[b][0]+f1[b]*z[0])),q);
r1[a]+=pow(fabs(x[a][0]+f1[a]*z[0] — (x[b][0]+f1[b]*z[0]) ),q-1)*
sgn(x[a][0]+f1[a]*z[0] — (f1[b]*z[0]+x[b][0]) );
}
e1+=pow((fabs(x[a][0]+f1[a]*z[0]-c)),p);
}
else
{
for(b=0;b
{
w1+=pow((fabs(x[a][0]-x[b][0])),q);
r1[a]+=pow((fabs(x[a][0]-x[b][0])),q-1)*sgn(x[a][0]-x[b][0]);
}
e1+=pow((fabs(x[a][0]-c)),p);
}
}
w1=pow(w1/(n*n),1/q);e1=pow(e1/n,1/p);
//printf("\nf=%f f[a]=%f",e/w,e1/w1);
a=0;
//for(j=1;j
//if (((x[j][0]+z[0]*f1[j])0))a++;
//if(a
if (((x[MAX][0]+z[0]*f1[MAX])0))a++;
if(a!=1)continue;
if(e1/w1>e/w) break;
if((e1/w1-e/w)>-0.00000001)
{
if(z[0]>0)
{
mm=1;
continue;
}
for(a=1;a
x[a][1]=x[a][0];
gotoA;
}
}
for(j=1;j
if(j==MAX)x[j][1]=x[j][0]+z[0]*f1[j];
else x[j][1]=x[j][0];
if(fabs(x[MAX][1]-x[MAX][0])
{
aa[bb]=MAX;
bb++;
}
if(bb==n-2)break;
for(j=1;j
x[j][0]=x[j][1];
} //закрытие цикла по k
A:
cerr
for(i=0;i
cerr
cerr
}// закрытиецикла по с
}
int sgn(floata)
{
intsg;
if(a>0) sg=1;
if(a==0) sg=0;
if(a
return(sg);
}
Приложение3. Листинг программы №3
#include
#include
#include
#include
#include
#include
#define n 4
intsgn(float);
main()
{
double**c,*f1,*f,*x,*w,*e,max,p=2,q=2,xx,yy;
inti=0,j=0,k,m,a,b,*l;
c=newdouble*[10000];
for(i=0;i
c[i]=newdouble[4];
f=newdouble[10000];
e=newdouble[10000];
w=newdouble[10000];
f1=newdouble[10000];
x=newdouble[n];
l=newint[10000];
for(xx=0.5;xx
for(yy=xx;yy
{
p=1./(1.-xx);
q=1./(1.-yy);
for(i=0;i
{
w[i]=0;
e[i]=0;
f1[i]=0;
}
for(i=0;i
for(j=0;j
{c[i][j]=0;
}
for(i=0;i
x[i]=0;
x[n-1]=1;
j=0;
for(i=0;i
{j=0;
f1[i]=1;c[i][0]=0;c[i][1]=1;c[i][2]=0.5;
while(fabs(f1[i])>0.000000001)
{
f1[i]=0;
for(k=0;k
{f1[i]+=pow((fabs(x[k]-c[i][2])),(p-1))*sgn(x[k]-c[i][2]);}
if(f1[i]
{max=c[i][2];c[i][2]=c[i][2]-(fabs(c[i][2]-c[i][1])/2.0);c[i][1]=max;}
if(f1[i]>0.000000001)
{max=c[i][2];c[i][2]=c[i][2]+(fabs(c[i][2]-c[i][1])/2.0);c[i][1]=max;}
if(fabs(f1[i])
{c[i][0]=c[i][2];gotoB;}
}
B:
c[i][0]=c[i][2];
for(a=0;a
{
for(b=0;b
w[i]+=pow((fabs(x[a]-x[b])),q);
e[i]+=pow((fabs(x[a]-c[i][0])),p);
}
f[i]=pow((e[i]/n),(1./p))/pow((w[i]/(n*n)),(1./q));
x[n-2]+=0.1;
for(k=2;k
{
if(x[n-k]>1.04)
{
x[n-k-1]+=0.1;
x[n-k]=x[n-k-1];
for(m=2;m
x[n-m]=x[n-k-1];
}
if (x[0]!=0)goto A;
}
}
A:
max=f[0];k=0;
for(m=0;m
{
if(fabs(max-f[m])
if(max
}
printf(«p=%fq=%f max=%f\n»,p,q,max);
x[n-1]=1;
for(a=0;a
x[a]=0;
for(a=0;a
{
x[n-2]+=0.1;
for(k=2;k
{
if(x[n-k]>1.04)
{
x[n-k-1]+=0.1;
x[n-k]=x[n-k-1];
for(m=2;m
x[n-m]=x[n-k-1];
}
}
}
for(a=0;a
printf(«Nabor:x[%d]=%f»,a,x[a]);
}
getch();
return 0;
}
int sgn(floata)
{
int sg;
if (a>0)sg=1;
if (a==0)sg=0;
if (a
return(sg);
}
Приложение№4 Результаты работы программы №1:
n=6
/>
/>
/>
/>
/>
n=5
/>
n=4
/>
Приложение№5. Результаты работы программы №3.
p=2.000000 q=2.000000 max=0.707107
Nabor:x[0]=0.000000 x[1]=0.600000 x[2]=0.700000 x[3]=1.000000
p=2.000000 q=2.100000max=0.696478
Nabor:x[0]=0.000000 x[1]=0.300000 x[2]=0.700000 x[3]=1.000000
p=2.000000 q=2.200000max=0.686567
Nabor:x[0]=0.000000 x[1]=0.300000 x[2]=0.700000 x[3]=1.000000
p=2.000000 q=2.300000max=0.677294
Nabor:x[0]=0.000000 x[1]=0.300000 x[2]=0.700000 x[3]=1.000000
p=2.000000 q=2.400000max=0.668738
Nabor:x[0]=0.000000 x[1]=0.200000 x[2]=0.800000 x[3]=1.000000
p=2.000000 q=2.500000max=0.660879
Nabor:x[0]=0.000000 x[1]=0.200000 x[2]=0.800000 x[3]=1.000000
p=2.000000 q=2.600000max=0.653565
Nabor:x[0]=0.000000 x[1]=0.200000 x[2]=0.800000 x[3]=1.000000
p=2.000000 q=2.700000max=0.646741
Nabor: x[0]=0.000000x[1]=0.200000 x[2]=0.800000 x[3]=1.000000
p=2.000000 q=2.800000max=0.640603
Nabor:x[0]=0.000000 x[1]=0.100000 x[2]=0.900000 x[3]=1.000000
p=2.000000 q=2.900000max=0.635019
Nabor:x[0]=0.000000 x[1]=0.100000 x[2]=0.900000 x[3]=1.000000