Метод почти половинного деления находение корней


Пусть $ 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^*$ найдено верно.     

Главы учебника "Курс лекций высшей математики"

 

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