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

Несколько иной метод перехода от произвольной к положительноопределенной матрице предложен в работах Левенберга [1351, Марквардта [1401, а также Гольдфельда и других авторов [871. В основу метода положено следующее свойство: если некоторая положительноопределенная матрица, то при достаточно большом матрица также будет положительно-определенной независимо от того, какова матрица Марквардт предложил задавать где В, определяется равенством Таким образом, в качестве здесь берется диагональная матрица с элементами на диагонали, равными абсолютным величинам диагональных элементов матрицы А (с заменой нулевых элементов на единицы). Следовательно, мы используем матрицу

и задаем шаг с т. е.

Отметим, что при слагаемое В? будет доминировать над А. Тогда выражение для шага приобретает вид

Поскольку положительно определена, то это чрезвычайно малый шаг в направлении уменьшения целевой функции. Достаточно большая величина всегда приведет к тому, что шаг окажется допустимым. С другой стороны, если очень мало, то приближается к направлению в методе Ньютона.

Марквардт в 1963 г. предложил следующий алгоритм выбора :

1) если то для начала положить, например, ;

2) при выполнении итерации вычислить

3) если принять и заменить на , где малое положительное число, скажем

4) если заменить на и перейти к операции 2. При невыполнении последнего условия произвести интерполяцию, т. е. найти значение достаточно малое для того, чтобы обеспечить (см. раздел 5.14). Принять

В рассмотренном алгоритме может потребоваться вычисление для нескольких значений на одной итерации. Этого можно избежать при замене операции на следующую:

4) найти значение достаточно малое для того, чтобы обеспечить (см. раздел 5.14). Принять Заменить на .

Еще один метод выбора описан в работе Смита и Шенно [178].

Вычисление может быть выполнено одним из двух способов.

(а) Решить систему линейных уравнений

Если на каждой итерации должны быть проведены расчеты при нескольких значениях , то соответствующее число раз должны быть решены и эти уравнения. Заметим, что если все диагональные элементы матрицы положительны, то матрицы и А идентичны за тем исключением, что диагональные элементы первой из них получены умножением соответствующих элементов на Если известно, что положительно-определенная матрица, как, например, в методе Гаусса (см. раздел 5.9), то для разрешения системы относительно можно применить метод разложения Холецкого (см. раздел А.5). Не лишено смысла начать решение с применения этого метода даже в тех случаях, когда отсутствует уверенность в положительной определенности упомянутой матрицы. Если в матрице будет найден отрицательный диагональный элемент, то вычисления по процедуре прерываются, значение увеличивается в 10 раз, формируется новая матрица и вновь начинаются расчеты по той же процедуре. Можно предложить модифицированную процедуру, в которой каждому столбцу матрицы ставится в соответствие свое значение Я. Если, например, отрицательный диагональный элемент был встречен в третьем столбце, то соответствующее Я увеличивается до тех пор, пока он не станет положительным. При этом процедура Холецкого может быть продолжена без возвращения к ее началу.

(б) Пусть уравнение описывает обратное шкалированное разложение матрицы А. Тогда можно легко убедиться в том, что выполняется равенство

Коль скоро разложение А получено, матрицу можно вычислить для любого числа значений Заметим, что мы можем ограничить свой выбор лишь значениями удовлетворяющими неравенству

Здесь нелишне будет напомнить, что в методе Марквардта шаг находится из условия минимизации квадратической аппроксимации функции

при ограничении

Другими словами, делается шаг в такую точку эллипсоида, заданного уравнением в которой функция достигает своего минимума.

Для проверки этого утверждения сформируем функцию Лагранжа:

Продифференцируем ее приравняем производную нулю:

и найдем из этого уравнения

Это решение находится в полном соответствии с равенством Выбор конкретного эллипсоида определяется значением , поскольку при подстановке равенства получается

Чем больше будет тем меньшим окажется с и тем меньшим по размерам будет эллипсоид ограничений Для того чтобы приступить к вычислениям по алгоритму, задается некоторый эллипсоид, размеры которого определяются уравнением при подстановке в него начального значения . Если соответствующий шаг не приведет к уменьшению целевой функции, это значит, что выбранный эллипсоид намного больше той области, в которой справедлива квадратическая аппроксимация, заданная выражением Увеличивая , можно сжать эллипсоид и повторить все сначала.

Метод Марквардта оказался очень надежным на практике. В задаче с плохим начальным] приближением из раздела 5.21, а также

в нескольких задачах раздела 5.23 метод Марквардта оказался более быстродействующим по сравнению с методами выбора направлений. С другой стороны, для ряда задач [13] получены прямо противоположные результаты. Очевидно, необходимы дальнейшие исследования в этой области.