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

Назначение сервиса. Онлайн-калькулятор используется для нахождения минимума функции методом Марквардта (см. пример). Решение оформляется в формате 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)

Пример. f(x)=x12+x22+2x1x2+5 → min
Градиент:


Матрица Гессе:

Hf =

Итерация №1.
Значение градиента в точке x0: ▽f(x0) = (4;4)
Проверим критерий остановки:
|▽f(X0)|=<ε
Имеем:
|▽f(X0)| = 5.6569>0.1
Вычислим значение функции в начальной точке f(x0) = 9. Сделаем шаг вдоль направления антиградиента
S1 = -[H00I]-1▽f(x0)
S1 = -(
22
22
+1
10
01
)-1
4
4
= (-0.8,-0.8)

x1 = (1,1) + (-0.8,-0.8) = (0.2,0.2)
Вычислим значение функции в новой точке: f(x1) = 5.16
Поскольку f(x1) < f(x0), то λ=1/2 = 1/2
Итерация №2.
Значение градиента в точке x1: ▽f(x1) = (0.8;0.8)
Проверим критерий остановки:
|▽f(X1)| = 1.1314>0.1
Вычислим значение функции в точке f(x1) = 5.16. Сделаем шаг вдоль направления антиградиента
S2 = -[H11I]-1▽f(x1)
S2 = -(
22
22
+1/2
10
01
)-1
0.8
0.8
= (-0.178,-0.178)

x2 = (0.2,0.2) + (-0.178,-0.178) = (0.0222,0.0222)
Вычислим значение функции в новой точке: f(x2) = 5.002
Поскольку f(x2) < f(x1), то λ=(1/2)/2 = 1/4
Итерация №3.
Значение градиента в точке x2: ▽f(x2) = (0.0889;0.0889)
Проверим критерий остановки:
|▽f(X2)| = 0.1257>0.1
Вычислим значение функции в точке f(x2) = 5.002. Сделаем шаг вдоль направления антиградиента
S3 = -[H22I]-1▽f(x2)
S3 = -(
22
22
+1/4
10
01
)-1
0.0889
0.0889
= (-0.0209,-0.0209)

x3 = (0.0222,0.0222) + (-0.0209,-0.0209) = (0.00131,0.00131)
Вычислим значение функции в новой точке: f(x3) = 5
Поскольку f(x3) < f(x2), то λ=(1/4)/2 = 1/8
Итерация №4.
Значение градиента в точке x3: ▽f(x3) = (0.00523;0.00523)
Проверим критерий остановки:
|▽f(X3)| = 0.00739<0.1
загрузка...