2015-04-01
481
Как и в § 2.3, решается задача (2.1.1): найти x * Î En, для которого выполнено условие
f (x *) = min f (x),
x Î En
где x = (x 1, x 2, …, xn) т – вектор варьируемых параметров x 1, x 2, …, xn;
n – размерность вектора х; f (x) – вещественная скалярная функция векторного аргумента или функция n -переменных; En – n- мерное евклидово пространство.
Метод решения этой задачи по-прежнему будем представлять в виде
x (k + 1) = x (k) + a ks (k), k = 0, 1, 2, …
Для определения направления движения из точки x ( k ) в точку x(k + 1) осуществим квадратическую аппроксимацию функции f (x) в окрестности точки x ( k ):
j(x) = f (x (k)) + (Ñ f (x (k)), x – x (k)) + 0.5(x – x (k))т H (x (k))(x – x (k)). (2.4.1)
Функцию j(x) можно получить, если в разложении функции f (x)
в ряд Тейлора в окрестности точки x ( k ) ограничиться первыми тремя членами ряда, отбросив все остальные, имеющие более высокий, чем второй, порядок по (x – x ( k )). Предположим, что вычисленная в точке x ( k ) матрица Гессе H (x ( k )) функции f (x) положительно определенная. В этом случае функция j(x) выпуклая и имеет только одну точку минимума, совпада-ющую со стационарной точкой данной функции. Определим эту точку, приравняв градиент функции j(x) к нулевому вектору:
|
|
|
Ñj(x) = Ñ f (x (k)) + H (x (k))(x – x (k)) = 0. (2.4.2)
В результате получим систему линейных уравнений относительно (x – x ( k ))
H (x (k))(x – x (k)) = –Ñ f (x (k)), (2.4.3)
решив которую имеем
(x – x ( k )) = –[ H (x ( k ))]-1Ñ f (x ( k )). (2.4.4)
Направление
s ( k ) = –[ H (x ( k ))]–1Ñ f (x ( k )) (2.4.5)
будем выбирать для движения из точки x ( k ) в точку x ( k + 1). В итоге получим рекуррентную формулу для вычисления x ( k + 1) при известном x ( k )
x (k + 1) = x (k) – [ H (x (k))]–1Ñ f (x (k)), k = 0, 1, 2, …, (2.4.6)
где [ H (x ( k ))]–1 – матрица, вычисленная в точке x ( k )) и обратная матрице Гессе функции f (x).
Рекуррентная формула (2.4.6) "определяет" так называемый метод Ньютона для решения задачи (2.1.1). На практике чаще реализуется другая форма представления метода Ньютона, в соответствии с которой вместо обращения матрицы H (x ( k )) на каждом шаге метода решается система линейных уравнений (2.4.3). В этом случае метод Ньютона записывается в виде
(2.4.7)
Решение задачи начинаем с некоторой точки x (0) Î En. Тогда метод Ньютона может быть представлен в виде процедуры, аналогичной процедуре метода наискорейшего спуска с той лишь разницей, что направление s ( k ) находится на каждом шаге решения системы линейных уравнений, а длина шага не нуждается в определении.
Пусть функция f (x) дважды непрерывно дифференцируемая. В этом случае метод Ньютона для решения задачи (2.1.1) можно записать в виде следующего алгоритма:
1. Начать с x (0) Î En, задав e > 0 и k = 0.
2. Вычислить Ñ f (x ( k )) = (¶f (x ( k ))/ ¶x 1, ¶f (x ( k ))/ ¶x 2, …, ¶f (x ( k ))/ ¶xn) т.
|
|
|
3. Если || Ñ f (x ( k )) || £ e, перейти к выполнению п. 9.
4. Вычислить Hk = H (x ( k )) и составить систему линейных уравнений:
Hks (k) = –Ñ f (x (k)). (2.4.8)
5. Найти s ( k ) из решения системы (2.4.8).
6. Вычислить x ( k + 1) по формуле
(x (k + 1) = x (k) + s (k)).
7. Если || x ( k + 1) – x ( k ) || / || x ( k ) || £ e, перейти к выполнению п. 9.
8. Положить k: = k + 1и перейти к выполнению п. 2.
9. Процесс окончен: x ( k ) – искомая точка минимума f (x).
Отметим характерные особенности метода Ньютона:
1. Является итерационным, относится к методам второго порядка и на каждой итерации требует вычисления n частных производных первого порядка и n 2 частных производных второго порядка минимизируемой функции.
2. При выполнении условий сходимости сходится к решению задачи с квадратической скоростью.
3. Помимо вычисления частных производных на каждом шаге необходимо решать систему линейных уравнений n -го порядка или обращать матрицу этой системы. В результате объем вычислительных операций
на каждом шаге метода Ньютона достаточно велик.
4. Не обладает свойством глобальной сходимости в том смысле, что неудачный выбор начального приближения x (0) может привести к расходимости метода. Начальное приближение x (0) рекомендуется выбирать в достаточной близости к локальному экстремуму минимизируемой функции.
5. Для квадратической функции f (x) находит решение задачи (2.1.1) за один шаг.
Существует много модификаций метода Ньютона, которые используются для снижения объема вычислительных операций на каждом шаге или обеспечения сходимости метода при любом начальном приближении x (0). Так, например, матрица Hk вычисляется либо один раз (H 0) и затем используется без изменения на всех итерациях, либо вычисляется заново через фиксированное (более чем один раз) количество итераций H 0, Hs, H 2 s, … (s > 1), а для промежуточных итераций в качестве Hk -1 используется последняя из вычисленных матриц. Такие модификации метода Ньютона имеют целью уменьшить количество вычисляемых матриц Hk, одновременно снижая трудоемкость многократного решения системы линейных уравнений (2.4.8). При выполнении некоторых дополнительных условий эти модификации часто сохраняют достаточно высокую скорость сходимости.
К другой группе относятся модификации метода Ньютона с регулировкой шага. В этом случае очередное приближение x ( k + 1) определяется по формуле
x (k + 1) = x (k) + a k s (k), k = 0, 1, 2, …,
где числовой параметр 0 < a k £ 1 задает длину шага из x ( k ) в направле-
нии s ( k ); при этом значение параметра a k часто определяется из решения одномерной задачи
j(a k) = min {j(a) = f (x (k) + a s (k)}.
a > 0
Главной целью такого подхода является стремление уменьшить зависимость сходимости метода от выбора начального приближения x (0). Метод Ньютона часто используется в комбинации с другими методами, например с методом наискорейшего спуска, который достаточно быстро находит хорошее приближение к решению задачи, используемое в качестве начального для метода Ньютона. Подробное описание таких подходов имеется во многих руководствах по вычислительной математике.
