Метод Фибоначчи. 
Методы оптимизации в АСКТП

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

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

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

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

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

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

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

Опишем 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-й шаг.

;

.