Основные методы поиска экстремума функции двух переменных и их реализация на языке программирования С++

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

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

1. Постановка задания

Дана функция двух переменных f(x,y) и начальное приближение = (. В курсовой работе должны быть реализованы следующие методы поиска экстремума:

Ш метод градиентного спуска;

Ш метод наискорейшего спуска;

Ш метод покоординатного спуска.

Требуется произвести сравнительное исследование перечисленных методов и представить результаты расчётов в виде линий уровня и градиентных кривых.

f(x,y) = 1, = (.

2. Аналитическое нахождение минимального значения функции через необходимое и достаточное условие экстремума

Перед тем, как использовать специальные методы нахождения минимального значения функции двух переменных, воспользуемся «классическим» методом отыскания его значения через необходимое и достаточное условие экстремума.

Найдём стационарные точки функции f(x,y) = 1

Из второго уравнения системы и, подставив данное значение в первое уравнение системы получаем, что , y = 1.

Теперь, проверим достаточное условие экстремума, составив матрицу вторых производных:

Подставляя точку (1,1) получаем матрицу:

Т.к. A = 802 > 0 и AC - = 400 > 0 следовательно, в рассматриваемой точке достигается минимальное значение функции f(1,1) = 0.

Линии уровня рассматриваемой функции имеют вид:

Рис. 1

3. Нахождение минимального значения функции методом градиентного спуска

Описание алгоритма на языке С++:

#include "stdafx.h"

#include <stdlib.h>

#include <iostream>

#include <math.h>

#include <conio.h>

#include <string>

#include <cstring>

#include <iomanip>

using namespace std;

void main(){

double dot[2], grad[2], min_shag, shag, koeff_shaga, x, y, z_ot_x_y_1, z_ot_x_y_2;

int iter, min_iter=65000000;

bool tochnost_dostignuta=false;

cout<<" x_final= y_final= koeff.shaga= norma grad.= iterations=\n\n";

//Опробуем сто значений коэффициента шага

for(koeff_shaga=0.01; koeff_shaga <= 1; koeff_shaga+=0.01){

dot[0]=-0.5;

dot[1]=0.5;

shag=0.1;

iter=0;

tochnost_dostignuta=false;

do{ //cout<<"x= "<<x<<" y= "<<y<<"\n";

x = dot[0];

y = dot[1];

//Получим значение функции от текущей точки

z_ot_x_y_1 = 100*powl((dot[1] - powl(dot[0],2)),2) +

powl((1-dot[0]),2);

grad[0] = -400*(dot[0]*dot[1] - powl(dot[0],3)) + 2*dot[0] - 2;

grad[1] = 200*(dot[1] - powl(dot[0],2));

dot[0] -= shag*grad[0];

dot[1] -= shag*grad[1];

//Получим значение функции при движении по антиградиенту

//с текущим значением коэффициента

z_ot_x_y_2 = 100*powl((dot[1] - powl(dot[0],2)),2)

+ powl((1 - dot[0]),2);

//Если значение функции во втором случае больше - значение текущей точки

//Изменение точки на следующую отменим, а шаг умножим на коэффициент

if (z_ot_x_y_2 >= z_ot_x_y_1){

dot[0] = x;

dot[1] = y;

shag *= koeff_shaga;

};

iter++;

if(sqrt(powl(grad[0],2) + powl(grad[1],2)) < 0.001){

tochnost_dostignuta = true;

}

}while(!tochnost_dostignuta);

cout<<setw(9)<<dot[0]<<setw(10)<<dot[1];

cout<<setw(11)<<koeff_shaga<<setw(25)<<sqrt(powl(grad[0],2) + powl(grad[1],2));

cout<<setw(18)<<iter<<"\n";

if (iter < min_iter){

min_iter = iter;

min_shag = koeff_shaga;

}

}

cout<<"\n Minimalnoe chislo iteracii "<<min_iter<<"\n Dostigaetsya pri koefficiente shaga, ravnom "<<min_shag<<"\n";

system("pause");

}

минимальный экстремум градиентный функция

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

Рис. 3

Из результатов видно, что наименьшее количество итераций (6510) достигается тогда, когда коэффициент , в формулах , , к которым мы прибегаем, если > , равен 0.95.

Немного изменив текущую программу, с целью изучения хода её работы при наилучшем значении коэффициента шага, получим следующее.

Рис. 4

График, построенный по полученным в результате работы программы точкам.

Рис. 5. Метод градиентного спуска

*пунктирной линией отмечены отрезки, в которых отсутствуют промежуточные точки. Т.е. программа совершила «прыжок» от одной крайней точки отрезка к другой.

4. Нахождение минимального значения функции методом наискорейшего спуска

Описание алгоритма на языке С++:

#include "stdafx.h"

#include <stdlib.h>

#include <iostream>

#include <math.h>

#include <conio.h>

#include <string>

#include <cstring>

#include <iomanip>

using namespace std;

void main(){

long double shag, dot[2]={-0.5,0.5}, grad[2], norma_grad, znacheniya_funkcii[1000], x, y, j;

int iter=0, i, min;

bool tochnost_dostignuta = false;

do{

i=0;

//Составим массив значений функции в точках, полученных

//варьированием коэффициента шага по антиградиенту от 0.001 до 1

for(shag = 0.001; shag <= 1; shag +=0.001){

x=dot[0];

y=dot[1];

grad[0] = -400*(x*y - powl(x,3)) + 2*x - 2;

grad[1] = 200*(y - powl(x,2));

x -= shag*grad[0];

y -= shag*grad[1];

znacheniya_funkcii[i] = 100*powl((y - powl(x,2)),2) + powl((1 - x),2);

i++;

}

//Вычислим, при каком именно шаге достигается минимальное значение функции

min = 0;

for (i=1;i<1000;i++){

if (znacheniya_funkcii[i] < znacheniya_funkcii[min]){

min = i;

};

}

j=0.001;

for(i=0;i<min;i++){

j+=0.001;

}

//Перейдём к новой точке, исходя из найденного, наилучшего значения шага

grad[0] = -400*(dot[0]*dot[1] - powl(dot[0],3)) + 2*dot[0] - 2;

grad[1] = 200*(dot[1] - powl(dot[0],2));

dot[0] -= j*grad[0];

dot[1] -= j*grad[1];

cout<<"\n x= "<<setw(10)<<dot[0]<<" y= "<<setw(10)<<dot[1]<<setw(11)<<"shag = "<<j;

//Проверим норму градиента в новой точке

norma_grad = sqrt(powl(grad[0],2) + powl(grad[1],2));

if( norma_grad < 0.001){

tochnost_dostignuta = true;

}

iter++;

}while(!tochnost_dostignuta);

cout<<"\n\n iterations = "<<iter<<"\n";

cout<<" norma gradienta = "<<norma_grad<<"\n";

system("pause");

}

Результаты работы программы:

Рис. 6

График, построенный по полученным в результате работы программы точкам

Рис. 7. Метод наискорейшего спуска

*пунктирной линией отмечены отрезки, в которых отсутствуют промежуточные точки. Т.е. программа совершила «прыжок» от одной крайней точки отрезка к другой.

5. Нахождение минимального значения функции методом покоординатного спуска

Описание алгоритма на языке С++:

#include "stdafx.h"

#include <stdlib.h>

#include <iostream>

#include <math.h>

#include <conio.h>

#include <string>

#include <cstring>

#include <iomanip>

using namespace std;

//Пояснение по логике работы программы:

//1) Возьмём производную по х от иходной функции. Получим 400*x3 + x*(2 - 200*y) - 2 = 0

//2) Возьмём вторую производную и получим 1200*x2 + 2 - 400*y = 0.

//Откуда x = +\- (1/3*y - 1/600)(1/2)

//Из свойства кубического уравнения: оно имеет 3 действ корня, в нашем случае,

//если (2 - 200*y)3 + 10800 < 0 <=> y > 0.12052094495

//И лишь один действительный корень, если (2 - 200*y)3 + 10800 > 0 <=> y < 0.12052094495

//Рассмотрим первый случай:

// a = (-1)*(1/3*y - 1/600)(1/2) и b = (1/3*y - 1/600)(1/2) - экстремумы второй производной

//В этом случае один ноль производной первого порядка будет в интервале (-inf, a), второй на (a,b), третий на (b, inf)

//Т.к. перед x3 положительный коэффициент - очевидно, что функция идёт от -inf к inf, три раза меняя свой знак

//Т.е. искомый нами минимум будет на интервале (b, inf)

//Во втором случае будет один ноль на интервале (-inf, inf)

//_____________________________________________________________________________

//В обоих случаях корни уравнения можно найти методом половинного деления

//Но, разумеется работать мы будем не с интервалом (-inf, inf), а с конечным интервалом, например (-10, 10)

//Функция, находящая значение х, при фиксированном у, такое что f(x,y) имеет минимальное значение

long double search_min(long double f){

long double y,g,a,b,c;

//Найдём минимум, в случае, когда экстремумов три

if (f > 0.12052094495){

a=sqrt(1/3*f - 1/600);

b=10;

do{

c=(a+b)/2;

y=400*pow(c,3) + c*(2 - 400*f) -2;

g=400*pow(a,3) + a*(2 - 400*f) -2;

if (y*g<0)

b=c;

else a=c;

}while (abs(a-b)>=0.000001);

return c;

}

//Найдём минимум в случае, когда экстремум один

if (f < 0.12052094495){

a=(-10);

b=10;

do{

c=(a+b)/2;

y=400*pow(c,3) + c*(2 - 400*f) -2;

g=400*pow(a,3) + a*(2 - 400*f) -2;

if (y*g<0)

b=c;

else a=c;

}while (abs(a-b)>=0.000001);

return c;

}

}

void main(){

long double x = -0.5, y = 0.5, grad[2], norma_grad;

int iterations=0;

bool tochnost_dostignuta = false;

do{

if (iterations%2 == 0){

x=search_min(y);

}

//Из условия задачи очевидно, что первая производная функции f(x,y) по у

//равна нулю только в том случае, когда у=х2

else y = powl(x,2);

cout<<"x = "<<x<<setw(12)<<"y = "<<y<<"\n";

grad[0] = -400*(x*y - powl(x,3)) + 2*x - 2;

grad[1] = 200*(y - powl(x,2));

iterations++;

norma_grad = sqrt(powl(grad[0],2) + powl(grad[1],2));

if(norma_grad < 0.001){

tochnost_dostignuta = true;

}

}while(!tochnost_dostignuta);

cout<<"\n"<<iterations<<"\n";

cout<<"norma gradienta = "<<norma_grad<<"\n";

system("pause");

}

Результаты работы программы:

Рис. 8

График, построенный по полученным в результате работы программы точкам.

Рис. 9. Метод покоординатного спуска

* пунктирной линией отмечены отрезки, в которых отсутствуют промежуточные точки. Т.е. программа совершила «прыжок» от одной крайней точки отрезка к другой.

6. Сравнительная таблица всех трёх методов

Табл. 1

Название метода	Количество итераций	Достигнутая точка	Норма градиента в достигнутой точке
Метод градиентного спуска	6510	(0.998884 , 0.997764)	0.000999287
Метод наискорейшего спуска	808	(1.00095 , 1.00193)	0.000966262
Метод покоординатного спуска	4045	(0.998897 , 0.99779)	0.000999632

Размещено на Allbest.ru

...