Решение задач методом Фибоначчи

В силу того, что в асимптотике.

метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции. Алгоритм :

Шаг 1. Задаются начальные границы отрезка и число итераций, рассчитывают начальные точки деления:

и значения в них целевой функции:

.

• 1. Шаг 2. .
• · если, то

.

Иначе .

• 2. Шаг 3.
• · Если, то и останов.
• · Иначе возврат к шагу 2.

Пример решения задачи методом Фибоначчи.

Найти min функции.

F (x) = 28x² -30x — 42.

на отрезке с ограничением [ 0; 50 ].

Решение :

F_n+2= F₁₀ =55.

F_n+1=F₉=34.

F_n=F₈=21.

F_n-1=F₇=13.

F_n-2=F₆=8.

F_n-3=F₅=5.

F_n-4=F₄=3.

F_n-5=F₃=2.

F_n-6=F₂=1.

F_n-7=F₁=1.

Итерация 1.

Х¹ ₁=a + F_n/F_n+2 =a+ F₈/F₁₀(b-a) = 21/55 * 50 =19,1.

X¹₂ =a+ Fn+1/Fn+2(b-a) =a+ F9/F10(b-a) = 34/35 * 50= 30,9.

F (X¹₁) = 28*(19,1)² -30*19,1−42 =10 214,7- 573−42 = 9599,7.

F (X¹₂) = 28(30,9)² — 30* 30,9 -42 = 26 734,6 — 927- 42 = 25 765,6.

Т.к F (X¹₁) при 1 итерации меньше, чем F (X¹₂) при 1 итерации, то получаем отрезок ограничений [0; 30,9].

Итерация 2.

X²₁= a+ Fn-1/Fn+1(b-a) = a+ F7/F9(b-a)= 13/34 * 30,9= 11,8.

X²₂= a+ Fn/Fn+1(b-a) = a+ F8/F9(b-a) = 21/34 * 30,9 = 19,1.

F (X₁²)= 28* (11,8)² — 30*11,8−42 =3898,7−354−42= 3502,7.

F (X²₂) = 28 * (19,1)²-30(19,1)-42 = 10 214,7 — 573 -42 =9599,7.

Т.к. F (X₁²) при 2 итерации меньше, чем F (X²₂) при 2 итерации, то получаем отрезок ограничений [0; 19,1 ].

Итерация 3.

X³₁=a+ Fn-2/Fn (b-a) = a+ F6/F8(b-a) = 8/21 * 19,1= 7,3.

X³₂=a+ Fn-1/Fn (b-a)= a+ F7/F8(b-a)= 13/21 * 19,1= 11,8.

F (X³₁) = 28 *(7,3)²— 30* 7,3−42 = 1492,1- 219−42= 1231,1.

F (X³₂) = 28* (11,8)² — 30*11,8−42 =3898,7−354−42= 3502,7.

Т.к. F (X³₁) при 3 итерации меньше, чем F (X³₂) при 3 итерации, следовательно получаем отрезок ограничений [0; 11, 8 ].

Итерация 4.

X⁴₁ = a+ Fn-3/Fn-1(b-a) = a+F5/F7(b-a)= 5/13 * 11,8= 4,5.

X⁴₂=a+ Fn-2/Fn-1(b-a)=a+ F6/F7(b-a)= 8/13 *11,8=7,3.

F (X⁴₁)=28 *(4,5)²-30*4,5−42=567−135−42=390.

F (X⁴₂)= 28 *(7,3)²— 30* 7,3−42 = 1492,1- 219−42= 1231,1.

Т.к F (X⁴₁) при итерации 4 меньше, чем F (X⁴₂) при 4 итерации, следовательно получаем отрезок ограничений [0; 7,3].

Итерация 5.

X⁵₁=a+ Fn-4/Fn-2(b-a)= a+F4/F6(b-a)= 3/8 *7,3= 2,7.

X⁵₂=a+Fn-3/Fn-2(b-a) = a+ F5/F6(b-a) = 5/8 * 7,3=4,5.

F (X⁵₁)= 28*(2,7)²-30*2,7−42= 204,1−81−42=81,1.

F (X⁵₂)= 28 *(4,5)²-30*4,5−42=567−135−42=390.

Т.к. F (X⁵₁) при итерации 5 меньше, чем F (X⁵₂) при 5 итерации, следовательно получаем отрезок ограничений [0; 4,5].

Итерация 6.

X⁶₁=a+Fn-5/Fn-3(b-a)=a+F3/F5(b-a)= 2/5*4,5=1,8.

X⁶₂=a+Fn-4/Fn-3(b-a)= a+F4/F5(b-a)= 3/5*4,5=2,7.

F (X⁶₁)=28*(1,8)²-30*1,8−42=90,7−54−42=-5,3.

F (X⁶₂)= 28*(2,7)²-30*2,7−42= 204,1−81−42=81,1.

Т.к. F (X⁶₁) при итерации 6 меньше, чем F (X⁶₂) при 6 итерации, следовательно получаем отрезок ограничений [0; 2,7].

Итерация 7.

X⁷₁=a+Fn-6/Fn-4(b-a)=a+F2/F4(b-a)=1/3*2,7=0,9.

X⁷₂=a+Fn-5/Fn-4(b-a)= a+F3/F4(b-a)=2/3*2,7=1,8.

F (X⁷₁)=28*(0,9)²-30*0,9−42= 22,7−27−42= -46,3.

F (X⁷₂)= =28*(1,8)²-30*1,8−42=90,7−54−42=-5,3.

Т.к. F (X⁷₁) при итерации 7 меньше, чем F (X⁷₂) при 7 итерации, следовательно получаем отрезок ограничений [0 ;1,8 ].

Итерация 8.

X⁸₁=a+Fn-7/Fn-5(b-a)=a+ F1/F3(b-a) = Ѕ*1,8=0,9.

X⁸₂= a+Fn-6/Fn-5(b-a)=a+F2/F3(b-a)= Ѕ*1,8=0,9.

F (X⁸₁)= 28*(0,9)²-30*0,9−42= 22,7−27−42= -46,3.

F (X⁸₂)= 28*(0,9)²-30*0,9−42= 22,7−27−42= -46,3.

Ответ: -46,3 — это и есть точка минимума.