Методы оптимизации. Метод дихотомии и метод золотого сечения

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

Государственное образовательное учреждение

высшего профессионального  образования

«Ижевский государственный  технический университет

имени М. Т. Калашникова»

Кафедра «Управление  качеством»

 

 

 

 

 

Лабораторная  работа №1

По дисциплине: «ИТ в ПЗ»

По теме: «Методы  оптимизации.

Метод дихотомии  и метод золотого сечения»

 

 

 

 

 

 

Выполнил:                                                                        студентка группы 7-05-1

       Килина Н.Л.

Проверил:                                                                                          преподаватель

к.ф.-м.н. Северюхин А. В.

 

 

 

 

 

Ижевск, 2013

Содержание

Введение…………………………………………………………………………...3

Задание…………………………………………………………………………….5

1. Построение графика………………………………………………………..6
2. Разработка схемы алгоритма………………………………………………7
3. Вычислительный эксперимент…………………………………………….9

Заключение.………………………………………………………………………11

Список использованных источников…………………………………………...12

Приложение……………………………………………………………………..13

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Дихотомия – раздвоенность, последовательное деление на две части, не связанные между собой. Способ логического деления класса на подклассы, который состоит в том, что делимое понятие полностью делится на два взаимоисключающих понятия.

Метод дихотомии несколько схож с методом бисекции, однако отличается от него критерием отбрасывания концов.

Пусть задана функция .

Разобьём мысленно заданный отрезок  пополам и возьмём две симметричные относительно центра точки  и так, что:

где   – некоторое число в интервале .

Вычислим два значения функции  в двух новых точках. Сравнением определим, в какой из двух новых точек значение функции максимально. Отбросим тот из концов изначального отрезка, к которому точка с максимальным значением функции оказалась ближе (напомним, мы ищем минимум), то есть:

• Если , то берётся отрезок , а отрезок отбрасывается.
• Иначе берётся зеркальный относительно середины отрезок , а отбрасывается .

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

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

Метод золотого сечения – метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения.

Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:

Иллюстрация выбора промежуточных точек метода золотого сечения.

, где  – пропорция золотого сечения.

Таким образом:

То есть точка  делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.

 

 

Задание

Разработать программу  по вычислению функции методом дихотомии и методом золотого сечения. И в соответствии с программой построить график функции .

Программа разрабатывается  на языке С++.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Построение графика

В соответствие с разработанной программой был построен график функции и данный график показан на рисунке 1.

Рисунок 1 – График функции

 

 

 

 

 

 

 

 

2 Разработка схемы алгоритма

Схема алгоритма программы, по вычислению функции методом дихотомии и методом золотого сечения, представлена на рисунке  2.

 

 

 

 

Рисунок 2 – Схема алгоритма программы

по вычислению функции методом дихотомии и  методом золотого сечения

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2 – Схема алгоритма программы

по вычислению функции методом дихотомии и методом золотого сечения (Продолжение)

 

3 Вычислительный эксперимент

Вычислительный  эксперимент программы по вычислению функции методом дихотомии и методом золотого сечения показан на рисунке 3.

Рисунок 3 – Вычислительный эксперимент программы

по вычислению функции методом дихотомии и методом золотого сечения

 

 

 

 

 

 

 

 

 

Рисунок 3 – Вычислительный эксперимент программы по вычислению функции методом дихотомии и методом золотого сечения (Продолжение)

 

 

 

 

 

Заключение 

В ходе выполнения лабораторной работы научились разрабатывать на языке программирования С++ программу по вычислению функции методом дихотомии и методом золотого сечения. В соответствии с данной программой был построен график функции .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы и источников

1. Шилдт Г.: «С++ Руководство для начинающих»: Учебный курс. – СПб: Питер; К.: Издательский дом «Вильямс» группа BHV, 2005. – 669 с.
2. Аверкин В., Бобровский А., Веснич В., Радушинский В.: «Программирование на C++»: Учебное пособие для высших и средних учебных заведений. – Издательство Корона-Принт, 1999. – 256 с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение  А (обязательное)

Программа по вычислению функции методом дихотомии и  методом золотого сечения показана на рисунке А1.

#include "stdafx.h"

#include <iostream>

#include <math.h>

using namespace std;

int m=1;

double func(double x)

{

return 418,9829*m +((-x)*sin(sqrt(abs(x))));   

}

double Dihotomy()

{

double a = -500;

double b = 500;

double E = 0.0001;

int n=0;

while(((b-a)>E)&&n<=10)

{

double X_1 = (a+b)/2 - E;

double X_2 = (a+b)/2 + E;

double Y_1 = func(X_1);

double Y_2 = func(X_2);

if (n % 1 == 0)

{

cout << "_____________________________"<<endl;

cout << "n= " <<n<<endl;

cout<<"a= "<<a<<" b= "<<b<<endl;

cout<<"x= "<<X_1<<" x1= "<<X_1<<" x2= "<<X_2<<endl;

cout<<"y1= "<<Y_1<<" y2= "<<Y_2<<endl;

cout << "F(x) = " << func((a+b)/2) << endl;

}

 

if (Y_1>Y_2)

a = X_1;

else

b = X_2;

n++;

}

return func((b+a)/2);

}

 

 

 

 

 

 

 

 

Рисунок А.1 – Программа по вычислению функции методом дихотомии и методом золотого сечения

double Golden_Cross()

{

double a = -500;

double b = 500;

double E = 0.001;

double X_1 =b-(b-a)/1.618;

double X_2 = a + (b-a)/1.618;

double Y_1 = func(X_1);

double Y_2 = func(X_2);

int n=3;

while ((b-a)>E)

{

if (n>0)

{

cout<<"a= "<<a<<" b= "<<b<<endl;

cout<<"x1= "<<X_1<<" x2= "<<X_2<<endl;

cout<<"y1= "<<Y_1<<" y2= "<<Y_2<<endl;

}

if(Y_1<Y_2)

{

b=X_2;

X_2 = X_1;

X_1 = b-(b-a)/1.618;

Y_2=Y_1;

Y_1 = func(X_1);

}

else

{

a=X_1;

X_1 = X_2;

X_2 = a + (b-a)/1.618;

Y_1=Y_2;

Y_2 = func(X_2);

}

n--;

}

return func((b+a)/2);

}

void main()

{

 

cout<<"_________________________________"<<endl;

cout<<"M.D.:"<<endl;

cout<<"_________________________________"<<endl;

cout<<"R: "<<Dihotomy()<<endl;

cout<<"_________________________________"<<endl;

cout<<"M.Z.S.:"<<endl;

cout<<"_________________________________"<<endl;

cout<<"R: "<<Golden_Cross()<<endl;

cin.get();

return;

}

 

Рисунок А.1 – Программа по вычислению функции методом дихотомии и методом золотого сечения (Продолжение)