Вычислительная математика 
 

  назад | оглавление

 

Глава 9. Одномерная оптимизация

1. Постановка задачи

Требуется найти наибольшее (или наименьшее) значение функции , заданной на множестве 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) может оказаться весьма трудоемким, то желательно сократить количество таких вычислений. Одним из наиболее эффективных методов, в котором при ограниченном количестве вычислений достигается наилучшая точность, является метод золотого сечения.


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

Метод состоит в построении последовательности отрезков [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)

Итак, алгоритм метода золотого сечения для поиска минимального значения функции можно описать следующим образом:

  1. Находим точки золотого сечения из (2) для интервала неопределенности [a,b]:
  2. Находим значения функции в точках y и z: .
  3. Если , то новый интервал неопределенности [a,z], , вычисляем .
  4. Если , то новый интервал неопределенности [y,b], и вычисляем .
  5. Вычисления прекращаются, когда . Тогда . В противном случае переходим на п.3.

Рекомендуемая литература:

  1. Волков Е.А. Численные методы. М., Наука, 1987.
  2. Демидович Б.П., Марон И.А. Основы вычислительной математики. М., Наука, 1970.
  3. Турчак Л.И. Основы численных методов. М., Наука, 1987.

назад | оглавление