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

• Ввод данных
• Инструкция
• Оформление Word

F(x) =

Искать в интервале отдо Точность δ

Количество вычислений функции, n =

Метод поиска Метод золотого сеченияМетод ФибоначчиМетод Свенна

...load... Действия

• Загрузить предыдущие

Видеоинструкция

Правила ввода функции

Примеры
≡ x^2/(1+x)
cos2(2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)

Скачать пример оформления

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

где n - заданное число вычислений функции; F_k - последовательность чисел Фибоначчи, заданная с помощью рекуррентной формулы
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). Тогда в первом случае, новый интервал неопределенности имеет длину

Пример. Минимизировать функцию f(x) на отрезке [0;8]. Известно, что можно выполнить n=6 вычислений функции.
Найдем минимум функции:
4.2•x²+23/x = 0
Используем для этого Метод Фибоначчи.
Важнейшая особенность этого метода состоит в том, что он позволяет для заранее заданного числа вычислений функции построить оптимальную процедуру поиска минимума унимодальной функции.
Предположим, что заданный начальный интервал неопределенности [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
Итерация 1.
Вычислим точки