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

Алгоритм поиска минимума методом дихотомии.

Условия окончания вычислений.

Активные методы поиска минимума

Каждая последующая точка выбирается с учетом полученных результатов.

2.4.1. Метод дихотомии (половинного деления)

Общее количество вычислений f(x) четное.

На каждом шаге (каждой итерации) производится пара вычислений в точках, отстоящих на расстоянии по обе стороны от середины текущего отрезка локализации.

Если ,

Если вычислений (2.6)

Для сокращения отрезка в 100раз в пассивном методе необходимо 198 вычислений, в методе дихотомии – 14.

1)Выполнение заданного количества вычислений N.

2)Уменьшение отрезка локализации в раз, где .

Для активного метода важно количество итераций. Номер итерации указывается надстрочным индексом в скобках.

Если проведено i вычислений:

1) Полагаем

2) На j-той итерации вычисляются

3)Если , то .

Если , то .

4)Проверяем условие окончания вычислений или .

Если условие выполняется, то вычисления завершаются. Если нет, то полагаеми переход к пункту 2.

Ответ: в итоге получаем отрезок оптимизации

Замечание: оценкой точки минимума является та точка итогового отрезка локализации, для которой значение отрезка f(x) минимально.

Данный метод является наилучшим, всмысле длины отрезка локализации.

На первом шаге проверяется 2 вычисления в точке расположенных симметрично, относительно середины отрезка .

По результатам вычислений, одна из частей отрезка (либо , либо ) отбрасывается,. При этом одна из точек уже проведенных вычислений остается внутри отрезка

На каждом последующем шаге (последующей итерации) точка очередного вычисления выбирается симметрично оставшейся точки.

N – вычислений

N-1 – итераций

Количество вычислений N в методе Фибоначчи задается всегда.

Проблема выбора первой точки.

Для этого надо посмотреть как завершить метод наиболее эффективно.

Предположим, что нашли отрезок. Проверим N-1 вычислений.

Максимальное уменьшение длины отрезка на последнем шаге

(2.7)

(2.8)

Комбинируя (2.7) и (2.8) в результате получим:

- числа Фибоначчи

Используя числа Фибоначчи приведем формулу к виду:

Алгоритм поиска минимума методом Фибоначчи.

1) Полагаем

2) На j-той итерации вычисляются

3)Если , то .

Если , то .

4)Проверяем условие окончания вычислений .

Если условие выполняется, то вычисления завершаются. Если нет, то полагаеми переход к пункту 2.

Замечание: в реальности точки и вычисляются только один раз (на первом шаге), на всех последующих шагах будет вычисляться только одна (либо , либо ).

Ответом является длина отрезка локализации.

.