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

Отчет по расчетной работе №1

Постановка задачи

Цель работы заключается в выборе более эффективного метода поиска экстремума для функции

на отрезке c точностью е=0,02. Для этого нужно проверить унимодальность функции аналитическим методом и по графику. Найти промежуток , на котором функция унимодальна и построить графики первой и второй ее производных. Далее с помощью метода перебора, поразрядного поиска, дихотомии и золотого сечения найти точку минимума и сравнить методы по количеству обращений к функции и по их точности.

Х о д р а б о т ы :

1. Проверка унимодальности аналитическим методом и по графику.

Построим график первой производной :



Построим график второй производной.

Достаточное условие унимодальности функции (у" > 0) выполнено на отрезке

За отрезок унимодальности можно выбрать [ 0; 0,3 ].

Проверим графически, построив график функции.

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

2. Точный метод поиска экстремума.

; [ 0; 0,3 ].

.

Числитель > 0, знаменатель на ООФ - тоже, значит у < 0 на всей ООФ. Значит функция убывает на [ 0; 0,3 ] и

= 0.50413.

3. Целевая функция унимодальна на [0; 0,3], т.е. на данном отрезке она имеет только один минимум, нет локальных максимумов и точек перегиба. Погрешность приближенного решения задачи определяется разницей между оптимальным значением проектного параметра * и принятым приближением к нему n . Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимого значения (точности) .

a) Метод перебора.

Алгоритм :

1) Разбить отрезок [a,b] на n равных частей точками

2) Вычислить значения f(xi) в точках xi и найти

Погрешность определения точки минимума xm функции f(x) методом

перебора не превосходит величины

.

Блок-схема.

n = (b - a) / e;

h = (b - a) / n;

x = a;

function(x, f);

c = f;

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

x = x + h;

function(x, f);

if (c > f) { x1 = x;

c = f; }

}

f = c;

x = x1;

Вывод: а = 0, b = 0,3, = 0.02

Локальный минимум: 0.3;

Наименьшее значение функции: 0,5041

Количество итераций: 15

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

Алгоритм :

1) Выбрать начальный шаг

Положить х0=а, вычислить f(x0)

2) Положить x1=x0+a Вычислить f(x1)

3) Сравнить значения f(x1) и f(x0) . Если f(x1) > f(x0), то перейти к шагу 4,

иначе - к шагу 5.

3) Положить

х0=x1, f(x0) = f(x1).

Проверить условие . Если ,

то перейти к шагу 2, иначе- к шагу 5.

4) Проверка на окончание поиска: если , то вычисления завершить, полагая

x* = x0, f(x*) = f(x0),

иначе - перейти к шагу 6.

6) Изменение направления и шага поиска: положить

.

Перейти к шагу 2.

Блок-схема.



Программа:

k = 0;

h = (b - a) / 4;

x0 = a;

f0 = function(x0, f);

label:

k++;

x1 = x0 + h;

f1 = function(x1, f);

if (f0 >= f1)

{

x0 = x1;

f0 = f1;

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

goto label;

}

if (fabs(h) <= e)

{

x = x0;

y = function(x0, f);

}

else

{

x0 = x1;

f0 = f1;

h = -h / 4;

goto label;

}

Вывод:

Левая граница отрезка а = 0

Левая граница отрезка b = 0,3

Eps = 0.02

Локальный минимум: 0.2906

Наименьшее значение функции: 0,5181

Количество итераций: 15

в) Метод дихотомии.

Алгоритм .

Шаг 1. Определить x1 и x2 по формулеам

, где д ? малое число

и вычислить f(x1) и f(x2).

Шаг 2. Если f(x1) ? f(x2), то перейти к отрезку [a;x2] , положив b=x2, иначе ? к

отрезку [x1,b], положив a=x1 .

Шаг 3. Найти достигнутую точность

еn = (b-a)/2

(здесь n ? номер итерации).

При еn > е, то идти к шагу 1, иначе завершить поиск x*, перейдя к шагу 4.

Шаг 4. Положить :

x? ? x = (a+b)/2; fmin ? f(x).

Блок-схема:



Реализация на С++:

#include <iostream>

#include <conio.h>

#include <math.h>

using namespace std;

int iter = 0;

float F(float x)

{ iter++;

return 5 * pow(x, 3.0) - 8 * pow(x, 2.0) - 20 * x; }

void main()

{ setlocale(LC_ALL, "Russian");

float a, b, E, c, x0, x1, f0, f1;

a = 2.0;

b = 5.0;

E = 0.02;

while (abs(b - a) >= E)

{ c = (b + a) / 2;

x0 = c - E;

x1 = c + E;

f0 = F(x0);

f1 = F(x1);

if (f0 <= f1) b = x0;

else a = x1;

}

float x = (b + a) / 2;

cout << "x = " << x << ", F(x) = " << F(x) << endl;//не считаем, поэтому вычитаем 1

iter--;

cout << "Обращений к функции:" << iter << endl;

_getch();

}

Вывод :

x = 0.2911; F(x) = 0.5174

Обращений к функции : 5

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

Алгоритм:

1) Задают начальные границы отрезка a, b и точность е.

2) Рассчитывают начальные точки деления:

х1 = а + 0,382(b-a), x2 = a + 0,618(b-a), f(x1), f(x2);

если f(x1) f(x2), то а= х1, х2 = а+0,618(b-a), иначе

b=x2, х1 = а + 0,382(b-a)

Если

и выход. Иначе возврат к шагу 2.

Блок-схема.

Программа:

i = 0;

while (abs(b - a) >= e) {

i = i++;

x1 = a + 0.382*(b - a);

x2 = a + 0.618*(b - a);

function(x1, f);

f1 = f;

function(x2, f);

f2 = f;

if (f1 >= f2) {

a = x1;

x2 = a + 0.618*(b - a);

}

else {

b = x2;

x1 = a + 0.382*(b - a);

}

Вывод:

Левая граница отрезка а = 0

Левая граница отрезка b = 0,3

Eps = 0.02

Локальный минимум: 0.2916

Наименьшее значение функции: 0.5166

Количество итераций: 7

4. Сравнение алгоритмов по количеству обращений к функции и по точности

Метод перебора - количество обращений: 15, наименьшее значение функции: 0.5041

Метод поразрядного поиска - количество обращений 15, наименьшее значение функции: 0.5181

Метод дихотомии - количество обращений 5, наименьшее значение функции: 0.5174

Метод золотого сечения - количество обращений 11, наименьшее значение функции: 0.5166

Рейтинг алгоритмов по количеству обращению к функции:

1.метод дихотомии

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

3.метод поразрядного поиска

4.метод перебора.

Рейтинг алгоритмов по точности вычисления (функция fmin= 0.504):

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

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

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

4.метод поразрядного поиска.

5. Вывод

Найдя точку экстремума для функции

экстремум алгоритм минимум унимодальность

на отрезке [0; 0,3] аналитическим методом, по графику, методом перебора, поразрядного поиска, дихотомии, золотого сечения и проанализировав пункт №5, можно сделать вывод, что наиболее подходящим методом для нахождения точки минимума этой функции является метод золотого сечения.

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