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

• Название: Метод Фибоначчи
• Дата: 16.06.2022
• Размер: 359.47 Kb.
• Имя файла: Метод Фибоначи.docx
• Тип: Документы; #595675

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

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

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

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

Определение.

Последовательность чисел называется последовательностью Фибоначчи.

Зададимся некоторым и выпишем последовательность чисел Фибоначчи.

Итак, необходимо найти минимум на отрезке с точностью .

Опишем 1-й шаг метода Фибоначчи.

Как и в предыдущем методе найдем на отрезке :

;

Из формул видно, что симметричны относительно середины отрезка .

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

В силу свойств последовательности Фибоначчи, на каждом шаге, кроме 1-го и предпоследнего, вычисляется одно новое значение функции, другое значение используется из предыдущего шага. Только на 1-м шаге значение вычисляется дважды, а на предпоследнем, когда совпадает с , известно из предыдущего шага. Можно показать, что на -м шаге совпадут, этим завершится процедура деления отрезка неопределенности. Для получения окончательного результата необходимо вычислить и , где - малая величина, параметр метода.

Если , то полагают, что , в противном случае .

Посмотрим, как уменьшается отрезок неопределенности

;





Таким образом, -й шаг метода Фибоначчи обеспечивает уменьшение длины отрезка неопределенности в раз.

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

Замечание 1.

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

Замечание 2.

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



Блок-схема метода Фибоначчи

Пример.

Найти минимум на отрезке c . Начнем с определения :



Для решения поставленной задачи потребуется 9 шагов по методу Фибоначчи, при этом понадобится 9 раз вычислять . Заметим, что для решения этой же задачи методом дихотомии мы проделали 7 шагов, то есть вычисляли 14 раз.

1-й шаг.

;

.

2-й шаг.





.

3-й шаг.

;

.

4-й шаг.

;

.

5-й шаг.

;

.

6-й шаг.

;

.

7-й шаг.





.

8-й шаг.

;

.

9-й шаг.

;

.



Замечание.

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

Метод золотого сечения.

В теории чисел показано, что существует предел отношения соседних чисел Фибоначчи



показывает, как соотносятся длины отрезков неопределенности при применении метода Фибоначчи.

С другой стороны, рассмотрим следующую задачу. Возьмем отрезок , найдем внутри этого отрезка , образующие золотое сечение.

Для этого необходимо выполнение следующих условий:



Найдем ,при котором возможны равенства

,

,

,



Поскольку



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





Если - заданная точность, то число шагов метода золотого сечения следует находить как решение неравенства



Замечание.

Метод золотого сечения немного медленнее сходится, чем метод Фибоначчи.

С другой стороны, при необходимости, для получения более точного результата, есть возможность его продолжить.

При шагах метода золотого сечения вычисляется раз, так как на 1-м шаге вычисляется дважды, а на последующих шагах по одному разу, так же как и в методе Фибоначчи одна из внутренних точек отрезка неопределенности последующего шага совпадает с одной из точек предыдущего шага.



Блок-схема метода золотого сечения

Пример.

Найти минимум на отрезке c

Предварительно определим, сколько потребуется шагов метода золотого сечения.



Итак, потребуется 8 шагов метода золотого сечения, при этом значения придется вычислять 9 раз, то есть трудоемкость такая же, как была в методе Фибоначчи.

1-й шаг.

;



.

2-й шаг.

;



.

3-й шаг.

;



.

4-й шаг.

;



.

5-й шаг.

;



.

6-й шаг.

;



.

7-й шаг.

;



.

8-й шаг.

;



.


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

Функция f(x) называется унимодальной на отрезке [a,b], если

1. 
   имеет единственную точку минимума x* на этом отрезке
   
2. 
   f(x) монотонно убывает на [a,x*], возрастает на [x*,b].
   

Свойства унимодальных функций.

Пусть f(x) унимодальна на [a,b], x,z принадлежат отрезку, x
1) если f(x)
2) если f(x)>f(z), то x* принадлежит [x,b];

3) если f(x)=f(z), то x* принадлежит [x,z];
Алгоритм.

1) Задаются: отрезок локализации L0 = [a0,b0], ε > 0, l > 0, (отрезок локализации можно найти алгоритмом Свена);

2) Необходимо найти N – количество вычислений как наименьшее целое число, при котором FN >= | L0 | / l

3) Количество итераций k = 0;

4) Вычисляются:

xk=ak + (FN-2 / FN) * (bk - ak)

yk=ak + (FN-1 / FN) * (bk - ak)

5) Вычисляютсяи сравниваются f(xk) и f(yk)

5.1) если f(xk) <= f(yk) , то

ak+1 = ak

bk+1 = yk

yk +1 = xk

xk+1= ak+1 + (FN – k — 3 / FN — k — 1) * (bk - ak)

5.2) если f(xk) > f(yk) , то

ak+1 = xk

bk+1 = bk

xk+1=yk

yk+1= ak+1 + (FN – k — 2 / FN — k — 1) * (bk - ak)

6) если k ≠ N-3, то k=k+1 и к 5)

если k= N-3, то

xN-2=yN-2 = (aN – 2 + bN – 2)/2

xN-1 = xN-2 = yN-2

yN-1= xN-1+ ε
7) в xN-1 и yN-1 вычисляются значения функции и находятся границы конечного отрезка локализации

7.1) если f(xN-1) <= f(yN -1), то

aN — 1 = aN — 2

bN — 2 = yN — 1
7.2) если f(xN-1) > f(yN -1), то

aN — 2 = xN — 1

bN — 1 = bN — 2

8) x*=(ak+1 + bk+1)/2

Найдем минимум функции:

f(x) = (x-3)²


Используем для этого Метод Фибоначчи.
Важнейшая особенность этого метода состоит в том, что он позволяет для заранее заданного числа вычислений функции построить оптимальную процедуру поиска минимума унимодальной функции.
Предположим, что заданный начальный интервал неопределенности [a₁,b₁], [a_i,b_i] является интервалом неопределенности, полученным на i-той итерации. Рассмотрим две точки λ_i и μ_i из интервала [a_i,b_i], заданные с помощью соотношений:


где n - заданное число вычислений функции; Fk - последовательность чисел Фибоначчи, заданная с помощью рекуррентной формулы:
F_k+1 = F_k + F_k-1, k = 1,2, … , где F₀ = F₁ = 1
Новый интервал неопределенности (a_i+1,b_i+1) равен (λ_i,b_i), если f(λ_i) > f(μ_i), и равен (a_i, μ_i), если f(λ_i) < f(μ_i). Тогда в первом случае, новый интервал неопределенности имеет длину:

Отсюда следует, что в любом случае на i-той итерации интервал неопределенности сжимается в F_n-i/F_n-i+1 раз. На (i+1)-ой итерации либо λ_i+1 = μ_i, либо μ_i+1 = λ_i. Поэтому на каждом шаге вычисляется только одно новое значение функции. На (n-1)-ой итерации λ_n-1 = μ_n-1,и значение функции не вычисляется.
Если ε есть точность вычисления значения функции, n – максимально возможное число вычислений функции, то конечный интервал неопределенности будет равен:

Решение.
Последовательность чисел Фибоначчи имеет вид: 1,1,2,3,5,8,13,21,34,55,89,144,
Итерация 1.
Вычислим точки


f(λ₁) = 3.4371; f(μ₁) = 1.3135
Так как f(λ₁) > f(μ₁), то сокращаем интервал неопределенности и принимаем на второй итерации:
a₂ = λ₁ = 1.1460674157303; b₂ = b₁ = 3
Итерация 2.
Вычислим точки


f(λ₂) = 1.3135; f(μ₂) = 0.5011
Так как f(λ₂) > f(μ₂), то сокращаем интервал неопределенности и принимаем на 3-й итерации:
a₃ = λ₂ = 1.8539325842697; b₃ = b₂ = 3
Итерация 3.
Вычислим точки


f(λ₃) = 0.5011; f(μ₃) = 0.192
Так как f(λ₃) > f(μ₃), то сокращаем интервал неопределенности и принимаем на 4-й итерации:
a₄ = λ₃ = 2.2921348314607; b₄ = b₃ = 3
Итерация 4.
Вычислим точки


f(λ₄) = 0.192; f(μ₄) = 0.07272
Так как f(λ₄) > f(μ₄), то сокращаем интервал неопределенности и принимаем на 5-й итерации:
a₅ = λ₄ = 2.561797752809; b₅ = b₄ = 3
Все вычисления сведены в таблицу. Вычисления продолжаются, пока не найдены 10 новых точек.

N	a	b	b-a	a+i*c	a+k*c	f(l)	f(m)
1	0	3	3	1.1461	1.8539	3.4371	1.3135
2	1.1461	3	1.8539	1.8539	2.2921	1.3135	0.5011
3	1.8539	3	1.1461	2.2921	2.5618	0.5011	0.192
4	2.2921	3	0.7079	2.5618	2.7303	0.192	0.07272
5	2.5618	3	0.4382	2.7303	2.8315	0.07272	0.02841
6	2.7303	3	0.2697	2.8315	2.8989	0.02841	0.01023
7	2.8315	3	0.1685	2.8989	2.9326	0.01023	0.00454
8	2.8989	3	0.1011	2.9326	2.9663	0.00454	0.00114

Вычисляем точку минимума функции

f(x_min) = 0.00114
Ответ: x = 2.9663; F(x) = 0.00114
Количество итераций, N = 8

1. 
   program fibonacci;
   
2. 
   uses crt;
   
3. 
   const n_m=40;
   
4. 
   type mas=array[1..n_m] of integer;
   
5. 
   type funo=function (x:real):real;
   
6. 
   var
   
7. 
     a,b,e:real;
   
8. 
     nom,n:integer;
   
9. 
     s:mas;
   
10. 
    procedure VvodIsxD_FC( var f:mas; var n:integer; var a,b,e:real);
    
11. 
    var i:integer;
    
12. 
    begin
    
13. 
      writeln('Ввод исходных данных для метода Фибоначчи');
    
14. 
      write('Задайте N (количество разбиений):   ');
    
15. 
      readln(n);
    
16. 
      writeln('Количество разбиений N = ',n);
    
17. 
      f[1]:=1;
    
18. 
      f[2]:=2;
    
19. 
      for i:=3 to n do
    
20. 
      f[i]:=f[i-1]+f[i-2];
    
21. 
      write('Задайте EPSILON (точность) : ');
    
22. 
      readln(e);
    
23. 
      writeln('Задайте интервал (a,b)');
    
24. 
      readln(a,b);
    
25. 
      writeln(a:12:8,',   b = ',b:12:8);
    
26. 
    end;
    
27. 
    procedure Fibonach(z:funo; f:mas; n:integer; a,b,e:real);
    
28. 
    var
    
29. 
      k,i,p:integer;
    
30. 
      f2,f4,x1,x2,x3,x4:real;
    
31. 
    begin
    
32. 
      writeln;
    
33. 
      writeln('Нахождение минимума по методу Фибоначчи');
    
34. 
      x1:=a;
    
35. 
      x2:=a+((b-a)*f[n-1]+e)/f[n];
    
36. 
      x3:=b;
    
37. 
      f2:=z(x2);
    
38. 
      writeln('      Текущий интервал');
    
39. 
      k:=1;
    
40. 
      writeln(x1:12:8,'  ',x3:12:8);
    
41. 
      repeat
    
42. 
      x4:=x1-x2+x3;
    
43. 
      f4:=z(x4);
    
44. 
      if f4>f2 then
    
45. 
        begin
    
46. 
          if x2
47. 
            begin
    
48. 
              x3:=x4;
    
49. 
              writeln(x1:12:8,'  ',x3:12:8);
    
50. 
            end
    
51. 
          else
    
52. 
            begin
    
53. 
              x1:=x4;
    
54. 
              writeln(x1:12:8,'  ',x3:12:8);
    
55. 
            end;
    
56. 
        end
    
57. 
      else
    
58. 
        begin
    
59. 
          if x2
60. 
            begin
    
61. 
              x1:=x2;
    
62. 
              x2:=x4;
    
63. 
              f2:=f4;
    
64. 
              writeln(x1:12:8,'  ',x3:12:8);
    
65. 
            end
    
66. 
          else
    
67. 
            begin
    
68. 
              x3:=x2;
    
69. 
              x2:=x4;
    
70. 
              f2:=f4;
    
71. 
              writeln(x1:12:8,'  ',x3:12:8);
    
72. 
            end
    
73. 
        end;
    
74. 
        k:=k+1;
    
75. 
      until k>n;
    
76. 
      writeln;
    
77. 
      writeln('Минимум найден по методу Фибоначчи');
    
78. 
      write('Конечный интервал [');
    
79. 
      writeln(x1:12:8,',',x3:12:8,' ]');
    
80. 
      writeln('Значение функции F = ',f2:15:12);
    
81. 
      end;
    
82. 
    function q(x:real):real;
    
83. 
      begin
    
84. 
        q:=x*x*x*x-14*x*x*x+60*x*x-70*x;
    
85. 
      end;
    
86. 
    begin
    
87. 
        writeln('Нахождение оптимума по методу  Фибоначчи');
    
88. 
        VvodIsxD_FC(s,n,a,b,e);
    
89. 
        Fibonach(q,s,n,a,b,e);
    
90. 
     
    
91. 
    end.