Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



Опыт показывает, что при исследовании неквадратичных функ­ций метод Ньютона не отличается высокой надежностью. В самом деле, если точка х(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; Просмотров: 1357; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.01 с.)
Главная | Случайная страница | Обратная связь