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

Назначение сервиса. Онлайн-калькулятор используется для нахождения минимума функции методом Марквардта (см. пример). Решение оформляется в формате Word.
f(x1,x2) =
Метод отыскания минимума функции
Начиная из точки ( ; ). Точность ξ = .
Количество итераций . λ = , β =
Правила ввода функций:
  1. Все переменные выражаются через x1,x2
  2. Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x12+x1x2, записываем как x1^2+x1*x2.

Метод Марквардта является комбинацией методов Коши и Ньютона. В нем сочетаются положительные свойства обоих методов. Направление поиска в ММ определяется равенством:
, (1)
где E - единичная матрица.
На начальной стадии λ0 присваивается большое значение (например, 104), так что
. (2)
Таким образом, большим значениям λ0 соответствует направление поиска d(x0)→-▽f(x0), т.е. направление поиска совпадает с направлением антиградиента. Из формулы (2) можно заключить, что при уменьшении λ до нуля направление d(x) изменяется от -▽f(x0) до –Hf-1(x). Если после первого шага получена точка с меньшим значением ЦФ (т.е. f(x1) < f(x0) ), следует выбрать λ1 < λ0 и реализовать еще один шаг. В противном случае следует положить λ0 = β λ0, где β>1 и вновь реализовать предыдущий шаг.

Схема алгоритма Марквардта
Ш. 1 Задать x0 - начальное приближение к x*;
задать M - максимальное (допустимое) количество итераций;
задать ε - параметр сходимости (точность).
Ш. 2 Положить k=0, λ0=104.
Ш. 3 Вычислить ▽f(xk).
Ш. 4 Проверить, выполняется ли критерий останова: |▽f(xk)| ≤ ε.
Да: → Ш.11. Нет: → Ш. 5.
Ш. 5 Проверить, выполняется ли критерий останова: k≥M.
Да: → Ш.11. Нет: → Ш. 6.
Ш. 6 Вычислить d(xk)=-[ Hf(xk)+ λkE]-1▽f(xk)
Ш. 7 Положить xk+1=xk+d(xk).
Ш. 8 Проверить выполнение неравенства: f(xk+1) < f(xk).
Да: → Ш.9. Нет: → Ш. 10.
Ш. 9 Положить λk+1=1/2λk и k=k+1 Ш. 3
Ш. 10 Положить λk=2λk → Ш. 6.
Ш. 11 Печать результатов.

Достоинства метода Марквардта. Относительная простота, ЦФ убывает от итерации к итерации, высокая скорость сходимости в окрестности точки минимума x*, отсутствует процедура поиска вдоль прямой.
Недостатки метода Марквардта. Необходимость вычисления Hf(xk) и последующего решения системы линейных уравнений (1).
Этот метод широко используется при решении задач (например, в регрессионном анализе) в которых f(x) может быть записана в виде суммы квадратов, т.е.
. (3)

Пример.

загрузка...