Лекции.ИНФО


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



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

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

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

f (x ) → min;

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

f (x ) ≤ f (x ).

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

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

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

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

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

[Н(0) + λ(0)I]-1 = [λ(0)I]-1 = I. (3.58)

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

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

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

Шаг 2.Положить k = 0, λ(0) = 104.

Шаг 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+1) = ½ λ(k) и k = k+1. Перейти к шагу 3.

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

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

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

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

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









Читайте также:

Последнее изменение этой страницы: 2016-03-17; Просмотров: 197;


lektsia.info 2017 год. Все права принадлежат их авторам! Главная