Вычислительная математика
|
Глава 9. Одномерная оптимизация
Требуется найти наибольшее (или наименьшее) значение функции , заданной на множестве s
, и определить значение xÎ
s
, при котором целевая функция принимает это экстремальное значение. Если в качестве s
взять отрезок [a,b] и функция f(x) непрерывна, то по теореме Вейерштрасса функция имеет на [a,b] наибольшее и наименьшее значения. В этом случае задача оптимизации имеет решение (возможно неединственное).
Если функция f(x) дифференцируема на [a,b] и может быть найдено явное выражение для . Тогда f(x) достигает своего наибольшего и наименьшего значения либо в граничных точках x = a, x = b, либо в одной из критических точек, где
. Следовательно, для определения наибольшего или наименьшего значения такой функции нужно вычислить ее значения во всех критических точках, в граничных точках и выбрать из полученных значений наибольшее и наименьшее. При нахождении критических точек возможно применение численных методов решения уравнения.
В ряде случаев целевая функция дифференцируема не во всех точках, либо вычисление ее производной в явном виде невозможно или требует больших затрат. В этих случаях для нахождения экстремума используются специальные методы поиска, состоящие в вычислениях f(x) в некоторых точках и выбора среди них наибольшего или наименьшего значения. Для успешного применения этих методов обычно необходимо, чтобы функция f(x) была унимодальной, т.е. имела на [a,b] только один минимум или максимум.
Простейшим методом поиска экстремума является метод перебора. Будем для определенности говорить о нахождении минимума. Отрезок, на котором находится минимум называется интервалом неопределенности. Разобьем отрезок [a,b] на n равных частей [xi,xi+1] (i = 1, 2, ¼
, n) длины . Вычислив значение f(x) в узлах xi, найдем среди них наименьшее
. Ясно, что минимум находится на отрезке [xk-1,xk+1]. Если выполняется, что
, где e
– заданная точность, то за точку минимума принимаем xk. Иначе разбиваем отрезок [xk-1,xk+1] на n равных частей и повторяем вычисления.
Поскольку вычисление значений f(x) может оказаться весьма трудоемким, то желательно сократить количество таких вычислений. Одним из наиболее эффективных методов, в котором при ограниченном количестве вычислений достигается наилучшая точность, является метод золотого сечения.
Метод состоит в построении последовательности отрезков [a0,b0], [a1,b1], ¼ (a = a0, b = b0), стягивающихся к точке минимума f(x), причем на каждом шаге вычисление значения f(x) производится только один раз. На первом шаге внутри отрезка [a0,b0] выбираем две внутренние точки x1 и x2 и вычисляем значения f(x1) и f(x2). Пусть, например, f(x1) < f(x2). Тогда, очевидно минимум расположен на отрезке [a0,x1] и этот отрезок можно взять в качестве нового интервала неопределенности. Второй шаг метода проводим на отрезке [a1,b1] (a1 = a0, b1 = x1). Теперь опять нужно выбрать две внутренние точки, но одна из них (x1) осталась с предыдущего шага, поэтому достаточно выбрать лишь одну точку x2, вычислить f(x2) и произвести сравнение и т.д. до тех пор, пока не будут достигнута заданная точность.
Рассмотрим способ размещения внутренних точек на каждом отрезке [ak,bk]. Пусть длина интервала неопределенности равна l, а точка деления делит его на части l1, l2: l1 > l2, l1 + l2 = l. Золотое сечение интервала неопределенности выбирается из соотношения:
.               (1)
Преобразуем (1) и найдем отношение .
. Поскольку нас интересует только положительное значение, то
. Откуда
.               (2)
Итак, алгоритм метода золотого сечения для поиска минимального значения функции можно описать следующим образом:
Рекомендуемая литература: