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

Федеральное Государственное Бюджетное Образовательное Учреждение Высшего Профессионального Образования

“Омский государственный технический университет”

Кафедра “Информатика и вычислительная техника”

Направление 230100 “Информатика и вычислительная техника”

Профиль “Технологии разработки программного обеспечения”

Расчетно-графическая работа

На тему: «Разработка программы для поиска минимума функций методом Фибоначчи»

по дисциплине «Системный анализ, оптимизация и принятие решений»

Выполнил студент

Кудашев Е.Павлович

Проверил: А.С. Яговдик

2015



Оглавление

Введение

1. Описание метода для поиска минимума

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

3. Интерфейс пользователя

4. Результаты тестирования

Заключение

Библиографический список

Приложение



Введение

В данной работе мы рассмотрим один из методов одномерной оптимизации, а именно - метод Фибоначчи.

При построении процесса оптимизации стараются сократить объем вычислений и время поиска.

Этого достигают обычно путем сокращения количества вычислений значений целевой функции f(x). Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод Фибоначчи.



1. Описание метода для поиска минимума

Последовательность чисел Фибоначчи определяется соотношением:

	(8)

и имеет вид:

i	0	2	2	3	4	5	6	7	8	9	10	11	12
Fi	1	1	2	3	5	8	13	21	34	55	89	144	233	и т.д.

Подобно методу золотого сечения процедура поиска с использованием чисел Фибоначчи требует два вычисления функции на первом шаге, а на каждом последующем - только по одному. Однако, в отличие от метода золотого сечения, в этой процедуре общее число S вычисления функции должно быть выбрано заранее. Кроме того, сокращение интервала неопределенности не остается постоянным, а меняется от шага к шагу: на k-ом шаге длина интервала неопределенности сжимается с коэффициентом

Первые два вычисления проводятся в точках:

расположенных симметрично относительно середины отрезка [a,b]. Если f(x₁)<f(x₂), то новым отрезком локализации минимума является [a, x₂], в случае f(x₁)?f(x₂)-[x₁, b]. Каждая следующая точка выбирается симметрично относительно середины полученного отрезка к лежащей внутри этого отрезка точке уже проведенного вычисления (x₁ или x₂). При этом любая внутренняя точка делит отрезок локализации в отношении, двух последовательных чисел Фибоначчи. алгоритм интерфейс программа фибоначчи

Взаимное расположение точек первых трех вычислений в случае f(x₁)<f(x₂) показано на рис. 7.

Рис. 7.

После (S-1)-го шага точка проведенного вычисления оказывается в середине отрезка локализации. Точка последнего, S-го, шага выбирается на расстоянии д от середины этого отрезка, где д - заранее фиксированное малое положительное число (константа различимости).

После S вычислений функции длина отрезка локализации составляет (с точностью до д):

	(9)

Сравнение (9) и (7) показывает, что при одном и том же S метод Фибоначчи дает меньший интервал неопределенности, чем метод золотого сечения, т.е. является более эффективным. Однако для достаточно больших S значение стремится к (0,618)^S-1 , так что эти методы становятся почти идентичными. В том случае; когда при использовании метода Фибоначчи задан .конечный интервал неопределенности е, число S можно определить из условия:

	(10)

Алгоритм минимизации функции f(x) с использование, чисел Фибоначчи.

1. По заданной точности рассчитывается вспомогательное число

2. Для полученного значения N находится такое число Фибоначчи F_S, для которого выполняется неравенство:

3.

4. По формуле (9) определяется длина конечного интервала неопределенности l.

5. Вычисляются значения x₁=a+l•F_S-2, x₂=b-l•F_S-2.

6. В зависимости от соотношения f(x₁) и f(x₂) выбирается новый интервал локализации минимума.

7. Внутри полученного интервала находится новая точка (x₁ или x₂), симметричная к уже имеющейся точке и отстоящая от конца интервала на величину l•F_S-1-k , где k - номер шага. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 5, до тех пор, пока k не станет равно S-1. Тогда переходят к пункту 7.

8. Полагают x₂=x₁+д, находят f(x₂). Если f(x₂)>f(x₁)то минимум реализуется на интервале (a, x₁), в противном случае - на интервале (x₁ , b).



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



3. Интерфейс пользователя

Интерфейс пользователя выглядит следующим образом:



4. Результаты тестирования

Метод Фибоначчи:

Итерация № 1

x1 = 0.590168F(x1) = -0.129898

x2 = 0.954916F(x2) = -0.987988

Итерация № 2

x1 = 0.954916F(x1) = -0.987988

x2 = 1.18034F(x2) = -0.793145

Итерация № 3

x1 = 0.815587F(x1) = -0.808495

x2 = 0.954916F(x2) = -0.987988

Итерация № 4

x1 = 0.954916F(x1) = -0.987988

x2 = 1.04101F(x2) = -0.989773

Итерация № 5

x1 = 1.04101F(x1) = -0.989773

x2 = 1.09424F(x2) = -0.945033

Итерация № 6

x1 = 1.00815F(x1) = -0.9996

x2 = 1.04101F(x2) = -0.989773

Итерация № 7

x1 = 0.987769F(x1) = -0.999106

x2 = 1.00815F(x2) = -0.9996

Итерация № 8

x1 = 1.00815F(x1) = -0.9996

x2 = 1.02062F(x2) = -0.997431

Итерация № 9

x1 = 1.00024F(x1) = -1

x2 = 1.00815F(x2) = -0.9996

Итерация № 10

x1 = 0.995686F(x1) = -0.999889

x2 = 1.00024F(x2) = -1

Итерация № 11

x1 = 1.00024F(x1) = -1

x2 = 1.0036F(x2) = -0.999922

Итерация № 12

x1 = 0.999053F(x1) = -0.999995

x2 = 1.00024F(x2) = -1

Итерация № 13

x1 = 1.00024F(x1) = -1

x2 = 1.00242F(x2) = -0.999965

Итерация № 14

x1 = 1.00124F(x1) = -0.999991

x2 = 1.00024F(x2) = -1

Итерация № 15

x1 = 1.00024F(x1) = -1

x2 = 1.00342F(x2) = -0.99993

Итерация № 16

x1 = 1.00442F(x1) = -0.999883

x2 = 1.00024F(x2) = -1

Итерация № 17

x1 = 1.00024F(x1) = -1

x2 = 1.00442F(x2) = -0.999883

Результат:

x = 1.00392F(x) = -0.999908

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



Заключение

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

Получен и разобран, процесс работы и построения алгоритма метода Фибоначчи. На основе этого алгоритма и была построена программа.

Минусом данной программы можно считать то, что функцию необходимо прописывать непосредственно в коде программы.

В целом, цели поставленные в начале работы, были достигнуты.



Библиографический список

1. ru.wikipedia.org/wiki - Информационная система: Википедия - свободная энциклопедия [Электронный ресурс]. - Режим доступа:

2. tp://dit.isuct.ru/ivt/sitanov/Literatura/M171/Pages/Glava1_4.htm

3. Пантелеев. Методы оптимизации в примерах, 2005.

4. Романов. Системный анализ для инженеров, 2006.



Приложение

Main.cpp

#include <iostream>

#include <cmath>

#include <fstream>

#include "Methods.h"

void Fib(double, double, std::ofstream&);

int main()

{

std::ofstream cout("rezult.txt", std::ios::out);

setlocale(LC_ALL, "Russian");

double a(0), b(2.5);

Fib(a, b, cout);

getchar();

}

Methods.h

#define eps 1e-3

double Fun(double x)

{

return (2 * x * x * x - 6 * x + 3);

}

int F(int n)

{

int f, f1(1), f2(1), m(0);

while(m < n - 1)

{

f = f1 + f2;

f1 = f2;

f2 = f;

++m;

}

return f1;

}

void Fib(double a, double b, std::ofstream& cout)

{

cout<<"\n\n\n\tМетод Фибоначчи:\n\n";

double x1, x2, _x, xf1, xf2;

int k(0);

int N(0);

double fn1(1), fn2(1), fn, f = (b - a) / eps;

while(fn1 < f)

{

fn = fn1 + fn2;

fn1 = fn2;

fn2 = fn;

++N;

}

x1 = a + (double)F(N - 2) / F(N) * (b - a) - (N&1 ? -1 : 1) * eps / F(N);

x2 = a + (double)F(N - 1) / F(N) * (b - a) + (N&1 ? -1 : 1) * eps / F(N);

xf1 = Fun(x1);

xf2 = Fun(x2);

P:

++k;

if(xf1 >= xf2)

{

a = x1;

x1 = x2;

xf1 = xf2;

x2 = a + (double)F(N - k - 1) / F(N - k) * (b - a) + ((N - k)&1 ? -1 : 1) * eps / F(N - k);

xf2 = Fun(x2);

}

else

{

b = x2;

x2 = x1;

xf2 = xf1;

x1 = a + (double)F(N - k - 2) / F(N - k) * (b - a) - ((N - k)&1 ? -1 : 1) * eps / F(N - k);

xf1 = Fun(x1);

}

cout<<"Итерация № "<<k<<'\n'

<<"x1 = "<<x1<<"\t\tF(x1) = "<<xf1

<<"\nx2 = "<<x2<<"\t\tF(x2) = "<<xf2

<<'\n'<<std::endl;

if(fabs(b - a) <= eps)

{

_x = (a + b) / 2;

cout<<"Результат:\nx = "<<_x<<"\t\tF(x) = "<<Fun(_x)<<

"\nКоличество итераций: "<<k;

}

else

goto P;

}

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

...