7.3. Метод Ньютона-Гаусса и его модификации

Специфический вид суммы квадратов отклонений позволяет построить методы минимизации, более эффективные, чем общие методы. Основой является метод Ньютона — Гаусса.

Найдем первые и вторые производные суммы квадратов отклонений:

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

а) нелинейная регрессия (7.2) имеет невысокий порядок нелинейности: вторые производные принимают не очень большие значения;

б) гессиан рассматривается в достаточно малой окрестности минимизирующего вектора а, для которого приближение к у достаточно хорошо, т. е. величины близки к нулю.

С учетом условий а) и б) приближенно можно считать поэтому

Общий метод минимизации, метод Ньютона, предлагает двигаться из данного начального приближения к следующему по правилу

где антиградиент, равный который в матричной форме записывается в виде Окончательно (7.16) переписывается следующим образом:

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

Формула (7.17) может быть получена также из других соображений. Пусть приближение известно; разложим функцию регрессии в окрестности в ряд Тейлора до линейных членов:

В матричном виде это равенство может быть переписано как

поэтому регрессия (7.2) линеаризуется

или

Применяя МНК к линеаризованной регрессии (7.18), найдем следующее значение вектора приближения:

которое совпадает с ранее полученным (7.17).

Метод Ньютона-Гаусса является в некотором смысле интерполяцией градиентного метода и метода Ньютона. Действительно, как и в градиентном методе, здесь вычисляются только первые производные; таким образом, время,

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

Длина шага в методе Ньютона-Гаусса (7.17) равна единице. Метод будет более гибким, если длину шага сделать переменной. Таким образом может быть построен модифицированный метод Ньютона-Гаусса:

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

Приведем теорему, с помощью которой можно легко получать условия сходимостей тех или иных методов.

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

где выбрано тем или иным образом. В оптимальном случае

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

Предположим, итерационный процесс, задаваемый отображением удовлетворяет соотношению

Тогда, если выбирать в интервале

где любое число: задается равенством (7.25)), то для всех предельных точек х последовательности имеемду

Доказательство теоремы приводится в параграфе 7.81. Сделаем некоторые замечания. Очевидно, в силу условий теоремы множество является замкнутым и ограниченным (см. теорему 7.1), и минимум функции достигается. В силу непрерывности гессиана функции и непрерывности максимального характеристического числа матрицы от своих элементов существует

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

Далее, из доказательства теоремы следует, что если выбирать из условия (7.22), то (7.23) достаточно для выполнения теоремы.

С помощью теоремы 7.2 легко проверяется сходимость различных методов. Для примера рассмотрим градиентный метод. Здесь поэтому условие (7.23) автоматически выполняется. Если отыскивается по правилу (7.22), то сходимость градиентного метода к стационарным точкам следует из теоремы 7.2. Допустим теперь, что в градиентном методе Найдем условия сходимости такого метода. Выражение (7.24) переписывается следующим образом:

или Ясно, что если то значение существует, неравенство (7.24) выполняется, и градиентный метод сходится.

Выясним условия сходимости итерационных методов минимизации суммы квадратов отклонений. Начнем с метода Ньютона-Гаусса (7.17). В [17] предлагаются условия сходимости метода Ньютона-Гаусса, однако они трудно проверяемы и завышены.

Как и ранее, будем считать, что матрица имеет полный ранг, таким образом, матрица положительно определена для всех Обозначим

В методе Ньютона — Гаусса Докажем сначала, что для этого метода выполняется условие (7.23). Обозначим

Тогда, как легко показать,

Но

т. е. в качестве можно взять отношение

Так же, как в градиентном методе, для существования достаточно, чтобы

Можно показать, что

поэтому условие (7.26) переписывается как

На основе (7.27) можно сделать вывод: если нелинейные регрессии «не очень нелинейны» не велико), а сингулярность матрицы не очень велика достаточно велико), то метод (7.17) сходится к стационарным точкам. Этот вывод полностью подтверждается на практике. В [87] предлагается другой критерий сходимости метода Ньютона — Гаусса:

где а — оценка МНК, минимизирующая ; К — число, имеющее ту же природу, что и Условие сходимости (7.28) нам кажется несколько искусственным, поскольку значение неизвестно, его то и требуется найти.

Не представляет труда выяснение условий сходимости модифицированного метода Ньютона-Гаусса (7.19). Если на минимизирует вдоль направления (7.20), то метод (7.19) сходится к стационарным точкам. Сходимость в (7.19) будет выполняться, если выбирать на интервале

где некоторое выбранное заранее положительное число, 1/2; оценка сверху максимального гессиана на 50. В частности, если , то

X. Хартли [121] для выбора предложил следующую процедуру. Вдоль выбранного направления в методе Ньютона-Гаусса аппроксимируем сумму квадратов отклонений параболой. Для этого подсчитаем значение для (метод Ньютона-Гаусса). Нам известно Проведем через полученные три точки параболу Найдем ее коэффициенты. Очевидно, так как парабола проходит через точку Далее,

и Отсюда легко найти Имеем

Как известно, парабола принимает минимальное значение при Подставляя полученные значения для получим:

При приближении к оценке МНК, как правило, стремится к 1. Это и понятно, так как говорит о том, что вблизи минимизируемого вектора хорошо аппроксимируется квадратичной функцией, для которой является оптимальным.

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

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

Очевидно, если ограниченное множество, то а

Упражнение 7.3

(см. скан)