Понятие унимодальности.Рассмотрим задачу

Численные методы отыскания экстремумов функции одной переменной.

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

Понятие унимодальности.Рассмотрим задачу

. (1)

Функцию f(x) будем называть унимодальной на отрезке [a,b], если на этом отрезке существует такая точка минимума x^*, что для любых двух точек x₁, x₂ этого отрезка имеют место следующие соотношения:

Другими словами унимодальная функция монотонна на обе стороны от точки минимума x^*. Отсюда следует, что если функция f(x) унимодальна на отрезке [a,b], то минимум этой функции единственен, а локальные максимумы обязательно располагаются на его концах.

Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными.

На рисунке 1 приведены графики непрерывных унимодальных на отрезке [a,b] функций. В случае а) на отрезке [a,b] одна точка минимума, в случае б) – одна точка максимума.

На рисунке 2 изображена неунимодальная на отрезке [a,b] функция. Однако нетрудно видеть, что на отрезках [a,x₁], [x₁,x₂], [x₂,b] она является унимодальной. Нетрудно видеть, что если функция непрерывна на отрезке [a,b] и не является постоянной, то внутри отрезка всегда можно выделить подотрезки, на которых функция будет обладать свойством унимодальности. Процедуру выделения из заданного отрезка подотрезков, на которых функция унимодальна, называют процедурой локализации экстремумов.

а) б)

Рис.1. Унимодальные на отрезке [a,b] функции.

Рис.2. Пример неунимодальной на отрезке [a,b] функции.

Поскольку минимум функции f(x) – это максимум функции –f(x), то задачи отыскания максимума и минимума идентичны. Ниже, для определенности, ограничимся рассмотрением только задачи (1).

2. Методы нулевого порядка. Пусть f(x) – унимодальная на отрезке [a,b] функция, имеющая на нём единственную точку минимума x^*; x₁, x₂ – две точки из (a,b),x₁<x₂ и f(x₁)<f(x₂) (см. рис. 3). Очевидно, поскольку f(x) унимодальна, то отрезок [x₂,b] не может содержать её минимума. Дествительно, давайте допустим, что . Тогда будем иметь: x₁<x₂<x^*, f(x₁)<f(x₂), f(x₂)>f(x^*). Но тогда отрезок [x₁,x^*], содержит точку максимума и эта точка является его внутренней точкой, а тем более внутренней точкой отрезка [a,b]. Выше отмечалось, что унимодальная функция, имеющая единственную точку минимума, не может иметь внутри отрезка [a,b] точки максимума. Полученное противоречие доказывает, что отрезок [x₂,b] не содержит x^* и его можно исключить из рассмотрения. Аналогичным образом, если, f(x₁)>f(x₂), то минимум не содержится в отрезке [a,x₁] и его можно отбросить.

Рис. 4. Анализ унимодальной функции.

Этот факт лежит в основе группы методов нулевого порядка, которые будем называть методами сечения отрезка. Их суть в следующем.

1) на отрезке [a,b] выбираем две точки: x₁ и x₂ – точки сечения отрезка (x₁ < x₂);

2) вычисляем и ;

3) если , то отрезок [a,b] сужаемдо отрезка [a,x₂], т.е. отбрасываем [x₂,b]; если , то переходим к отрезку [x₁,b], т.е. отбрасываем [a,x₁];

4) полученный отрезок принимаем в качестве исходного для следующей итерации и переходим к п.1.

Этот процесс продолжаем до тех пор, пока длина отрезка не будет меньше заданной точности .

Методы сечения отрезка отличаются друг от друга способом выбора точек x₁ и x₂. Рассмотрим 2 из них.

2.1. Метод «золотого» сечения. Пусть [a^k,b^k] – отрезок на k -ой итерации метода ([a¹,b¹]=[a,b]). Точки , вычислим по правилу:

,

где l^k=b^k-a^k – длина отрезка, - коэффициент сечения,

.

Коэффициент сечения подобран специально. Точки сечения располагаются таким образом, что при переходе к новому отрезку [a^k+1,b^k+1] та из точек , , которая остается в новом отрезке, автоматически становится точкой разбиения нового отрезка (см. рис. 5).

Рис. 5. Примерная схема перехода точек сечения от отрезка к отрезку

Поэтому, если, например, , то новый отрезок [a^k+1,b^k+1] и его сечение строятся по правилам:

a^k+1=a^k, b^k+1= ;

, =

В силу этих правил нет необходимости вычислять значение функции в точке - оно было вычислено на предыдущей итерации. Его просто нужно запомнить и сохранить до нужного момента.

Собственно, в этом приеме суть метода «золотого» сечения, его «золото»: на каждой итерации метода (кроме первой) вычисляется только одно новое значение функции. При решении сложных задач, в которых одно вычисление функции занимает несколько минут, а то и часов, общее время вычислений может сократиться до двух раз.

2.2. Метод квадратичной интерполяции. Если отрезок [a,b] небольшой, а функция f(x) достаточно гладкая (например, дважды дифференцируемая), то ее график близок к графику параболы (см. рис. 5). Если y=Ax²+Bx+C – уравнение параболы, то точка ее минимума находится без каких-либо проблем: . Поэтому очевидна идея: вместо исходной функции рассмотреть близкую к ней параболу, а точку её минимума принять в качестве приближенной точки минимума исходной функции.

Известно, что для построения параболы нужно знать 3 точки, через которые она проходит. В качестве этих точек возьмем точки на графике функции f(x), соответствующие концам отрезка, и некоторой внутренней точке с (при отсутствии дополнительной информации в качестве этой точки можно взять середину отрезка: с=(a+b)/2).

Рис.5. График исходной функции (тонкая линия) и аппроксимирующей параболы (жирная линия)

По значениям f(a), f(b) и f(c) точку минимума параболы можно найти по следующей формуле:

(2)

Опишем теперь алгоритм метода сечения отрезка, базирующийся на идее метода квадратичной интерполяции. Допустим, что к началу k -ой итерации известны отрезок [a^k,b^k] и внутренняя точка c^k вместе с соответствующими значениями функции.

1) по формуле (2) найдем точку минимума параболы, которую для удобства обозначим δ^k. Для определенности предположим, что δ^k>c^k.

2) вычислим f(δ^k).

3) если f(δ^k)<f(c^k), то новый отрезок [a^k+1,b^k+1] построим так: a^k+1=c^k, b^k+1=b^k. В качестве точки c^k+1 примем точку δ^k.

В противном случае (f(δ^k)≥f(c^k)) положим: a^k+1=a^k, b^k+1=δ^k, c^k+1= c^k.

4) если , то перейдем к следующей итерации. В противном случае работа алгоритма завершена, .

Случай δ^k≥c^k рассмотрите самостоятельно.

3. Методы 1-го и 2-го порядка. В этом пункте будем предполагать, что функция f(x) непрерывна и дифференцируема нужное число раз, а точка минимума x* является внутренней точкой отрезка [a,b]. В этом случае она удовлетворяет необходимому условию экстремума:

. (3)

Поэтому вместо задачи отыскания минимума функции f(x) можно решать уравнение (3) и, следовательно, для отыскания экстремума можно использовать численные методы решения уравнений. Ниже рассматриваются два метода, базирующиеся на этом принципе.

3.1. Метод дихотомии (половинного деления). Пусть [a^k,b^k] – отрезок на k -ой итерации метода ([a¹,b¹]=[a,b]). Заметим, что на концах отрезка производная функции f(x) имеет значения различных знаков.

1) найдем середину отрезка c^k=(b^k-a^k)/2.

2) вычислим f'(c^k). Если f’(c^k)=0, то решение задачи окончено: x^*=c^k. В противном случае перейдем к п.3.

3) новый отрезок построим в зависимости от соотношения знаков значений производной функции в точке c^k и на одном их концов отрезка, например a^k. Если f’(c^k) и f’(a^k) имеют различные знаки, то a^k+1=a^k, b^k+1=c^k; в противном случае a^k+1=c^k, b^k+1=b^k.

4) если b^k+1-a^k+1<ε, то работа алгоритма завершена: . В противном случае переходим к следующей итерации.

В этом алгоритме используются производные 1-го порядка. Поэтому его можно отнести к методам 1-го прядка.

3.2. Метод Ньютона. Метод Ньютона базируется на популярном методе решения уравнений. Если g(x)=0 заданное уравнение, x0 – известное приближение к решению, то решение с заданной точностью находится по итерационной формуле:

(4)

Подставляя в формулу (4) вместо g(x) производную f’(x), получаем:

Этот метод откосится к методам второго порядка.