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

Метод секущих, являющийся комбинацией метода Ньютона и общей схемы исключения интервалов, ориентирован на нахождение корня уравнения f '(x)=0 в интервале (а, b), если, разумеется, такой корень существует.

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

Если |f(z)|≤ , поиск следует закончить. В противном случае необходимо выбрать одну из точек L или R таким образом, чтобы знаки производной в этой точке и точке z были различны, а затем повторить основной шаг алгоритма. Например, в ситуации, изобра­женной на рис. 2.16, в качестве двух следующих точек должны быть выбраны точки z и R. Легко видеть, что в отличие от метода средней точки метод секущих основан на исследовании не только знака, но и значений производной в пробных точках и поэтому в ряде случаев позволяет исключить более половины интервала поиска (см. рис. 2.16).

Пример 2.11. Метод секущих

Опять рассмотрим задачу из примера 2.10:

минимизировать f(x)=2x²+(16/x) в интервале 1≤х≤5.

Шаг 3. f '(z)=3,51>0; положить R = 1,94. Итерации продол­жаются до тех пор, пока не будет выполняться неравенство |f(z)|≤ .

2.5.4. Метод поиска с использованием кубичной аппроксимации

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

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

f (Х)=а₀+а₁(х—х₁)+а₂(х—х₁) (х—х₂} +а₃(х—х₁ )²(х—х₂). (2.8)

Параметры уравнения (2.8) подбираются таким образом, чтобы зна­чения f (х) и ее производной в точках х₁ и х₂ совпадали со значениями f (х) и f '(x) в этих точках. Первая производная функции f(x) равна

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

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

Формула для  обеспечивает надлежащий выбор одного из двух корней квадратного уравнения; для значений , заключенных в ин­тервале от 0 до 1, формула (2.10) гарантирует, что получаемая точка х расположена между х₁ и х₂. Затем снова выбираются две точки для реализации процедуры кубичной аппроксимации — х, и одна из точек x₁ или х₂, причем значения производной исследуемой функции в этих точках должны быть противоположны по знаку, и процедура кубичной аппроксимации повторяется.

Приведем формализованное описание алгоритма. Пусть заданы начальная точка х₀, положительная величина шага  и параметры сходимости ₁ и ₂.

Шаг 1. Вычислить f ‘(х₀).

Шаг 2. Вычислить значения f '(x) в точках х_к+1 при K=0, 1, 2, ... вплоть до точки х_M, в которой f '(x_M-l) f '(x_M)≤0. Затем положить x_l=x_M-1, х₂=х_M. Вычислить значения f₁ f₂, f ₁’ и f ’₂.

Ш а г 3. Найти стационарную точку х аппроксимирующего ку­бичного полинома, пользуясь формулой (2.10).

Ш а г 4. Если f(x)<f(x₁ ), перейти к шагу 5. В противном слу­чае вычислять х по формуле x=x+¹/2(x—х₂) до тех пор, пока не будет выполняться неравенство f(x)≤f(x_l).

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

Затем перейти к шагу 3.

Заметим, что шаги 1 и 2 реализуют процедуру поиска границ интервала по эвристическому методу, причем изменение знака про­изводной используется в качестве критерия перехода через точку оптимума. На шаге 3 проводятся вычисления координаты точки оптимума аппроксимирующего полинома. Шаг 4 ассоциирован с проверкой того факта, что полученная оценка действительно явля­ется улучшенным приближением к точке оптимума. В случае когда значения производной вычисляются непосредственно, метод поиска с использованием кубичной аппроксимации, безусловно, оказыва­ется более эффективным по сравнению с любым из представленных выше методов поиска. Однако если значения производной вычисля­ются путем разностного дифференцирования, то предпочтение сле­дует отдать методу Пауэлла, основанному на квадратичной аппрок­симации.

Пример 2.12. Поиск с использованием кубичной аппроксимации и производных

Опять рассмотрим задачу, в которой требуется

минимизировать f(x)=2x²+16/x.

Пусть начальная точка х₀=1 и длина шага  = 1. В качестве пара­метров сходимости используем

Поиск закончен.

Заметим, что при тех же самых исходных точках x₁=l и х₂=2 метод Пауэлла в примере 2.9 позволил получить оценку х=1,714, тогда как метод с использованием кубичной аппроксимации привел к оценке х=1,5657. Точная координата точки минимума равна 1,5874, что указывает на преимущество полиномиальной аппрок­симации более высокого порядка.