Минимизация функций одной переменной

иначе x₃=x₁-2Dx.

4. Вычислить f₃=f(x₃)

   и найти

             f_min=min{f₁, f₂, f₃},

             x_min-точка, которой соответствует f_min.

5. Вычислить x_a* по трем точкам x₁, x₂ и x₃ в соответствии с   формулой квадратичной аппроксимации.
6. Вычислить [f_min-f(x_a*)] и (x_min- x_a*).

Если обе  разности достаточно малы, то Стоп.

7. Выбрать "наилучшую" точку из x_min и x_a* и две точки по обе стороны от нее. Пронумеровать эти точки в естественном порядке и перейти к 4.

 

Заметим, что  при первой реализации шага 5 границы интервала, содержащего точку минимума, не обязательно оказываются установленными. При этом полученная точка x_а* может находиться за точкой x₃. Для того чтобы исключить возможность слишком большого экстраполяционного перемещения, следует провести после шага 5 дополнительную проверку и в случае, когда точка x_а* находится слишком далеко от x₃, заменить x_а* точкой, координата которой вычисляется с учетом заранее установленной длины шага.

 

• Пример. Методом Пауэлла минимизировать

 

f(x)= 2x³ + (16/x).

 

Пусть начальная точка  x₁=1 и длина шага Dx=1. Для проверки правила окончания поиска (или правила останова) будем использовать следующие параметры сходимости:

 

           ||(разность значений x)/x|| £ 3×10^-2,

 

           ||(разность значений f)/f|| £ 3×10^-3.

 

Итерация 1

Шаг 1.    x₂=x₁+Dx=2.

Шаг 2.    f(x₁)=18, f(x₂)=16 .

Шаг 3.    f(x₁)> f(x₂), следовательно, положить x₃=1+2=3.

Шаг 4.    f(x₃)=22.33,  F_min=16,   X_min=x₂=2.

Шаг 5.    a₁=(16-18)/(2-1)=-2,

          a₂= ,

          x=

          f(x)=15.210.

 

 

Шаг 6. Проверка на окончание поиска:

 

          > 0.003.

Следовательно, поиск продолжается.

Шаг 7. Выбираем x как "наилучшую" точку, а x₁=1 и x₂=2 - как точки, которые ее окружают. Обозначаем эти точки в ес-тественном порядке и переходим к итерации 2, которая на-чинается с шага 4.

 

Итерация 2.

Шаг 4.    x₁=1,          f₁=18,

          x₂=1.714,      f₂=15.210=F_min,    X_min=x₂=171,

          x₃=2,          f₃=16.

 

Шаг 5.    a₁=(15.21-18)/(1.714-1)=-3.908,

          a₂= ,

          x=

          f(x)=15.142.

 

Шаг 6. Проверка на окончание  поиска:

 

          > 0.003.

Условие не выполняется, следовательно, поиск продолжается.

 

Шаг 7.        Выбираем x как "наилучшую" точку, а x₁=1 и x₂=1.714 - как точки, которые ее окружают.

 

Итерация 3.

Шаг 4.    x₁=1,          f₁=18,

          x₂=1.65,       f₂=15.142=F_min,    X_min=x₂=1.65,

          x₃=1.714,      f₃=15.210.

 

Шаг 5.    a₁=(15.142-18)/(1.65-1)=-4.397,

          a₂= ,

          x=

          f(x)=15.123.

 

Шаг 6. Проверка на окончание поиска:

 

          < 0.003,

 

          < 0.003.

Следовательно, поиск закончен.

1.3.2. Кубическая  аппроксимация

В соответствии с рассматриваемым методом минимизируемая функция f аппроксимируется полиномом третьего порядка. Логическая схема метода аналогична схеме методов с использованием квадратичной аппроксимации. Однако в данном случае построение аппроксимирующего полинома проводится на основе меньшего количества точек, поскольку в каждой точке можно вычислять как значение функции, так и ее производной.

Работа алгоритма  начинается в точке x₁, задаваемой пользователем, а затем находится другая точка x₂, такая, что производные f'(x₁) и f'(x₂) имеют разные знаки. Это означает, что стационарная точка x*, в которой f'(x*)=0, будет лежать в интервале между выбранными точками x₁ и x₂.

Аппроксимирующая  кубическая функция записывается в виде:

 

       f_a(x)=a₀+a₁(x-x₁)+a₂(x-x₁)(x-x₂)+ a₃(x-x₁)²(x-x₂).  (1.25)

 

Параметры уравнения (1.25) подбираются таким образом, чтобы  значения f_a(x) и ее производной в точках x₁ и x₂ совпадали со значениями f(x) и f’(x) в этих точках. Первая производная f_a(x) равна

 

f_a’(x)=a₁+a₂(x-x₁)+a₂(x-x₂)(x-x₂)+a₃(x-x₁)²+2a₃(x-x₁)(x-x₂).(1.26)

 

Коэффициенты a₀, a₁, a₂ и a₃ уравнения (1.26) определяются по известным значениям f(x₁), f(x₂), f’(x₁) и f’(x₂) путем решения следующей системы линейных уравнений:

 

f₁ = f(x₁)=a₀,

f₂  =f(x₂)=a₀+a₁(x₂-x₁),

f₁’=f’(x₁)=a₁+a₂(x₁-x₂),

f₂’=f’(x₂)=a₁+a₂(x₂-x₁)+a₃(x₂-x₁)².

 

Заметим, что  данная система легко решается рекурсивным  методом. После того как коэффициенты найдены, действуя по аналогии со случаем  квадратичной аппроксимации, можно оценить координату стационарной точки функции f c помощью аппроксимирующего полинома (1.25). При этом приравнивание к нулю производной (1.26) приводит к квадратному уравнению. Используя формулу для вычисления корней квадратного уравнения, запишем решение, определяющее стационарную точку аппроксимирующего кубического полинома, в следующем виде:

 

            x_a*= ,               (1.27)

где

              m =(f₂’+w-z)/(f₂’-f₁’+2w),

 

              z =3(f₁-f₂)/(x₂-x₁)+f₁’+f₂’,

 

                 ì   (z²-f₁’f₂’)^1/2,  если x₁<x₂,

              w =í  

                 î -(z²-f₁’f₂’)^1/2,   если x₁<x₂.

 

Формула для w обеспечивает надлежащий выбор одного из двух корней квадратного уравнения; для значений m, заключенных в интервале от 0 до 1, формула (1.27) гарантирует, что получаемая точка x_а* расположена между x₁ и x₂.

Затем снова  выбираются две точки для реализации процедуры кубической аппроксимации - x_а* и одна из точек x₁ и x₂, причем значения производной исследуемой функции в этих точках должны быть противоположны по знаку, и процедура кубичной аппроксимации повторяется.

 

1.4. МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ  ПРОИЗВОДНЫХ

 

1.4.1. Метод Ньютона-Рафсона

 

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

Метод, разработанный  Ньютоном, а затем уточненный Рафсоном предполагает, что f(x) дважды дифференцируема. Работа алгоритма начинается в точке x₁, которая представляет начальное приближение (или начальную оценку) искомой точки минимума, или корня уравнения f’(x)=0. Затем строится линейная аппроксимация функции f’(x) в точке x₁, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения.

Формализм метода заключается в следующем. Пусть x_k является текущим приближением к стационарной точке. Тогда линейная аппроксимация f_a’ производной f’(x) в точке x_k равна

 

               f_a’(x, x_k)= f’(x)+ f’’(x_k)(x-x_k)         (1.28)

 

Приравнивая правую часть (1.28) нулю, получим следующее  приближение:

 

               x_k+1 = x_k-[f’(x_k)/f’’(x_k)].

 

 

0   x_k             x_k+2 x_k+1     x 

 

Рис.1.6. Метод  Ньютона-Рафсона

На рис.1.6 дана геометрическая интерпретация метода Ньютона-Рафсона.

При всей своей  простоте, метод Ньютона обладает существенным недостатком, который  заключается в том, что его сходимость весьма чувствительна к выбору начальной точки поиска. Так, например, на рис.1.7 изображен случай, когда сходимость отсутствует:

f’(x)

 

 

                                   0   x*     x₀    x_k    x_k+1    x_k+2  х

 

                      Рис.1.7. Случай отсутствия

                  сходимости метода Ньютона-Рафсона

 

Рекомендации  для выбора начальной точки, гарантирующие сходимость метода заключаются в следующем:

 

• x₀ должна быть достаточно близка к корню уравнения f’(x)=0;
• производная f’(x₀) не слишком близка к нулю;
• производная f”(x₀) не слишком велика.

 

 

1.4.2.  Методы  средней точки и секущих

 

Метод средней  точки является эффективным методом уменьшения интервала неопределенности на основе информации, вычисленной только в одной пробной точке.

 

       Алгоритм метода средней точки  (метод Больцано)

Задать интервал унимодальности [a, b] и параметр сходимости e.

1. Положить R=b, L=a; (при этом f’(a)<0 и f’(b)>0).
2. Вычислить z=(R+L)/2 и f’(z).
3. Если |f’(z)|£ e, то Стоп;

   иначе,  если f’(z)<0, то L=z; перейти к 2;

          иначе, R=z и перейти к 2.

 

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

Метод секущих  как раз и использует информацию не только о знаке производной, но и о величине этой производной. Предположим, что в процессе поиска стационарной точки функции f(x) в интервале унимодальности [a, b] обнаружены две точки L и R, в которых знаки производных различны. В этом случае алгоритм метода секущих позволяет аппроксимировать функцию f’(x) «секущей прямой» (или «хордой») и найти точку, в которой секущая графика f’(x) пересекает ось абсцисс (рис.1.8). Таким образом следующее приближение к стационарной точке x* определяется по формуле

 

                   z= .

 

Если модуль f’(z) не больше параметра сходимости e, то поиск точки минимума завершен. В противном случае нужно выбрать одну из точек L или R, чтобы знаки производной в этой точке и точке z были различны, а затем повторить итрерацию. Например, в ситуации, изображенной на рис.1.8, в качестве этих точек должны быть выбраны точки z и R. Этот метод в ряде случаев позволяет исключать более половины интервала неопределенности.

       f’(x)    

L z x* R

 

              

                      

                 

Рис.1.8. Метод  секущих 

 

Легко видеть, что  в отличие от метода средней точки метод секущих основан на исследовании не только знака, но и значений производной в пробных точках и поэтому в ряде случаев позволяет исключить более половины интервала поиска.

1.4.3.  Численная  аппроксимация производных

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

Схема конечно-разностной аппроксимации вытекает из ряда Тейлора, если мы будем решать обратную задачу: аппроксимировать неизвестные значения производных в точке по известным значениям функции в окрестности некоторой точки. В одномерном случае из  тейлоровского разложения в окрестности точки x⁰ дважды дифференцируемой функции f(x) следует, что оценка первой производной может быть записана в виде: