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

Рассмотрим все множество последовательных методов для минимизации унимодальных функций. Установлено, что оптимального метода в данном классе не существует. d-оптимальным методом (позволяющим сколь угодно близко подойти к минимальной точности) является метод Фибоначчи.

Метод основан на использовании чисел Фибоначчи, которые определяются рекуррентными соотношениями:

Ф ₀ = 1; Ф ₁ = 1; Ф _п = Ф _{п- 2} + Ф _{п- 1}; (п ³ 2).

Используя коэффициенты t» 1,618и x» 0,618,характеризующие золотое сечение, по индукции можно показать, что числа Фибоначчи представимы также в виде уравнения Люкаса:

Второе слагаемое в уравнении Люкаса быстро стремится к нулю. Уже при сравнительно небольших п (п = 5, 6 ) его доля составляет менее одного процента и им можно пренебречь. Следовательно, с высокой точностью при п > 5 можно считать:

Ф_n» t ^{n+ 1} / 2,236.

Число n (e) необходимых вычислений функции при заданной точности в методе Фибоначчи сокращается за счёт более оптимального выбора последовательности пробных точек. Длина отрезка [ a, b ] интерпретируется как число Фибоначчи Ф_{п+ 1}, умноженное на масштабный коэффициент C: (b-a) =СФ_{п+ 1}.Затем данное число разбивается пробными точками на числа Фибоначчи более низкого порядка: СФ_{п+ 1} = СФ_п + СФ_{п- 1}и т.д., пока не будет получен доверительный отрезок [ a_k, b_k ]длины b_k - a_k £ e, где e - заданная точность. Итоговый доверительный отрезок [ a_k, b_k ] интерпретируется как число Фибоначчи Ф ₁=1, умноженное на масштабный коэффициент С= (b-a) /Ф_{п+ 1}:

(b_k - a_k ) = Ф ₁ (b-a)/ Ф_{п+ 1} = (b-a)/ Ф_{п+ 1}.

Из соотношений Ф_{n+ 1} » t^{n+ 2} / 2,236 ³ (b-a)/e = M следует правило приближенного выбора необходимого максимального используемого числа Фибоначчи и величины п: Ф_{п+ 1} ³ (b-a)/e = М, п = ]log _t (2,236 (b-a)/e)[ - 2.

Поскольку для программной реализации необходимы точные значения чисел Ф_п, то можно использовать следующие эмпирические формулы, дающие верный результат для п< 77(при этом Ф ₇₆» 5,52794× 10¹⁵).

1. Вначале вычисляется величина

Затем рассматриваем два случая: (n< 46) и (46 £n< 77).

2. n< 46. При четных n, меньших 36: Ф_п: = [ Р+1 ], иначе: Ф_п: = [ Р ].

3. 46 £ n < 77. Вначале присваиваем Ф_п: = [ Р ].

При n > 70 Ф_п: = Ф_п + 70 - n.

При n> 74 дополнительно Ф_п: = Ф_п + 296 - 4 n.

4. При n ³ 77числа Фибоначчи можно определить по основному рекуррентному соотношению, начиная с чисел Ф₇₅ = 3.416.454.622.906.707, Ф₇₆ = 5.527.939.700.884.757.

Метод работает следующим образом.

Предварительные действия (Шаг 0 ). Рассчитываем масштаб задачи М= (b-а)/e, величины п и чисел Фибоначчи Ф _п и Ф _{п+ 1}, при которых Ф_п £ М £ Ф_{п+ 1}. Начальный доверительный отрезок принимаем равным исходному: а ₀ = а, b ₀ = b. Поскольку метод симметричный, то по формулам, содержащим числа Фибоначчи, теоретически достаточно рассчитать только положение на отрезке[ а ₀, b ₀]первой точки. Вычисление производим по формуле

х ₁ = а + (b - a) Ф _{п- 1} / Ф _{п +1} = а + С Ф _{п- 1}.

В полученной точке вычисляем значение функции F (х ₁), переходим к Шагу 1.

Шаги i= 1 ¸ (n- 1). К их началу известны:

а) доверительный отрезок [ a_{i- 1}, b_{i- 1}] длины D _i = b_{i- 1} - a_{i- 1} = С Ф _{п+ 2 – i},

б) пробная точка х, в которой уже найдено значение функции F(х), отстоящая от ближнего края отрезка [ a_{i- 1}, b_{i- 1}]на расстоянии: D _i Ф _{п – i}/ Ф _{п+ 2 – i}.

Расчет новой пробной точки, функции в ней и упорядочение пробных точек и сокращение доверительного отрезка выполняем, как и в методе золотого сечения:

1. Расчет положения новой пробной точки: х¢ = (b_{i- 1} + а_{i- 1}) - х, расчет значения функции F (x¢).

2. Упорядочение пробных точек х, х¢ и значений функции в них:

если (х < х¢), то { х ₁ = х; F (x ₁)= F (x); х ₂ = х¢; F (x ₂)= F (x¢) };

иначе { х ₁ = х¢; F (x ₁)= F (x¢); х ₂ = х; F (x ₂)= F (x) }.

3. Сокращение доверительного отрезка:

а) при F (x ₁) ³ F (x ₂) принимаем: a ₁ = х ₁, х ₁ = х ₂, b ₁ = b ₀,

б) при F (x ₁) < F (x ₂) принимаем: a ₁ = а ₀, х ₂ = х ₁, b ₁ = х ₂.

Характеристики произвольного i- го шага:

а) длина отбрасываемой части отрезка: d _i = D _{i- 1} Ф _{п –i} / Ф _{п–i +2} = С Ф _{п – i+ 1},

б) длина оставшегося доверительного отрезка [ a _i,b _i ]: D _i = D _{i- 1} - d _i = С Ф _{п– i+ 1}.

Шаг n (заключительный ). К началу известен:

а) доверительный отрезок [ a_{n- 1}, b_{n- 1}]длины D _{n- 1} = b_{n- 1} - a_{n- 1} = С Ф ₂,

б) пробная точка х, в которой уже найдено значение функции F (х), отстоящая от ближнего края отрезка [ a_{n- 1}, b_{n- 1}]на расстоянии: D _{n- 1} Ф ₁/ Ф ₂ =0, 5 D_n-1.

Особенностью заключительного шага является то, что известная пробная точка х теоретически лежит точно в средней точке доверительного отрезка [ a_{n- 1}, b_{n- 1}]. В силу этого вторую пробную точку нельзя рассчитывать как симметричную х относительно центра [ a_{n- 1}, b_{n- 1}], поскольку она совпадёт с х.

Поэтому на последнем Шаге п принимаем:

x ₁ := x; F (x ₁): = F (x); x ₂:= x ₁ + d;

где d - некоторое малое число, можно принять d=0,1e.

После вычисления F (х₂)производим по обычной схеме анализ F (х ₁), F (х ₂)и последнее сокращение доверительного отрезка.

Итоговая длина D _п доверительного отрезка равна СФ ₁ + d либо С Ф ₁.

Если число Ф_{п+ 1}близко к М, то из-за сдвига точки x ₂ на dдлина D _n может незначительно превысить гарантированную точность e.

Скорость сходимости и точность метода. Учитывая, что на первом шаге функция рассчитывается дважды, получим величину n (e) для метода Фибоначчи:

n (e) = ]log_t (2,236(b-a)/e)[-1.

Из этого же уравнения находим зависимостьe(n) точности от общего числа вычислений функции:

e(n)» 2,236(b-a)/t ^п+1=2,236 (b - a)x ⁽ⁿ⁺¹⁾.

Разделив точность метода золотого сеченияe (п) = (b - a)x ^{( n- 1)}на эту величину, получим значение 1/(2,236x ² )» 1,17. Таким образом, при n ® ¥ метод золотого сечения в среднем хуже метода Фибоначчи (при заданном числе вычислений больше длина получаемого доверительного отрезка) приблизительно на 17%.

Замечание. При достаточно больших n, как следует из приближённого уравнения Люкаса, отношение Ф _п / Ф _{п+ 1}стремится к коэффициенту x = 1/t. Следовательно, первая пробная точка метода Фибоначчи х ₁ = а + (b - a) Ф _{п- 1} / Ф_{п+ 1} стремится к первой пробной точке х ₁метода золотого сечения.

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

Пример 1. Найти минимум функции F (х) = х² – 2 х на исходном доверительном отрезке [0,2; 2]по методу Фибоначчи при заданной точности e =0,5.

Решение.

Шаг 0. Предварительные действия. Масштаб задачи М = (b-a)/e=3,6.Из соотношений Ф ₃ =3 < 3,6 < Ф ₄ =5следует: n= 3, Ф_{п+ 1} = 5, Ф_п = 3.

Доверительный отрезок: а ₀ = а = 0,2; b ₀ = b= 2.

Шаг 1. Пробные точки: х ₂ = а ₀ + (b ₀ - a ₀) Ф _п / Ф _{п+ 1} = 1,28; х ₁ = а ₀ + b ₀ - х ₂ = 0,92.

Значения функции: F (x ₁)=-0,9936; F (x ₂)=-0,9216. F (x ₁)< F (x ₂),поэтому отбрасываем часть отрезка [ x ₂ ;b ₀].Получаем новый отрезок [ а ₁; b ₁]= [0,2;1,28].

b ₁ -а ₁ = 1,08 > e = 0,5;продолжаем поиск.

Шаг 2. Границы доверительного отрезка а ₁=0,2; b ₁=1,28. Известно значение F (x) = -0,9936при х= 0,92.

Новая пробная точка: х¢ = а ₁ + b ₁ - х = 0,56. Значение функции в ней: F (x ¢)= -0,8064.

Так как х¢ < х, то принимаем: х ₁ = х¢; F (x ₁)= F (x¢); х ₂ = х; F (x ₂)= F (x). Поскольку F (x ₁) >F (x ₂),то отбрасываем часть доверительного отрезка, равную [ a ₁ ;x ₁].

Получаем новый доверительный отрезок [ а ₂ ;b ₂]= [0,56;1,28]. Так как b ₂ -а ₂ = 0,72 > e;то продолжаем поиск.

Шаг 3 (заключительный). Границы доверительного интервала а ₂=0,56; b ₂=1,28. Известно значение F (x) = -0,9936при х= 0,92.

Новую пробную точку строим сдвигом известной: х¢ = 0,92+0,01=0,93. Значение функции в ней: F (x¢) = -0,9951.

Поскольку х¢>х, то полагаем х ₁ =х; F (x ₁)= F (x); х ₂ =х¢; F (x ₂)= F (x¢).

Так как F (x ₁)> F (x ₂),то отбрасываем часть доверительного отрезка [ a;x ₁].Получаем итоговый отрезок [ а ₃ ;b ₃]= [0,92;1,28]. b ₃ -а ₃ = 0,36 < e;поиск завершаем.

Ответ. Выполнено3 шага при 4 пробных точках. Найден доверительный интервал [ а ₃, b ₃] = [0,92; 1,28]длины 0,36.

По сравнению с методом золотого сечения число вычислений функции осталось прежним, но сократилась длина итогового доверительного интервала с 0,4248 до 0,36.

Несмотря на то, что метод Фибоначчи является самым быстрым из регулярных последовательных методов, применяемых для минимизации однопараметрических унимодальных функций на отрезке, он не намного лучше метода золотого сечения при том, что значительно сложнее в реализации.

Вопросы для проверки знаний.

1. Какая числовая последовательность называется числами Фибоначчи?

2. В каком виде числа Фибоначчи могут быть явно представлены в а) точной и б) приближенной формах?

3. Как по заданному масштабу задачи определить число итераций п, необходимое для ее решения по методу Фибоначчи? Какие дополнительные данные помимо п требуются для начала итераций?

4. Чем отличается первый шаг от последующих в методе Фибоначчи?

5. Какая особенность заключается в выполнении последнего шага в методе Фибоначчи?

6. К какому методу стремятся при числе итераций n ® ¥ положения первых пробных точек в методе Фибоначчи?