Рассмотрим задачу поиска минимума функции f (х), определенной на отрезке [а; b], способами, не связанными с решением уравнения f (х) = 0. При этом достаточно ограничиться поисками минимумов лишь во внутренних точках отрезка, поскольку вычисление значений функции на его концах задача тривиальная.
Все, сказанное об отделении корней уравнений, можно повторить об отделении минимумов. Эта задача не имеет формализованных, однозначно ведущих к успеху, решений. Мы сосредоточимся на поиске минимума, считая, что на данном отрезке он существует и единственен. Иначе говоря, будем считать, что функция f (х) является на отрезке [а; b] унимодальной, т.е. монотонно убывающей слева от точки минимума и монотонно возрастающей справа от нее.
Приведем также более строгое описание унимодальности. Непрерывная функция у=f(х) является унимодальной на отрезке [а; b], если:
Рис. К определению унимодальности функции у=f(х)
1) точка ξ локального минимума функции принадлежит отрезку [а; b];
2)для любых двух точек отрезка х1 и х2, взятых по одну сторону от точки минимума, точке х1, более близкой к точке минимума, всегда соответствует меньшее значение функции, т.е. неравенство f (х1) < f (х2) справедливо как при ξ <х1 <х2 (рис. 7.2, а),так и при х2<х1 < ξ (рис. 7.2, б).
Очевидно, что если бы шла речь о максимуме функции, то унимодальность определялась бы обратными утверждениями.
Метод дихотомии столь прост и очевиден по замыслу, что легко переносится на задачу уточнения положения точки минимума унимодальной функции.
На рис. проиллюстрирован первый шаг указанного метода. Искомый минимум находится в точке ξ. Разделим отрезок [а; b] пополам точкой с=(а + b)/2. Если (как это имеет место на рис. 7.3) точка минимума оказалось левее точки с, то следующий отрезок, подлежащий делению пополам, есть [а; с], иначе — [с; b].
Поскольку реально в ходе вычислений мы не располагаем значением ξ, то возникает вопрос, как определять на каждом шаге, левый или правый отрезок подлежит делению. При решении уравнений методом половинного деления этот выбор был очевиден — по сопоставлению знаков f (а), f(с) и f (b). В данном случае ни знаки, ни сравнения значений функции ни о чем не говорят и приходится использовать слегка усложненный прием.
Пусть точность, с которой мы хотим оценить значение с, есть ε. Будем вычислять не одно значение f (с), а два: f (с- ε/2) и f (с + ε /2). Учитывая предполагаемую унимодальность функции f(х) , ясно, что при f (с- ε/2) < f (с + ε /2) следующему делению пополам подле жит отрезок [а; с] (или, что практически то же самое, [а; с — ε /2]). Если же f (с — ε /2)> f (с + ε /2), то делению подлежит отрезок [с; b]. Итерационный вычислительный процесс продлится до тех пор, пока длина очередного отрезка не станет меньше ε. Наконец, нельзя исключить ситуацию, когда на очередном шаге f (с — ε /2)= f (с + ε /2),т.е. искомая точка, в которой функция f(х) имеет минимум, оказалась между с — ε /2 и с + ε /2; в этом случае результат решения задачи (с заданной точностью) есть с.
Оставить комментарий