Метод Ньютона-Гаусса

Материал из MachineLearning.

Метод Ньютона-Гаусса - это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода - это так называемый метод Левенберга-Марквардта.

Содержание 1 Описание метода 2 Обоснование метода 3 Преимущества и недостатки метода 4 Литература

Описание метода

В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.

Под имеется ввиду следующий вектор-столбец:

Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Пусть - матрица Якоби для функции , то есть
, где из

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

Обоснование метода

Пусть необходимо найти экстремум функции многих переменных . Это равносильно нахождению точки . Если для решения этой задачи использовать итерационный метод Ньютона (метод касательных), то формула обновления для выглядит следующим образом:

Здесь под имеется ввиду матрица Гесса функции , то есть матрица вторых производных:

Когда рассматривается задача наименьших квадратов

градиент и матрица Гесса для функции принимают особый вид:


, где


Здесь под имеется ввиду матрица Гесса для функции ( i-ая компонента вектора ). - матрица Якоби для функции
Если использовать итерационный процесс Ньютона для минимизации , то формула для обновления будет следующая:

Метод Ньютона — Гаусса строится на предположении о том, что , то есть слагаемое доминирует над . Также такое приближение возможно при условии, что близко к 0. Это требование не соблюдается, если минимальные невязки велики, то есть если норма сравнима с максимальным собственным значением матрицы . В противном случае пренебрегаем и получаем итерационную процедуру с формулой для обновления :

Преимущества и недостатки метода

В стандартном итерационном методе Ньютона на каждой итерации требуется вычисление и обращение матрицы Гесса, что зачастую является достаточно сложным процессом. В методе Ньютона-Гаусса подобная необходимость отпадает, причем скорость сходимости также может достигать квадратичной,, хотя вторые производные и не учитываются. Также данный метод прост в реализации и присутствует в большинстве программных пакетов по прикладной математике. Тем не менее, в методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

Литература

1. Машинное обучение (курс лекций, К.В.Воронцов)
2. [1]
3. [2]
4. К.П. Ловецкий, Л.А. Севастьянов, М. В. Паукшто, О.Н. Бикеев. Математический синтез оптических наноструктур

---

Данная статья является непроверенным учебным заданием. Студент: Участник:DenisGKolev Преподаватель: Участник:Константин Воронцов Срок: 6 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.