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

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

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

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

Простейший способ обнаружить точку x^* с точностью — это перебирать точки x_i отрезка [a; b] с шагом h? начиная с x₀ = a_, до тех пор, пока не будет выполнено условие f (x_i+1) > f (x_i), то есть пока функция не начнёт возрастать после точки минимума. При этом точка x^* может оказаться либо на отрезке [x_i-1; x_i], либо на отрезке [x_i; 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^*.