Методы поиска точек экстремума функции на отрезке

Пусть дана функция f (x), для которой на заданном отрезке [a; b] нужно найти максимальное значение или минимальное значение и установить, в какой точке x* это экстремальное значение достигается. Так как задача нахождения максимума функции f (x), эквивалентна задаче нахождения минимума функции f _(x) = – f (x), то можно всюду далее предполагать, что решается задача поиска минимума.

Метод простого перебора

Будем предполагать, что искомый минимум является строгим, то есть f (x) > f (x*) при всех x ≠ x* , x [a; b], и других точек локального минимума на отрезке нет. Предположим также, что точка минимума x* – внутренняя точка отрезка. Зададимся точностью , с которой будем приближённо отыскивать x* . Приближённое значение точки минимума обозначим , то есть  – это такое число, что

Простейший способ обнаружить точку x* с точностью  – это перебирать точки xi отрезка [a; b] с шагом h ≤ начиная с x0 = a, до тех пор, пока не будет выполнено условие

f (x‍i+1) > f (x‍i), то есть пока функция не начнёт возрастать после точки минимума. При этом точка x* может оказаться либо на отрезке [xi-1; x‍i], либо на отрезке [xi; x‍i+1] (cм. следующий чертёж):

Если теперь положить , то в любом из двух случаев будет выполнено неравенство , то есть точка минимума будет найдена с нужной нам точностью. За приближённое значение нужно теперь взять. Дополнительного вычисления функции при этом не потребуется, поскольку значение f (x‍i ) уже было найдено ранее.

Если не предполагать, что локальный минимум на отрезке [a; b] только один и, что точка минимума – внутренняя точка отрезка, то придётся изменить метод так: вычислять значения f (x‍i ) до тех пор, пока точка x‍i не достигнет правого конца отрезка – точки b на каждом шаге сравнивать текущее значение f (x‍i ) с минимальным из предыдущих значений m заменяя это минимальное значение m на f (x‍i ) при m > f (x‍i ). Наконец, вычислить

НЕ нашли? Не то? Что вы ищете?

f (b ) (если точка b не совпадает с последней из точек x‍i) и также сравнить с минимальным из предыдущих значений. После этой процедуры m будет приближённо равно , а та точка, в которой получено значение функции, равное m – приближённым значением точки

минимума x*.

Общая схема методов поиска минимума на отрезке

Теперь мы перейдем к рассмотрению других методов, более общих в том смысле, что они не требуют условия непрерывности или дифференцируемости. Они просто предполагают, что по крайней мере в некотором интервале функция f(x) обладает свойством унимодальности. Функция называется унимодальной на отрезке [a0, b0], если она монотонно убывает от a0 до некоторого x* из [a0, b0], а затем возрастает до b0. В этом случае x* соответствует локальному минимуму функции, и он единственный.

Пусть функция f(x) унимодальна на отрезке [a0, b0]. Необходимо найти точку минимума функции на этом отрезке с заданной точностью ε. Все методы одномерного поиска базируются на последовательном уменьшении интервала, содержащего точку минимума. Возьмем внутри отрезка [a0, b0] две точки x1 и x2: a0 < x1 < x2 < b0, и вычислим значения функции в этих точках. Из свойства унимодальности функции можно сделать вывод о том, что минимум расположен либо на отрезке [a0, x2], либо на отрезке [x1, b0]. Действительно, если f (x1) < f (x2), то минимум не может находиться на отрезке [x2, b0], если f (x1) > f (x2), минимум не может находиться на отрезке [a0, x1]. Если же f (x1) = f (x2), то минимум находится на интервале [x1, x2].

Алгоритм заканчивается, когда длина интервала, содержащего минимум, становится меньше ε.

Метод золотого сечения

Точки x1, x2 находятся симметрично относительно середины отрезка [a0, b0] и делят его в пропорции золотого сечения, когда длина всего отрезка относится к длине большей его части также, как длина большей части относится к длине меньшей части:

и .

Отсюда:

За одну итерацию интервал неопределенности уменьшается в раз, но на следующей итерации мы будем вычислять функцию только один раз, так как по свойству золотого сечения и . Для достижения точности ε потребуется итераций.

Неточное задание величины на ЭВМ уже при достаточно небольшом количестве итераций может приводить к погрешностям и потере точки минимума, так как она выпадает из интервала неопределенности. Поэтому, вообще говоря, при реализации алгоритма возможность такой ситуации должна быть предусмотрена.