55

Анализ метода Фибоначчи и метода золотого сечения показывает, что, начи-

ная с некоторого числа значения экспериментов N, FN −1 ≈ τ2 , следовательно, точ-

FN +1

ки испытаний на первом шаге практически одинаковы в обоих методах. Так, при

вать оба метода в виде единой процедуры поиска минимума унимодальной функции F(x) , определенной на интервале [ 0 ,1] (рис. 4. 4).

4.1.3. Методы с использованием производных. Эффективность процедуры поиска экстремума можно повысить, если ввести требование дифференцируемо-

сти функции. Необходимым условием существования минимума в точке x* является равенство нулю первой производной функции в этой точке, т.е.

Если функция F(x) содержит члены, включающие x в третьей и более высоких степенях, то получение аналитического решения уравнения F ' (x) = 0 может

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

Метод Ньютона-Рафсона. Будем полагать, что функция F(x) дважды дифференцируема. Пусть точка xk является текущим приближением к точке экстре-

56

x1 = 0, x2 =1 γ = τ2

F1 = F(x3 )

x4 = x1 + (x2 − x3 )

F2 = F(x4 )

x* = x3, Fmin = F1

Рис. 4.4. Алгоритм поиска минимума унимодальной функции методом Фибоначчи и методом золотого сечения

Графическая интерпретация процедуры поиска методом Ньютона-Рафсона приведена на рис. 4.5, а. Точка x0 является начальной оценкой корня уравнения

F ' (x) = 0 (или начальной оценкой координаты точки экстремума). Касательная к

57

функции F ' (x) в точке x0 является линейной аппроксимацией функции F(x) в точке x0 . Точку пересечения этой касательной с осью абсцисс принимают за новую точку x1, в которой проводят следующую касательную к функции и т.д. Итерации продолжаются до тех пор, пока не будет выполняться неравенство F ' ( xk ) ≤ ε , где ε – заранее заданная точность решения задачи.

В зависимости от выбора начальной точки x0 и вида функции F ' (x) алгоритм

может расходиться (рис. 4.5, б). Если x0 расположена правее точки z, то получаемые в результате последовательных приближений точки удаляются от x*. Для улучшения сходимости используют модифицированный метод, в котором вводится шаг αk [0,1] . При этом процесс отыскания нуля производной задается форму-

лой:

Рис. 4.5. Графическая интерпретация метода Ньютона-Рафсона: а – сходимость метода; б – отсутствие сходимости

Метод хорд, или метод «секущих» является комбинацией метода Ньютона-Рафсона и общей схемы исключения интервалов и заключается в нахо-

ждении корня уравнения F ' (x) = 0 в интервале [a, b] , если такой корень

существует.

Для решения задачи в интервале [a, b] выбираются две точки M и N, в которых знаки производных различаются. Функция F ' (x) аппроксимируется «секу-

58

щей» прямой, соединяющей F ' (M ) и F ' (N ) и находится точка z , в которой прямая линия пересекает ось абсцисс (рис. 4.6).

F ′(x)

F ′(N )

x*

F′(M )

Рис. 4.6. Графическая интерпретация метода хорд

Уравнение прямой, проходящей через две точки с координатами (x1, y1) и (x2 , y2 ) , имеет вид

Если F ' (z) ≤ ε, поиск следует прекратить. В противном случае необходимо

выбрать одну из точек M или N таким образом, чтобы знаки производной в этой точке и точке z были различными, и снова повторить основной шаг алгоритма.

59