Метод половинного деления.

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

Алгоритм метода деления интервала пополам включает следующие шаги поисковой процедуры:

1 Пусть - отрезок поиска экстремума функции . Вычислить , и значение функции .

2 Положить и . Вычислить значения функции и .

3 Если , исключить интервал , положив . Положить и перейти к п.5. Если , то перейти к п.4.

4 Если , исключить интервал , положив и перейти к п.5. Если , исключить интервалы и . Положить и . Перейти к п.5.

5 Вычислить . Если , то закончить поиск, а в противном случае перейти к п.2.

Пример 3. Найти минимум на отрезке [60; 150]. Пусть а =60, b=150, L=90, x_m=(150+60)/2 =105.

Итерация 1.

Вычисляем

x₁ = 60 + (90/4) = 82.5,

x₂ = 150 - (90/4) = 127.5,

f(82.5) = 306.25 > f(105) = 25,

f(127.5) = 75.27 > f(105).

Исключаем интервалы (60;82.5) и (127.5;150).

Длина отрезка поиска будет L₂ = 45.

Итерация 2.

Положим а = 82.5, b = 127.5, x_m = 105.

Вычисляем

x₁ = 82.5 + (45/4) = 93.75,

x₂ = 127.5 - (45/4) = 116.25,

f(93.75) = 39.06 > f(105) = 25,

f(116.25) = 264.06 > f(105).

Получаем отрезок [93.75; 116.25] и его длина L₃ =22.5. Таким образом, после двух итераций длина исходного отрезка L₁ = 90, уменьшилась до L₃ =22.5. Приближенное значение точки минимума x_m =105, f(x_m) = 25.

Предлагаю ознакомиться с аналогичными статьями:

образование

• Мой тест по сетям
• Цифровая обработка сигналлов
• Интерфейсы. Общие положения.
• Активность
• Основная семиотическая конструкция: треугольник Фреге
• Семиотика и знания

методичка

• Построение изображений заданных решений линейной системы по минимальным многочленам векторов пространства состояний
• Моделирование процессов управления ЛА. Управление самолетом «Боинг - 747» при посадке.
• ПЕРЕПЛЕТ ЖУРНАЛОВ
• КАК ПРОДЛИТЬ КНИЖКЕ ЖИЗНЬ
• Договоренности и динамика знаков
• Активность

Оптимизация

• Безусловная минимизация функций численными методами второго порядка.
• Метод сопряженных градиентов Флетчера-Ривса.
• Метод наискорейшего спуска.
• Градиентные методы.
• Формулировка задачи многомерной оптимизации.
• Метод поиска минимума функции одной переменной с использованием кубичной аппроксимации