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

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

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

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] на основе вычислительных экспериментов показали, что метод Марквардта отличается высокой эффективностью при решении задач такого типа.

Дата добавления: 2018-06-01; просмотров: 614; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒

Мы поможем в написании ваших работ!