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

В данной работе мы рассмотрим один из методов одномерной оптимизации, а именно — метод Фибоначчи.

При построении процесса оптимизации стараются сократить объем вычислений и время поиска.

Этого достигают обычно путем сокращения количества вычислений значений целевой функции f (x). Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f (x) достигается наилучшая точность, является метод Фибоначчи.

Описание метода для поиска минимума

Последовательность чисел Фибоначчи определяется соотношением:

	(8).

и имеет вид:

i.

Fi

и т.д.

Подобно методу золотого сечения процедура поиска с использованием чисел Фибоначчи требует два вычисления функции на первом шаге, а на каждом последующем — только по одному. Однако, в отличие от метода золотого сечения, в этой процедуре общее число S вычисления функции должно быть выбрано заранее. Кроме того, сокращение интервала неопределенности не остается постоянным, а меняется от шага к шагу: на k-ом шаге длина интервала неопределенности сжимается с коэффициентом Первые два вычисления проводятся в точках:

расположенных симметрично относительно середины отрезка [a, b]. Если f (x₁)<f (x₂), то новым отрезком локализации минимума является [a, x₂], в случае f (x₁)?f (x₂)-[x₁, b]. Каждая следующая точка выбирается симметрично относительно середины полученного отрезка к лежащей внутри этого отрезка точке уже проведенного вычисления (x₁ или x₂). При этом любая внутренняя точка делит отрезок локализации в отношении, двух последовательных чисел Фибоначчи. алгоритм интерфейс программа фибоначчи.

Взаимное расположение точек первых трех вычислений в случае f (x₁)<f (x₂) показано на рис. 7.

После (S-1)-го шага точка проведенного вычисления оказывается в середине отрезка локализации. Точка последнего, S-го, шага выбирается на расстоянии д от середины этого отрезка, где д - заранее фиксированное малое положительное число (константа различимости).

После S вычислений функции длина отрезка локализации составляет (с точностью до д):

	(9).

Сравнение (9) и (7) показывает, что при одном и том же S метод Фибоначчи дает меньший интервал неопределенности, чем метод золотого сечения, т. е. является более эффективным. Однако для достаточно больших S значение стремится к (0,618)^S-1, так что эти методы становятся почти идентичными. В том случае; когда при использовании метода Фибоначчи задан. конечный интервал неопределенности е, число S можно определить из условия:

	(10).

Алгоритм минимизации функции f (x) с использование, чисел Фибоначчи.

1. По заданной точности рассчитывается вспомогательное число.

• 2. Для полученного значения N находится такое число Фибоначчи F_S, для которого выполняется неравенство:
• 3.
• 4. По формуле (9) определяется длина конечного интервала неопределенности l.
• 5. Вычисляются значения x₁=a+l•F_S-2, x₂=b-l•F_S-2.
• 6. В зависимости от соотношения f (x₁) и f (x₂) выбирается новый интервал локализации минимума.
• 7. Внутри полученного интервала находится новая точка (x₁ или x₂), симметричная к уже имеющейся точке и отстоящая от конца интервала на величину l•F_S-1-k , где k — номер шага. В этой точке рассчитывается значение f (x). Затем вычисления повторяются, начиная с пункта 5, до тех пор, пока k не станет равно S-1. Тогда переходят к пункту 7.
• 8. Полагают x₂=x₁+д, находят f (x₂). Если f (x₂)>f (x₁)то минимум реализуется на интервале (a, x₁), в противном случае — на интервале (x₁ , b).