2.3. Фибоначчи әдісі

Әдісті түсіндірмес бұрын Фибоначчи саны анықтамасын енгізейік [11].

Анықтама 2. Фибонначчи саны келесі формула арқылы анықталады:

Фибоначчи сандарының тізбегі келесі түрде болады:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …..

Фибоначчи әдісі тізбекті стратегияға жатады. Бастапқы анықталмағандық аралығы және функция мәнің есептеу саны N беріледі. Аралықтың кішірею алгоритмі екі нүктедегі функция мәнін талдауға негізделген. Функция мәнің есептеу нүктелері N+1 Фибоначчи сандар тізбегін пайдалану арқылы орындалады. «Алтын қима» әдісіндегідей бірінші итерацияда екі нүктедегі функция мәнін есептеу керек болады. Ал әрбір келесі итерацияда тек ғана бір нүктедегі функция мәнің есептеу керек болады. Итерациялық процесстің аяқталу шарты стандартты түрде, яғни ағымдағы анықталмағандық аралығынын ұзындығы берілген шамадан кіші болғанда іздеу аяқталады.

Фибоначчи әдісінің алгоритмі [8].

Қадам 1.  бастапқы анықталмағандық аралығын,  - ақырғы аралықтың мүмкін болатын ұзындығын және  айырушылы тұрақтысын (константа различимости) беру керек.

Қадам 2.  шарты орындалатын ең кіші бүтін сан түрінде, функция мәндерін есептеу саны -ді және Фибоначчи сандар тізбегі , ,....,  табу керек.

Қадам 3.  деп аламыз.

Қадам 4. Келесі мәндерді есептеу керек:

, 

Қадам 5. J(z_k) мәндерін есептейміз.

Қадам 6. J(y_k),және J(z_k) мәндерін салыстырамыз:

а) егер J(y_k) £  J(z_k) болса, онда

, , ,

;

деп аламыз және 7-қадамға көшеміз;

ә) егер J(y_k) > J(z_k) болса, онда

, , ,

деп аламыз және 7-қадамға ораламыз.

Қадам 7. Итерациялық процесстің аяқталу шартын тексереміз және қажет болған жағдайда шешімді алу үшін функцияның мәнің есептеу үшін ақырғы N- есептеуді жүргіземіз:

а) егер болса, онда  деп аламыз да 5-қадамға ораламыз;

ә) егер  болса, онда әрқашан  болады. Яғни функция мәнің есептеудің жана нүктесі болмайды.

Онда , .  және  нүктелерінде функция мәні есептелінеді және анықталмағандықтын ақырғы аралығының шектері анықталады:

- егер  болса, онда

, ;

- егер  болса, онда

, .

Минимум нүктесін іздеу процессі аяқталады және . Жуық шешім ретінде ақрғы аралықтың кез келген нүктесін алуға болады. Мысалы, аралықтын ортаңғы нүктесін .

Жинақтылық. Фибоначчи әдісі үшін анықталмағандықтың бастапқы аралығының кішіреюнің салыстырмалы сипаттамасы келесі формула арқылы анықталады:

,

мұндағы N – функцияны есептеу саны.

Ескерту.

1. Функцияны есептеудің берілген N саныныда Фибоначчи әдісі әлдыңғы қарастырылған әдістерге (іріктеу әдісі, кесіндіні қақа бөлу әдісі, «алтын қима» әдісі) қарағанда анықталмағандықтың ақырғы аралығының ең аз шамасын береді.

2. k-итерацияда анықталмағандық аралық ұзындығы  ережесі бойынша қысқарады.

Мысал 3. Фибоначчи әдісі бойынша келесі функцияның минимумын табыныз

.

Шешуі.

1. Бастапқы аралықты береміз .

Айталық,

2. Фибоначчи сандарын анықтаймыз:

Онда

болғандықтан,  болады.

3. k = 0 деп аламыз.

4⁰. Келесі мәндерді есептейміз:

5⁰. Функция мәндерін есептейміз

6⁰.  мәндерін салыстырмаыз.  болғандықтан, ;

.

7⁰. Аяқталу шартын тексереміз: k = 0 ¹ N - 3 = 6 - 3 = 3; L₂ = [0; 6,154]. k=1 деп алып 5-қадамға көшеміз.

5¹. Функция мәндерін есептейміз   (5⁰-қадамда есептелген).

6¹.   мәндерін салыстырамыз.  болғандықтан,

.

7¹. Аяқталу шартын тексереміз: k = 1 ¹ N - 3 = 3; L₂ = [0; 3,846]. k = 2 деп алып, 5-қадамға көшеміз.

5². Функция мәндерін есептейміз    (5¹- қадамда есептелген).

6².  мәндерін салыстырамыз.  болғандықтан,

7². Аяқталу шартын тексереміз: k = 2 ¹ N - 3 = 3; L₄ = [1,538; 3,846]. k = 3 деп алып 5-қадамға көшеміз.

5³. Функция мәндерін есептейміз  .

6³.  мәндерін салыстырамыз.  болғандықтан,  

7³. Аяқталу шартын тексереміз: k  = 3 ¹ N - 3 = 3; L₅ = [2,308; 3,846]. Онда    

 мәнің есептейміз (5³- қадамда есептелген); .  болғандықтан,  

Сондықтан,

Келесі мәнді ескереміз,

.

Жуық шешім ретінде L₆ аралығының ортасын аламыз, яғни