Назад Метод простого перебора     
Наверх: Приближённое нахождение корней уравнений
Вперед: Метод золотого сечения и метод Фибоначчи

Untitled Document

Ядерное оружие | Графика | Математика | Физика | Заказать диплом | Информатика | ТКМ | Электротехника | Атомная энергетика | Лекции

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

Пусть $ f(x)$ -- непрерывная функция, точку минимума которой на отрезке $ [a;b]$ мы хотим найти с точностью $ {\varepsilon}$. В этом методе мы предполагаем, что $ x^*\in(a;b)$ -- единственная точка локального минимума функции $ f(x)$ на отрезке $ [a;b]$. Мы будем последовательно сужать отрезок $ [a;b]=[a_0;b_0]$ так, чтобы точка минимума $ x^*$ всегда оставалась на выбираемой части отрезка $ I_i=[a_i;b_i]$, и продолжим процедуру до тех пор, пока длина $ {\Delta}_i=b_i-a_i$ оставшейся части отрезка не станет меньше $ 2{\varepsilon}$. После этого достаточно будет взять $ \wt x=\dfrac{a_i+b_i}{2}$, и очевидно, что тогда будет $ \vert\wt x-x^*\vert<{\varepsilon}$, то есть точка $ x^*$ будет найдена с требуемой точностью.

Опишем теперь процесс выбора той части $ I_{i+1}$ отрезка $ I_i=[a_i;b_i]$, на которой находится точка минимума $ x^*$. Выбор конечных точек $ a_{i+1}$ и $ b_{i+1}$ будет использовать значения функции в концах предыдущего отрезка, то есть $ f(a_i)$ и $ f(b_i)$.

Перед началом вычисления выберем число $ {\delta}<\dfrac{{\varepsilon}}{2}$ и положим $ I_0=[a_0;b_0]=[a;b]$. Шаг перехода от $ I_i$ к $ I_{i+1}$ состоит в следующем. Вычислим два значения функции, в точках $ l_i=\dfrac{a_i+b_i}{2}-{\delta}$ и $ r_i=\dfrac{a_i+b_i}{2}+{\delta}$. Эти две точки симметричны относительно середины отрезка, точки $ \dfrac{a_i+b_i}{2}$. Сравним теперь значения $ f(l_i)$ и $ f(r_i)$:
если $ f(l_i)\leqslant f(r_i)$, то $ x^*\in[a_i;r_i]$, и надо положить $ I_{i+1}=[a_i;r_i]$, то есть взять $ {a_{i+1}=a_i;b_{i+1}=r_i}$;
если же $ f(l_i)>f(r_i)$, то $ x^*\in[l_i;b_i]$, и надо положить $ I_{i+1}=[l_i;b_i]$, то есть взять $ {a_{i+1}=l_i;b_{i+1}=b_i}$ (см. следующий чертёж).

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


На первых итерациях, когда длины отрезков $ I_i$ остаются много больше малого числа $ {\delta}$, длина $ {\Delta}_{i+1}$ нового отрезка $ I_{i+1}$ меньше длины предыдущего отрезка $ I_i$ почти вдвое:

$\displaystyle {\Delta}_{i+1}=\dfrac{{\Delta}_i}{2}+{\delta}.$

(Отсюда название метода: метод почти половинного деления.) После нескольких итераций длина отрезка $ {\Delta}_i$ начинает уменьшаться не так быстро и приближается к $ 2{\delta}$. Поскольку мы выбирали $ {\delta}$ так, что $ 2{\delta}<{\varepsilon}$, на некотором шаге будет выполнено неравенство $ {\Delta}_i<4{\delta}<2{\varepsilon}$ и, как отмечалось выше, процесс можно будет прервать и взять $ \wt x=\dfrac{a_i+b_i}{2}$.

        Замечание 9.1   Если не предполагается, что на исходном отрезке $ [a;b]$ только одна точка локального минимума, то применение описанного выше алгоритма приводит к нахождению какой-то одной из точек локального минимума, причём не обязательно той, в которой принимается наименьшее на всём отрезке значение. Это общая трудность, присущая методам минимизации. Однако на практике, как правило, в оптимизационных задачах обычно из каких-то соображений (часто лежащих вне математики) известно, что на рассматриваемом отрезке других локальных минимумов нет, то есть функция убывает на $ [a;x^*]$ и возрастает на $ [x^*;b]$; вся проблема только в том, что неизвестно положение точки $ x^*$.

Довольно часто существование и единственность локального минимума на $ [a;b]$ является следствием того, что функция $ f(x)$ строго выпукла на $ [a;b]$. Тогда, действительно, $ f(x)$ не может иметь на интервале $ (a;b)$ более одной точки локального минимума.

Если же для рассматриваемой функции $ f(x)$ такие свойства неизвестны, то остаётся действовать эмпирически: применить метод к отрезку $ [a;b]$ и некоторым его частям вида $ [a';b']$, выбранным наугад. Если каждый раз либо будет получаться то же самое значение $ x^*$ (с выбранной точностью), либо будет оказываться, что $ x^*\notin[a';b']$, а минимум на $ [a';b']$ больше, чем значение в точке $ x^*$, то значение $ x^*$ найдено верно.     

Назад Метод простого перебора     
Наверх: Приближённое нахождение корней уравнений
Вперед: Метод золотого сечения и метод Фибоначчи


Физика лабы
Элементарная математика Кратные интегралы Математический анализ
Векторный анализ Аналитическая геометрия Пределы функции Изучение функции Конспекты по математике Комплексные числа Дифференциальные уравнения Определенные интегралы Лекции по высшей математике Исследование функций Вычисление объема с помощью интегралов Алгеброические структуры