Метод деления отрезка пополам (Дихотомии)

Метод прямого поиска.Суть метода состоит в последовательном делении отрезков пополам, пока не будет найден минимум функции и не достигнута требуемая точность.

Пошаговое описание алгоритма:

1) Определить x₁ иx₂ по формулам:

, , где - малое число.

И вычислить f(x₁), f(x₂).

2) Сравнить f(x₁) и f(x₂). Если f(x₁) f(x₂), то перейти к отрезку [a; x₂], положив b = x₂, иначе – к отрезку [x₁; b], положив a = x₁.

3) Найти десятичную точность Если > , то перейти к следующей итерации, вернувшись к шагу 1. Если < , то завершить поиск минимума x*, перейти к шагу 4.

4) Положить

Плюсы метода: Простота, высокая точность, меньше количества вычислений.

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

Уменьшение итерации достигается путем деления «Золотого сечения».

5) Метод «Золотого сечения»

Пусть задана функцияf(x). Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска, рассматриваемый отрезок делится в пропорции Золотого сечения в обоих направлениях, то есть выбираются точки x1 и x2 такие что:

где - пропорция Золотого сечения.

Таким образом расположение пробных точек вычисляется как:

Пошаговое описание алгоритма:

1) Найти x1 и x2, по формулам:

.

Вычислить f(x₁) и f(x₂). Положить , .

2) Проверка на окончание поиска: если > , то перейти к шагу 3, иначе – к шагу 4.

3) Переход к новому отрезку и новым пробным точкам. Если f(x₁)<f(x₂), то положить b = x₂, x­₂ = x₁, f(x₁) = f(x₂), x₁ = b- (b - a) и вычислить f(x₁), иначе - a = x₁, x­₁ = x₂, f(x₁) = f(x₂), x₂ = b+ (b - a) и вычислить f(x₂). Положить и перейти к шагу 2.

4) Окончание поиска: положить

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

Минусы: примерим для одноэкстримальных функций.