Случаи, когда один или два из отрезков [a,α], [α,β], [β,b] вырождаются в точку, здесь не исключаются. В частности, если α=β, то функция f0(x) строго унимодальная на [а,b] (рис. 9д).

Пусть f0(x) унимодальная функция, заданная на интервале [а,b]. Тогда по любым двум значениям f0(x1) и f0(x2) можем указать интервал, в котором находится точка минимума, причем этот интервал имеет меньшую длину, чем первоначальный.

Пусть для определенности x1<x2 и возможны следующие варианты (рис.9 а,б,в). Отбрасываемая часть интервала заштрихована.

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

7.4. Метод дихотомии

Метод дихотомии применяется для унимодальных функций. Метод дихотомии заключается в том, что исходный интервал [а,b] делится средней точкой с = (b + a) / 2 на два подинтервала [а,с] и [с,b] в одном из которых лежит точка минимума х*.

Для выбора подинтервала, для хорошо дифференцируемой функции вычисляют в точке c производную f0'(с) и анализируют ее знак. Если f0'(с)>0, то х*лежит слева от точки c, т.е. В отрезке [а,с]; если f0'(с)<0, то х* лежит справа от точки c, т.е. В отрезке [с,b], а при f0 '(c) ≈ 0 найдена точка минимума х* = с.

Если f0(x) не дифференцируемая, то выясняется направление убывания унимодальной функции. С этой целью задается точка с+h (где h>0 − малая величина, соизмеримая с ε и вычисляется ордината f0(с+h).

Если приращение функции f0 (c) = f0 (c) − f0 (c + h) < 0 , то точка х* лежит справа от точки c, т.е. х* принадлежит отрезку [с,b].

Если f0 (c) = f0 (c) − f0 (c + h) > 0 , то точка х* лежит сktdf от точки c, т.е. х* принадлежит отрезку [a,c].

63

При f0 (c) ≈ 0 имеем точку минимума x* ≈ c .

После выбора подинтервала, в котором находится х*, например [с,b], переопределяем левую границу а=с (при выборе [а,с] следует поменять правую границу b=с).

Проверяем b − a ≤ ε , если нет, то вновь делим отрезок [b-a] попо-

лам и опять определяем, в каком подинтервале находится точка минимума.

Алгоритм поиска минимума:

1.Вводим границы [а,b] и ε. h = 100 ε.

2.Делим отрезок пополам с = (b + a) / 2 .

3. Вычисляем приращение функции f0 (c) = f0 (c) − f0 (c + h) . Если f0(с) < 0, то a = с, иначе если f0(с) ≥ 0, то b = с.

4.Проверяем условие (b − a) ≤ ε ? Если нет, то переходим на п.2, да – переход на п.5.

5.Печать: "точка минимума х* = ", с, f0(с), f0'(c). Конец.

Для контроля правильности полученного решения можно вывести на печать значение f0'(x*), которое должно быть близко к нулю. Если условие (6.2) не выполняется, то следует искать ошибку в программе.

Если интервал, содержащий точку минимума функции определяется на основе вычисления производной f0'(с), то такая реализации метода дихотомии будет относиться к итерационным процедурам 1 порядка.

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

Метод "золотого" сечения требует только унимодальности функции f0(x).

"Золотое" сечение, открытое Евклидом, состоит в разбиении интервала [а,b] точкой x1 на две части таким образом, чтобы отношение большей части к длине всего интервала было равно отношению меньшей части к большей.

64

	b − x1	=	x1 − a	=τ
	b − a		b − x
			1

Представим интервал [а,b] как совокупность двух отрезков:

b − a = x1 − a +b − x1

Разделив уравнение (7.5) на (b-а), получим:

	x1 − a	+	b − x1	=1 .
	b − a		b − a

(7.4)

(7.5)

Так как

(b − x1 ) /(b − a) =τ

и

x1 − a

b − x1

=τ

2

, имеем

τ2 +τ =1,

b − a

b − x

1

корни которого определяются по формуле:

τ1,2 =

−1

+

1

+1,

т.е. τ =

5 −1

≈ 0,618 .

4

2

2

Из уравнения (7.4) следует

x1 = b −τ(b − a) .

(7.6)

Проведем "золотое" сечение относительно точки а, получим

x2 −a

=

b − x2

=τ .

(7.7)

b −a

x2 −a

Из уравнения (7.7) получим формулу для определения точки x2:

x2 = a +τ(b −a) .

(7.8)

Заметим,

что точка x1 производит

"золотое"

сечение

интервала

[а,x2], а точка x2 – интервала [x1,b].

Для унимодальной функции, зная значения функции в точках золотого сечения f0(x1) и f0(x2), можно определить интервал неопределенности, в котором находится х*. После выбора на оставшемся интервале нужно определить только одну точку, производящую "золотое" сечение. Для выбранного интервала [а,x2] следует положить b=x2, x2=x1 и пересчи-

65

тать точку x1 по формуле (7.6), а для [x1,b] – a=x1, x1=x2 и пересчитать точку x2 по формуле (7.8). На каждом шаге итерации длина интервала неопределенности уменьшается и составляет примерно 0,62 длины предыдущего интервала неопределенности. Итерационную процедуру следует закончить, когда длина интервала неопределенности станет меньше или равна заданной точности.

Алгоритм метода "золотого" сечения:

1.Ввод a, b, ε. Вычисляем значения x1 и x2 по формулам (7.6), (7.8).

2.Вычисляем f1 = f0(x1) и f2 = f0(x2)

3.Если f0(x1) < f0(x2), то х* находится в интервале [а,x2] (рис. 9б), т.е. b=x2. Переопределяем точки x2=x1 и f2=f1, пересчитываем точку x1 по формуле (7.6) и вычисляем f1. Переходим на п.4.

Если f0 (x1) ≥ f0 (x2 ) , то х* находится в интервале [x1,b] (рис. 9а),

т.е. a=x1, x1=x2, f1=f2. Пересчитываем точку x2 по формуле (7.8) и вычисляем f2.

4.Проверка (b–а)<ε, если нет, то переходим на п.3, да – на п.5.

5. Печать x* = (b + a) / 2 , оптимального значения критерия f0 (x* ) , f0 '(x* ) для контроля правильности полученных данных.

7.6. Одномерный градиент

Метод основан на необходимом условии существования экстремума функции. Итерационный поиск точки минимума х* дифференцируемой функции f0(х) (не обязательно унимодальной) производится с помощью процедуры первого порядка

xk +1 = xk − hf0 '(xk ), где h – const, k = 0,1,2,...,

(7.9)

где k – номер итерации, h – постоянный шаг вдоль направления антиградиента, подбираемый при решении задачи из условия, чтобы двукратное увеличение h не нарушало неравенство

66

f0 (xk +1) < f0 (xk ) .

Начальное приближение х0 задается из множества

D = { x | a ≤ x ≤ b } .

Уравнение (7.9) является уравнением градиентного спуска. Итера-

ционная процедура				уравнения (7.9) продолжается						до тех пор, пока
	f0 '(xk )		>ε, где ε –	малая положительная величина,						характеризующая
крутизну f0 (x) в окрестности точки х*.
	Последовательность точек {хk}, k = 0,1,2…								сходится к точке х* со
скоростью пропорциональной величине						f0 '(xk )		,	т.е. зависит от "крутиз-

ны" функции, чем больше, df0/dx тем быстрее {хk} стремится к точке минимума.

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

Если f0 (x) – "пологая" функция, то величина f0 ' – мала, величина

h f0 ' тоже будет мала и итерационная процедура медленно сходится к

х*.

f (x)	f '(x)
f (x)		f '(x)
x	x*	x

Рис.10. Пологая функция

Как видно из рисунка 10, справа от точки локального минимума х* первая производная имеет положительные значения, а слева от х* – отрицательные значения ( f '(x) < 0 ).

При пологом характере изменения первой производной, которое

67

может наблюдаться вблизи х*, значение f '(x) может изменяться незначительно, при существенном изменении аргумента. В этом случае число итераций будет очень большим. Чтобы избежать медленного перемещения к точке х* шаг h следует увеличить вдвое (h = 2·h), либо использовать итерационные процедуры второго порядка.

Если крутой участок расположен вблизи точки х* (рис.11), то в итерационной процедуре может возникнуть явление "зацикливания",

когда производные f0 '(xk ) и f0 '(xk+1) примерно равны и имеют разные знаки. Для борьбы с явлением "зацикливания" уменьшают параметр h, например, вдвое (h=h/2), или переходят на другие методы поиска экстремума.

f (x)

f '(x)

f '(xk)

xk+1

xk+1 x* xk

x

x*

f '(xk) ≈ -f '(xk+1)
xk	x
f '(xk+1)

Рис.11. Функция с крутым участком вблизи точки х*

При трудном вычислении производной используют вместо f0 ' конечную разность

df0 / dx ≈ ( f0 (xk+δ ) − f0 (xk )) /δ,

где величина параметра δ мала по сравнению с xk.

Величину δ находят из условия, что шаги 2δ и 3δ не должны влиять на величину df0 / dx .

Алгоритм поиска точки локального минимума:

1.Ввод начального приближения x0, точности ε, величины шага h, (при использовании конечных разностей ввод значения δ).

2.Вычисляется значение критерия f0 = f0(x0), производная f0' = f0(x0)

или конечная разность f0 (x0 ) = f0 (x0 +δ) − f0 (x0 ).

68