5.4.2. Модифицированный метод Ньютона

Процедура Коши основана на тейлоровской аппроксимации функции первого порядка, на линейной аппроксимации. Такая аппроксимация в точке имеет вид

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

Процедура Ньютона распространяет идею Коши дальше на один шаг и использует аппроксимацию второго порядка или квадратичную аппроксимацию

Поведение функции при подходе к подходящей точке.

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

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

Допустим, что имеется разложение в ряд Тейлора в точке где близка к х. В этом разложении вследствие того, что близко к нулю, начинают, доминировать члены второго порядка. При этом вблизи X отдельные компоненты градиента, так как они близки к нулю, могут осциллировать, становясь положительными и отрицательными. Таким образом, направление, определяемое градиентом, может меняться очень быстро. А это значит, что вблизи оптимальной точки линейная аппроксимация ведет себя плохо, в то время как квадратичная аппроксимация более устойчива.

Квадратичные аппроксимации. Процедура Ньютона — типичный представитель методов, использующих квадратичные аппроксимации. Чтобы объяснить метод, допустим, что представляет собой квадратичное приближение к в точке

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

Отсюда, предполагая, что матрица обратима, получаем

Видно, что вектор направления в точке указывает направление в ту точку х, которая оптимизирует квадратичную аппроксимацию

В общем случае неквадратична. Однако благодаря тому, что правая часть (5.6) является квадратичной аппроксимацией в точке направление является хорошим направлением для поиска больших значений Метод Ньютона использует это направление и отображение для определения лучшей точки.

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

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

Поскольку доказательство сходимости аналогично доказательству для случая Коши, она оставляется читателю в качестве упражнения (упр. 1).