1.1.9 Метод Марквардта
Метод Марквардта (метод Ньютона с переменной матрицей), повторяет метод Ньютона. Отличие заключается в том, что точки строятся по закону:
где
- последовательность чисел (>0), обеспечивающих положительную определенность матрицы . Обычно назначается как минимум на порядок больше, чем самый большой элемент матрицы .Алгоритм метода:
1) Задается начальная система точек (многогранник), включающая в себя
точку:для функции 2-х переменных задается три начальные точки:
2) Вычисляется значение функции во всех точках многогранника и выбирается:
лучшая точка
: (здесь - номер итерации, - номер точки) худшая точка :Далее заданная система из
точки перестраивается, для этого:3) Строится центр тяжести системы заданных точек за исключением худшей:
(для функции 2-х переменных точка
- середина отрезка, соединяющего точки за исключением худшей)4) Выполняется операция отражение худшей точки через центр тяжести:
здесь
- параметр отражения (рекомендуемое значение ).Рисунок 1.11. Отражение
5) Формируется новая система точек (многогранник). Для этого в точке
вычисляется значение функции, полученное значение сравнивается с :если
выполняется операция растяжение:Рисунок 1.12. Растяжение
здесь
- параметр растяжения (рекомендованное значение )При этом если
, то в новой системе точек точка будет заменена на , если же , то в новой системе точек точка будет заменена на- если
выполняется операция сжатие:Рисунок 1.13. Сжатие
здесь
- параметр сжатия (рекомендованное значение ).При этом если
, то в новой системе точек точка будет заменена на , если же , то в новой системе точек точка будет заменена на .- если
выполняется операция редукции: при этом формируется новый многогранник, содержащий точку с уменьшенными вдвое сторонами:Рисунок 1.14. Редукция
Т.о. в результате выполнения этого пункта алгоритма формируется новая система точек (многогранник), причем в случае возникновения операций растяжения и сжатия перестраивается только одна точка -
, в случае возникновения операции редукции – все точки, за исключением .6) Процедура 2)-5) повторяется до выполнения критерия окончания счета.
Основной критерий окончания метода:
Дополнительные критерии окончания метода:
- при выполнении предельного числа итераций:
при однократном или двукратном одновременном выполнении двух условий:
,
где
- малое положительное число.Алгоритм работы метода Нелдера-Мида схематически изображен на рис. 1.15
Рисунок 1.15. Диаграмма работы метода Нелдера-Мида
Алгоритм метода:
1) Задается начальная точка
и начальное значение параметра2) Строится система пробных точек (обычно 5-10 точек):
здесь
- номер итерации, - случайный вектор единичной длины, - номер пробной точки.Построенные пробные точки оказываются лежащими на гиперсфере радиуса
(в случае двух переменных – на окружности радиуса ).3) Для каждой пробной точки вычисляется значение функции
и выбирается наилучшая , для которой . Выбор может осуществляться как автоматически, так и при участии пользователя.4) Проверяется условие:
· если условие выполнено, то система пробных точек считается удачной, далее возможно два продолжения алгоритма:
4.1)
4.2) в направлении, соединяющем точки
и делается ускоряющий шаг:в этом случае, если оказывается, что
, принимаетсяРисунок 1.16. Удачная система пробных точек
- если условие не выполняется, делается попытка построить новую удачную систему пробных точек. если при этом число неудачных попыток достигает некоторого заданного числа
, текущий радиус уменьшается (автоматически или пользователем).