Метод Ньютона

Рассмотрим теперь применение метода Ньютона для решения задачи (1.1.1). Его можно отнести к методам второго порядка, поэтому одним из условий его использования является принадлежность функции f (x) к классу дважды дифференцируемых функций.

Метод представляет собой многошаговый итерационный процесс поиска решения в общем случае нелинейного уравнения

f^¢(x) = 0. (1.4.1)

Как уже было отмечено, решение уравнения (1.4.1) соответствует стационарной точке функции f (x), следовательно, в этой точке выполнены необходимые условия экстремума. Для того чтобы решение (1.4.1) соответствовало точке локального минимума функции, в этой точке должны быть выполнены соответствующие достаточные условия (см. § 1.1).

В процессе работы метода Ньютона начиная с точки х ⁽⁰⁾ начального приближения к решению (1.4.1) строится (в общем случае бесконечная последовательность точек х ⁽⁰⁾, х ⁽¹⁾, х ⁽²⁾, …, х ^(k)…) посредством вычисления каждого очередного элемента последовательности по формуле

x ^{(k +1)} = х ^(k) – f^¢ (х ^(k)) / f^¢¢ (х ^(k)), k = 0, 1, 2, … (1.4.2)

Для того чтобы метод сходился, в некоторой окрестности искомой точки должны быть выполнены требования, предъявляемые к свойствам функции f (x), а также к выбору начального приближения х ⁽⁰⁾.
С практической точки зрения рекомендуется выбирать х ⁽⁰⁾ достаточно близко к х ^* – искомому решению. Для работы метода необходимо также, чтобы f^¢¢ (х ^{( k )}) ¹ 0, " k.

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

Рекуррентное соотношение (1.4.2) получено на основании следующих соображений.

В общем случае нелинейная функция f^¢ (x) аппроксимируется
в окрестности точки х ^{( k )} линейной функцией j(x):

j(x) = f ^¢ (х ^(k)) + f ^¢¢ (х ^(k))(x – х ^(k)). (1.4.3)

Затем ищется решение линейного уравнения

j(x) = f^¢ (х ^(k)) + f ^¢¢ (х ^(k))(x – х ^(k)) = 0, (1.4.4)

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

x = х ^(k) – f^¢ (х ^(k))/ f^¢¢ (х ^(k)). (1.4.5)

Теперь рекуррентное соотношение (1.4.2) можно получить из (1.4.5), если в правой части последнего вместо x записать x ^{(k + 1)}.

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

Запишем метод Ньютона в более формализованном виде. Пусть f (x) – дважды дифференцируемая функция в некоторой области W Ì X, в которой выполнены условия сходимости метода Ньютона и х ⁽⁰⁾ Î W; достаточно малое число d > 0 задает точность отделения от нуля значений f^¢ (x). Тогда метод Ньютона для решения задачи (1.1.1) можно записать в виде следующего алгоритма.

1. Задать х ⁽⁰⁾ Î W, d > 0; положить k = 0.

2. Вычислить f ^¢ (х ^(k)), f ^¢¢ (х ^(k)).

3. Если÷ f ^¢ (х ^(k))ç £ d, то перейти к выполнению п. 6.

4. Вычислить x ^{(k + 1)} = х ^(k) – f ^¢ (х ^(k)) / f ^¢¢ (х ^(k)).

5. Положить k: = k + 1. Перейти к выполнению п. 2.

6. Положить х ^*: = х ^(k). Процесс завершен.

Критерием окончания работы данного алгоритма является близость
к нулю значения f ^¢ (х ^(k)). Наряду с этим критерием могут быть использованы и другие (это определяется внешними требованиями к работе алгоритма и характером задачи), например близость к нулю разности двух последних членов последовательности .

Результаты работы метода Ньютона удобно отображать в табличной форме (табл. 1.4.1).

Таблица 1.4.1

Номер итерации	х ( k )	f ¢ (х (k))	f ¢¢ (х (k))	f ¢ (х (k))/ f¢¢ (х (k))
…	…	…	…	…
k

Отметим характерные особенности метода Ньютона:

– применяется только к дважды (и более) дифференцируемым функциям;

– требует вычисления на каждой итерации производных первого
и второго порядков минимизируемой функции f (x). Отсюда следует,
что метод Ньютона характеризуется сравнительно большой трудоемкостью выполнения каждой итерации.

– в процессе работы строится последовательность точек х ⁽⁰⁾, х ⁽¹⁾,
х ⁽²⁾,…, х ^(k), …, которая при выполнении условий сходимости будет сходиться к точке х ^* – локальному минимуму минимизируемой функции f (x);

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

– при выполнении условий сходимости скорость сходимости метода квадратическая;

– для квадратических функций решение находится за один шаг.

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