Модифицированный метод Ньютона

⇐ ПредыдущаяСтр 5 из 7Следующая ⇒

Опыт показывает, что при исследовании неквадратичных функций метод Ньютона не отличается высокой надежностью. В самом деле, если точка х⁽⁰⁾ находится на значительном расстоянии от точки х*, шаг по методу Ньютона часто оказывается чрезмерно большим, что может привести к отсутствию сходимости. Метод можно довольно просто модифицировать, с тем чтобы обеспечить уменьшение целевой функции от итерации к итерации и осуществлять поиск вдоль прямой, как в методе Коши. Последовательность итераций строится в соответствии с формулой

x = x – α f (x ) f(x ). (3.56)

Выбор α осуществляется таким образом, чтобы

f (x ) → min;

это гарантирует выполнение неравенства

f (x ) ≤ f (x ).

Такой метод носит название модифицированного метода Ньютона и в случаях, когда вычисление точных значений первых и вторых производных не сопряжено с существенными трудностями, оказывается надежным и эффективным. Однако при использовании модифицированного метода Ньютона на каждой итерации возникает необходимость построения и решения_линейного уравнения, содержащего элементы матрицы Гессе f( ).

Метод Марквардта

Рассматриваемый метод является комбинацией методов Коши и Ньютона, в которой удачно сочетаются положительные свойства обоих методов. Вместе с тем при использовании метода Марквардта требуется информация о значениях вторых производных целевой функции. Выше было отмечено, что градиент указывает направление наибольшего локального увеличения функции, а движение в направлении, противоположном градиенту, из точки х⁽⁰⁾, расположенной на значительном расстоянии от точки минимума х*, обычно приводит к существенному уменьшению целевой функции. С другой стороны, направления эффективного поиска в окрестности точки минимума определяются по методу Ньютона. Простая идея объединения методов Коши и Ньютона была положена в основу алгоритма, разработанного Марквардтом [25] в 1963 г. В соответствии с этим методом направление поиска определяется равенством

s(x^(k)) = – [ Н ^(k) + λ ^(k) I ]^-1 f (x^(k)). (3.57)

При этом в формуле (3.42) следует положить α ⁽^k⁾ = +1, поскольку параметр λ позволяет не только изменять направление поиска, но и регулировать длину шага. Символом I здесь обозначена единичная матрица, т. е. матрица, все элементы которой равны нулю, за исключением диагональных элементов, равных +1. На начальной стадии поиска параметру λ ⁽⁰⁾ приписывается большое значение (например, 10⁴), так что

[ Н ⁽⁰⁾ + λ ⁽⁰⁾ I ]^-1 = [λ ⁽⁰⁾ I ]^-1 = I. (3.58)

Таким образом, большим значениям λ ⁽⁰⁾ соответствует направление поиска s(x⁽⁰⁾) → f (x⁽⁰⁾).Из формулы (3.57) можно заключить, что при уменьшении λ до нуля s(x) изменяется от направления, противоположного градиенту, до направления, определяемого по методу Ньютона. Если после первого шага получена точка с меньшим значением целевой функции (т.е. f(х⁽¹⁾) < f(x⁽⁰⁾)), следует выбрать λ ⁽¹⁾ < λ ⁽⁰⁾ и реализовать еще один шаг; в противном случае следует положить λ ⁽⁰⁾ = β λ ⁽⁰⁾, где β > 1, и вновь реализовать предыдущий шаг. Ниже представлены шаги алгоритма.

Алгоритм Марквардта

Шаг 1.Задать х⁽⁰⁾— начальное приближение к х*; М — максимальное (допустимое) количество итераций; ε — параметр сходимости.

Шаг 2.Положить k = 0, λ ⁽⁰⁾ = 10⁴.

Шаг 3.Вычислить компоненты f (x⁽^k⁾).

Шаг 4.Выполняется ли неравенство

|| f (x⁽^k⁾)|| < ε?

Да: перейти к шагу 11.

Нет: перейти к следующему шагу.

Шаг 5.Выполняется ли неравенство k ≥ M?

Да: перейти к шагу 11.

Нет: перейти к следующему шагу.

Шаг 6.Вычислить s(x⁽^k⁾) = – [ Н ⁽^k⁾ + λ ⁽^k⁾ I ]^-1 f (x⁽^k⁾).

Шаг 7.Положить x = x s (x ).

Шаг 8.Выполняется ли неравенство f (x ) < f (x )?

Да: перейти к шагу 9.

Нет: перейти к шагу 10.

Шаг 9.Положить λ ⁽^k⁺¹⁾ = ½ λ ⁽^k⁾ и k = k+1. Перейти к шагу 3.

Шаг 10.Положить λ ⁽^k⁾ = 2λ ⁽^k⁾. Перейти к шагу 6.

Шаг 11.Печать результатов и останов.

Метод Марквардта характеризуется относительной простотой, свойством убывания целевой функции при переходе от итерации к итерации, высокой скоростью сходимости в окрестности точки минимума х*, а также отсутствием процедуры поиска вдоль прямой. Главный недостаток метода заключается в необходимости вычисления Н ⁽^k⁾ и последующего решения системы линейных уравнений, соответствующей (3.57). Этот метод широко используется при решении задач, в которых f(x) записывается в виде суммы квадратов¹⁾, т.е.

f (x) = f (x) + f (x) +…+ f (x). (3.59)

Именно такая задача рассматривалась Марквардтом. Пауэлл [26] и Бард [27] на основе вычислительных экспериментов показали, что метод Марквардта отличается высокой эффективностью при решении задач такого типа.

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒