Переваги і недоліки методу Фібоначчі

 

 for (iRow=0;iRow<=15;iRow++)

{

 printf(" ");

}

iRow=0;

printf ("%c",201);

for (iRow=0;iRow<=50;iRow++)

{

printf ("%c",205);

}

printf("%c",187);

printf ("\n");

iRow=0;

for (iRow=0;iRow<=15;iRow++)

{

printf(" ");

}

iRow=0;

printf ("%c",186);

for (iRow=0;iRow<=50;iRow++)

{

printf (" ");

}

iRow=0;

printf ("%c",186);

printf ("\n");

for (iRow=0;iRow<=15;iRow++)

{

printf (" ");

}

iRow=0;

printf ("%c",186);

printf ("                Курсовая                       ");

for (iRow=0;iRow<=2;iRow++)

{

 printf (" ");

}

iRow=0;

printf ("%c",186);

printf ("\n");

for (iRow=0;iRow<=15;iRow++)

{

 printf (" ");

}

iRow=0;

printf ("%c",186);

for (iRow=0;iRow<=50;iRow++)

{

 printf (" ");

}

iRow=0;

printf ("%c",186);

printf ("\n");

for (iRow=0;iRow<=15;iRow++)

{

printf (" ");

}

iRow=0;

printf ("%c",186);

printf (" (C)2012 Саша Тризна, Днепропетровск, Украина    ");

for (iRow=0;iRow<=1;iRow++)

{

 printf (" ");

}

iRow=0;

printf ("%c",186);

printf ("\n");

for (iRow=0;iRow<=15;iRow++)

{

printf(" ");

}

iRow=0;

printf ("%c",186);

for (iRow=0;iRow<=50;iRow++)

{

printf (" ");

}

iRow=0;

printf ("%c",186);

printf ("\n");

for (iRow=0;iRow<=15;iRow++)

{

 printf (" ");

}

iRow=0;

printf ("%c",200);

for (iRow=0;iRow<=50;iRow++)

{

printf ("%c",205);

}

printf ("%c",188);

printf ("\n");

printf ("\n");

printf ("\n");

 

 

kurs();// ВЫЗОВ ФУНКЦИИ ПОИСКА МИНИМУМА

 

  system("PAUSE"); 

  //return 0;

}

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Числа Фібоначчі в теорії пошуку

 

Відомо, що при дуже малих  швидкостях автомобіль витрачає на кожен  кілометр дороги відносно багато бензину. Велика його витрата і на великих  швидкостях. Якась проміжна швидкість  є при цьому «оптимальною»: при  пересуванні з цією швидкістю  автомобіль витрачає на кілометр дороги найменшу кількість пального. Таким  чином ми можемо передбачити, що приблизний графік залежності витрати автомобілем  пального на кілометр шляху від швидкості  автомобіля має вигляд (див.мал.1) , де у – витрата пального, а х – швидкість. Спочатку, у міру зростання швидкості, кілометрова витрата пального убуває до деякої мінімальної величини, а потім, з подальшим зростанням швидкості, починає неухильно (як прийнято говорити в математиці, «монотонно») зростати.

 Хоча загальні контури  графіка цієї залежності (спочатку  спуск, а потім підйом) однакові  майже для всіх автомобілів,  його точна форма може змінюватися  навіть в межах автомобілів  одного типу, залежавши від індивідуальних  особливостей автомобіля та механізмів.

Передбачимо тепер, що ми отримали в своє розпорядження автомобіль і хочемо зробити подорож по такій  місцевості, де в дорозі не вдасться заправитися пальним. Для того, щоб  мати можливість проїхати найбільшу  відстань, ми повинні досить точно  визначити швидкість, відповідну мінімальній  витраті пального. Ця швидкість зазвичай називається найбільш економічною  швидкістю.

 

 

 

 

 

 

 

 

 y

                                    

 

x 

малюнок 4.1 –  залежність витрати автомобілем пального на кілометр шляху

 

 

Визначати найбільш економічну швидкість автомобіля найприродніше  дослідним шляхом, проїжджаючи  з  різними швидкостями кілометрові  ділянки дороги, характер та якість якої типові для умов майбутньої подорожі, і вимірюючи кожного разу витрату  бензину. Оскільки це заняття не з  веселих, природньо задуматися над наступними питаннями:

 Скільки дослідів досить  для того, щоб визначити найбільш  економічну швидкість автомобіля  із найбільшою точністю?

Та яка ця найбільша  точність.

При цьому під визначенням  найбільш економічної швидкості  «з точністю до даного е» ми будемо розуміти V, що дійсне значення найбільш економічної  швидкості лежить між V- е  та V + е (тобто що помилка у визначенні цієї швидкості не може перевищувати е).

Для визначеності вважатимемо  заздалегідь відомим, що найбільш економічна швидкість нашого автомобіля лежить між деякими межами V’ i V’’. В якості V’ слід взяти швидкість яка свідомо не перевищує найбільш економічну, а в якості V’’ – таку швидкість, яка завідомо не менше її.

 

Відволікаючись від описаного  тільки що конкретного прикладу, розглянемо наступне математичне завдання.

 

Відповідно до сказаного  кожне конкретне завдання пошуку може мати три аспекти:

1. Наскільки може бути здійснена поставлена мета при даних можливостях і в даних умовах? Відносно до питання, що цікавить нас, це означає наступне.

Хай ми маємо право зробити  n послідовних визначень значення f, вибираючи кожного разу точку визначення на свій розсуд. В яких точках варто визначати значення функції, щоб точка х визначалася з найбільшою точністю, і яка ця точність?

2. Які можливості необхідно мати, щоб здійснити поставлену мету в даних умовах?

 У нашому завданні  це питання можна конкретизувати  так.

 Хай ми хочемо визначити  мінімізуючу функцію f точку х із заданою точністю е, тобто вказати таке х, що х розташоване між х - е і х + е. Скільки визначень значень функції f для цього необхідно зробити і як ці визначення організувати?

3. В яких умовах дані можливості достатньо для досягнення поставленої мети?

В даному випадку йдеться  про знаходженні найбільшого  інтервалу L зміни функції f (тобто найбільшого значення різниці х’ -х’’), для якого існує спосіб визначення тієї, що мінімізує f точки із заданою точністю е за n спостережень.

Тобто нам доведеться зараз  мати справу не з одним завданням, а з двома.

           По-перше, мова може йти про  знаходження мінімізуючої точки х в той же час значенням f(х), яке функція в цій точці приймає.

 По-друге, ми можемо  цікавитися лише самою точкою  х, залишаючись байдужим до  значення f(х).

Абсолютно ясно, що в першому  з цих завдань (будемо далі його називати завданням А) наші цілі ширші, ніж  в другому (яке ми назвемо завданням  Б). Тому природньо чекати:

Що при заданих можливостях  та умовах мету задачі А вдасться реалізувати  в меншій степені, ніж мету задачі Б;

 Що для здійснення  в рівній мірі цілей обох  завдань за однакових умов  в завданні А необхідні великі  можливості (при одній і тій  же погрішності е і однакових  довжинах L інтервалів змінення функції в завданні А необхідно, взагалі говорячи, більше n); що однакове здійснення цілей при рівних можливостях вимагає в завданні А легших умов.

 

Сенс вирішуваних нами завдань полягає в тому, що ми хочемо скласти не просто план дій, що дає у всіх і у тому числі  в найменш сприятливих випадках життя значення х зі вказаною точністю, а найбільш економічний з таких планів, тобто план, «найкращий в найгірших умовах». Але найгіршими умовами є ті, в яких число обчислюваних значень функції f максимально. Аналогічно найбільш економічним планом є такий план, який здійснює поставлену мету з мінімальним числом обчислень значень функції. Тому найкращий в найгірших умовах план часто називають мінімаксимальним планом, або планом мінімакса. Я цей план називатиму оптимальним. Суть дій, для оптимального плану (як у цій, так і в будь-якій аналогічній задачі), можна охарактеризувати як пошук того що «ховається» від нас мінімуму функції, «прагнучого виявитися якраз не там, де ми його шукаємо». Сказане не має нічого спільного ні з містикою, ні із забобонами а є лише характеристикою тих найгірших обставин, до яких ми і кваліфікуємо наші дії як найкращі.[1]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Реалізація методу безумовного екстремуму

 

Структура пошуку мінімуму

1. Знайти погрішність

e=(b-a)/(F[N]);

2. Знаходимо x1

            x1=F[N-2];

           x1=(x1/F[N])*(b-a)+a;

3. Знаходимо y1

y1=function(x1);

4. Знаходимо x2

x2=F[N-1];

x2=(x2/F[N])*(b-a)+a;

5. Знаходимо y2

y2=function(x2);

6. Порівняння y1 та y2

if (y1<y2)

{

b=x2;

x2=x1;

 

y2=y1;

x1=a+b-x2;

y1=function(x1);

}

 

else

{

a=x1;

x1=x2;

   y1=y2;

 

x2=a+b-x1;

  y2=function(x2);

}

Б.)

 if (y1<y2)

{

b=x2;

x2=x1;

y2=y1;

}

 

else a=x1;

x1=x2-e;

y1=function(x1);

в.)

if(y1<y2)

b=x2;

else  

a=x1;

7. Вираховування мінімуму

min=(a+b)/2;

 

 

 

 

 

 

 

 

 

 

Висновок

 

У даній роботі був розглянутий  один з ключових методів прямого  пошуку метод Фібоначчі. Результатом роботи стало здобуття робочої програми на мові С++, яка дозволяє вирішувати задачу знаходження мінімумів функції за задану кількість кроків.     Отримані і розібрані, процес роботи і побудови алгоритмів методу Фібоначчі. На основі цих алгоритмів і була побудована програма.     В цілому цілі поставлені на початку роботи, були досягнуті.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Література

 

1. Н.Н. Воробьев Числа Фибоначчи. – главная редакция физико-математической литературы 1978.
2. Лаптев, В. В. C++. Экспресс-курс./ В.В Лаптев - СПб.: БХВ-Петербург, 2004. - 512 с.