Характерной чертой метода является способ вычисления границ текущего интервала, основанный на использовании чисел Фибоначчи. Метод можно использовать в том случае, когда известно число испытаний n. Основная идея метода состоит в следующем :
Пусть необходимо провести n испытаний (вычислений f(x) в пробных точках) для отыскания минимума унимодальной функции на [a0, b0]. Положим, что проведены все испытания кроме последнего, и имеется интервал неопределенной длины Ln-1 (рис. 2.2).
Внутри этого интервала следует поместить последнюю точку xn и длина последнего интервала Ln должна быть наименьшей. Оптимальным при этом будет расположение точек xn и xn-1 симметрично относительно середины интервала и удаленных от нее на величину e/2 (e - точность поиска). Следовательно, [2]
Далее пусть проведены все испытания, кроме двух последних. Точки xn и xn-1 будем располагать симметрично внутри интервала Ln-2 на расстоянии Ln-1 от концов этого интервала, т.е.
Проведя аналогичные рассуждения для любого интервала Lj, получающегося после проведения j испытаний, получим рекуррентную формулу
Используя формулы (17) и (19), можно вычислить
Введем последовательность чисел Фибоначчи Fk, определяемую следующим образом
Если исходный отрезок [a0, b0] имеет длину L1 = b0-a0, то
Таким образом, стратегия метода гарантирует, что длина отрезка Ln после n испытаний будет не больше величины Ln, вычисленной по формуле (24) для любой унимодальной функции f(x).
При реализации итерационного процесса используют правило симметрии. Необходимо найти положение первой точки, которая располагается на расстоянии L2 от одного из концов начального отрезка [a0, b0]. Вторая точка располагается согласно правилу симметрии на расстоянии L2 от второго конца отрезка [a0, b0] (рисунок 2.3).
Длина отрезка L2 вычисляется по формуле
Аналогично вычисляются координаты всех n точек, т.е. для вычисления текущего отрезка [ak+1; bk+1] выбираются точки x1* и x2* по формулам
где Fn-1-k, Fn+1-k, Fn-k – числа Фибоначчи.
Рис. 2.2. Расположение точек 
при поиске минимума 
![clip_image040[1]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlVQ2A0p_u0lSfiHAYP-vPVNO4fXvaHKSp_fPuvWJwbz66m2l4-Es-GEuePaHRj81p7D0XMCz0AXrSSfv-fWO86ZSGvBaji0yBfWICv9v4J-LvxNWOhiRTjas4YFTLcg_5Qwxx_b1H9GM/s1600-h/clip_image040%5B1%5D%5B2%5D.gif "clip_image040[1]"){kind=small}
Ниже представлен алгоритм одной из модификаций метода Фибоначчи. Пусть а = а0, b = b0.
1 Если n=1, то перейти к п. 2. Если n > 1, то перейти к п. 3.
2 Вычислить 
3 Определить последовательность чисел Фибоначчи: F0 = 1, F1 = 1, Fk = Fk-1+Fk-2 для k = 2,3,…,n. Вычислить
4 Вычислить значения функции f(x1) и f(x2).
5 Если n = 2, то перейти к п. 6. Если n > 2 , то перейти к п. 9.
6 Если f(x1) £ f(x2), то перейти к п. 7. Если f(x1) > f(x2), то перейти к п. 8.
7 Положить 
![clip_image044[1]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhp_kVqV6RWv1lMUXLeAyYLV9RjC1bYrW0ylF3cYdtquBtQrEjadSRrMp6Br3lQW2scNoY7wLFV7uDm9ldozPfUqwRr2HhYqvZ5MHhGl6CeGCVtG9HKNLdo805zDbf2p1lKtn-VInPNgg0/s1600-h/clip_image044%5B1%5D%5B2%5D.gif "clip_image044[1]"){kind=small}
8 Положить 
![clip_image044[2]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOy9jevHz_Dy991ob8IAAiVlvTxOT35ncvzwHHkZeKedDV45bqJ0NFB2Q1krO6eQlt50cXlUesAzJ5oW2LY8aGuH4uuEFZKDckEk1K1XoO2BeiD5h1P1NZPV0a0qhHiIH9tq23FNk8hLE/s1600-h/clip_image044%5B2%5D%5B2%5D.gif "clip_image044[2]"){kind=small}
9 Если f(x1) £ f(x2), то перейти к п. 10. Если f(x1) > f(x2), то перейти к п. 13.
10 Положить b = x2, x2 = x1 и n = n-1.
11 Вычислить
12 Вычислить f(x1) и перейти к п. 5.
13 Положить a = x1, x1 = x2 и n = n-1.
14 Вычислить
15 Вычислить f(x2) и перейти к п. 5.
16
Пример 4. Используя метод Фибоначчи найти минимум функции 
Решение: поиск решения приведен в таблице 1.
Числа Фибоначчи F2=1, F3=2; F4=3; F5=5; F6=8; F7=13; F8=21; F9=34; F10=55; F11=89; F12=144.
Таблица 1.
| a | b | x1 | x2 | f(x1) | f(x2) | n | |
| Итерация 1 | 0 | 1 | 0,38194 | 0,618 | -1,17337 | -1,09133 | 10 |
| Итерация 2 | 0 | 0,618 | 0,23613 | 0,381 | -1,15482 | -1,17337 | 9 |
| Итерация 3 | 0,236 | 0,618 | 0,38194 | 0,382 | -1,17337 | -1,17336 | 8 |
| Итерация 4 | 0,236 | 0,382 | 0,29192 | 0,381 | -1,16856 | -1,17337 | 7 |
| Итерация 5 | 0,291 | 0,382 | 0,38194 | 0,326 | -1,17337 | -1,17289 | 6 |
| Итерация 6 | 0,291 | 0,326 | 0,30517 | 0,381 | -1,1706 | -1,17337 | 5 |
| Итерация 7 | 0,305 | 0,326 | 0,38194 | 0,318 | -1,17337 | -1,17217 | 4 |
| Итерация 8 | 0,305 | 0,318 | 0,31047 | 0,381 | -1,17128 | -1,17337 | 3 |
| Итерация 9 | 0,310 | 0,318 | 0,38194 | 0,306 | -1,17337 | -1,17081 | 2 |
| Итерация 10 | 0,310 | 0,318 | 0,38194 | 0,306 | -1,17337 | -1,17081 | 1 |
0 коммент.:
Отправить комментарий