Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 5.4.2. Модифицированный метод НьютонаПроцедура Коши основана на тейлоровской аппроксимации функции первого порядка, на линейной аппроксимации. Такая аппроксимация в точке имеет вид
Градиент является хорошим направлением для максимизации линейной аппроксимации, и, так как линейная аппроксимация довольно точная, особенно в окрестности направление градиента является выгодным для увеличения значения функции Процедура Ньютона распространяет идею Коши дальше на один шаг и использует аппроксимацию второго порядка или квадратичную аппроксимацию Поведение функции при подходе к подходящей точке. Квадратичные аппроксимации не только точнее линейных, но их достоинство возрастает по мере приближения к подходящей точке Подходящая точка для процедуры Ньютона определяется как точка в которой точно так же, как и для процедуры Коши. Если использовать разложение в ряд Тейлора функции в подходящей точке х, то
где - матрица Гесса вторых частных производных в точке х. Обратите внимание, что здесь отсутствует линейный член, так как в точке Допустим, что имеется разложение в ряд Тейлора в точке где близка к х. В этом разложении вследствие того, что близко к нулю, начинают, доминировать члены второго порядка. При этом вблизи X отдельные компоненты градиента, так как они близки к нулю, могут осциллировать, становясь положительными и отрицательными. Таким образом, направление, определяемое градиентом, может меняться очень быстро. А это значит, что вблизи оптимальной точки линейная аппроксимация ведет себя плохо, в то время как квадратичная аппроксимация более устойчива. Квадратичные аппроксимации. Процедура Ньютона — типичный представитель методов, использующих квадратичные аппроксимации. Чтобы объяснить метод, допустим, что представляет собой квадратичное приближение к в точке
Если приближение было бы вогнутой функцией, то необходимым и достаточным условием того, чтобы х максимизировал на было бы или после дифференцирования Отсюда, предполагая, что матрица обратима, получаем
Видно, что вектор направления в точке указывает направление в ту точку х, которая оптимизирует квадратичную аппроксимацию В общем случае неквадратична. Однако благодаря тому, что правая часть (5.6) является квадратичной аппроксимацией в точке направление является хорошим направлением для поиска больших значений Метод Ньютона использует это направление и отображение для определения лучшей точки. Таким образом, процедура Ньютона идентична процедуре Коши, за исключением того, что вместо используется направление . В частности, в методе Ньютона для получения направления используется отображение
где -обратная матрица вторых частных производных вычисленных в точке х. Тогда . Далее мы полагаем, что непрерывна и отрицательно определена. Под отрицательной определенностью подразумевается, что для любого Поскольку доказательство сходимости аналогично доказательству для случая Коши, она оставляется читателю в качестве упражнения (упр. 1).
|
1 |
Оглавление
|