§ 10.4. Метод Ньютона

1. Простейший вариант метода Ньютона и метод Ньютона с дроблением шага.

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

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

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

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

с таким выбором методом Ньютона.

Отметим, что ньютоновское направление является направлением спуска. В самом деле, в силу равенства (10.30) для верна формула Матрица положительно определена (это следует из положительной определенности матрицы Поэтому

Таким образом, условие (10.14) выполняется и действительно задает направление спуска.

Разлйчные варианты метода (10.31), (10.30) связаны с различными способами выбора шагов Заметим, что при выборе рассматриваемый метод в точности совпадает с методом Ньютона решения систем нелинейных уравнений, примененным к решению системы Отсюда — и название метода.

Простым следствием теоремы 7.3 о сходимости метода Ньютона решения систем нелинейных уравнений является следующая теорема.

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

метода (10.30), (10.31) при не выходит за пределы -окрестмости точки х и сходится к ней квадратично.

Замечание. Квадратичная скорость сходимости метода позволяет использовать простой практический критерий окончания:

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

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

Теорема 10.3. Пусть трижды непрерывно дифференцируемая в функция имеет точку минимума х и ее матрица Гессе положительно определена. при любом начальном приближении последовательность вычисляемая методом Ньютона с выбором сходится к х с квадратичной скоростью. Более тою, найдется номер По такой, что для всех по выполняется равенство

Замечание. Используют и другие способы выбора Например, иногда выбирают из условия где

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

Пример 10.4. Применим метод Ньютона (10.30), (10.31) с для поиска точки минимума функции с точностью Будем использовать критерий окончания итераций (10.32) и вести вычисления на -разрядной десятичной ЭВМ. Отметим, что минимальное и равное нулю значение функция достигает в точке Имеем

Возьмем за начальное приближение

1 итерация. Вычислим

Таким образом, при система (10.30) принимает следующий вид:

Решая ее, получаем . Далее в соответствии с формулой (10.31) полагаем Так как то вычисления следует продолжить далее.

Результаты следующих итераций приведены в табл. 10.1.

Таблица 10.1 (см. скан)

При критерий окончания выполняется и вычисления следует прекратить. Итак,

2. Понятие о квазиньютоновских методах.

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

Направление спуска в квазиньютоновских методах определяется как решение системы уравнений

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

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

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

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

применяемых на практике. Весьма интересное и содержательное обсуждение квазиньютоновских методов содержится в книгах [24], [32], [91].

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

3. Метод Ньютона и квааиныотоновские методы при наличии помех.

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

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