Пусть $ f_{}(x) $ — полином с вещественными коэффициентами, $ \deg f \ge 2 $, и $ \lambda $ обозначает его корень, лежащий на интервале $ ]a,b[ $. Пусть, кроме того, $ f^{\prime}(x)\ne 0 $ на указанном интервале, тогда $ \lambda_{} $ — единственный корень полинома на $ ]a,b[ $. При произвольном $ x_0 \in ]a,b[ $ выпишем формулу Тейлора $$f(x)=f(x_0)+f'(x_0)(x-x_0)+\dots \ ,$$ ограничившись в ней двумя первыми слагаемыми. Вместо уравнения $ f_{}(x)=0 $ будем рассматривать его линейное приближение $ f(x_0)+f'(x_0)(x-x_0)=0 $. Утверждается, что достаточно часто (в смысле выбора точки $ x_{0} $) решение этого уравнения, т.е. точка $$ x_1= x_{0}-\frac{f(x_{0})}{f'(x_{0})} $$ лежит ближе к (неизвестному нам заранее) значению корня $ \lambda $, чем точка $ x_{0} $. Можно утверждать и большее: при подходящем выборе $ x_{0} $ итерационная последовательность $$ \left\{ x_j= x_{j-1}-\frac{f(x_{j-1})}{f'(x_{j-1})} \right\}_{j=1}^{\infty} $$ будет сходиться к $ \lambda_{} $ при $ j\to + \infty $.

Метод поиска вещественного решения уравнения $ f(x)=0 $ построением указанной последовательности известен как метод Ньютона или же (см. ☟ ПУНКТ) как метод каcательных.

Биографические заметки о Ньютоне ☞ ЗДЕСЬ.

Теорема 1. Если полином $ f_{}(x) $ не имеет кратных корней и последовательность $ \{x_j\}_{j=1}^{\infty} $ сходится к конечному пределу, то этот предел является корнем $ f_{}(x) $.

Доказательство. Пусть $$ \lim_{j\to + \infty} x_j = A , $$ тогда и $$\lim_{j\to + \infty} x_{j-1} = A . $$ По непрерывности $ f_{}(x) $ и $ f^{\prime}(x) $ будет выполнено $$\lim_{j\to + \infty} f(x_{j-1})= f(A) \ , \quad \lim_{j\to + \infty} f^{\prime}(x_{j-1})= f^{\prime}(A) \ , $$ и, по предположению, числа $ f(A) $ и $ f^{\prime}(A) $ не могут одновременно обращаться в нуль. Если бы число $ f^{\prime}(A) $ было равно нулю, то последовательность $ \{x_j\}_{j=1}^{\infty} $ была бы неограниченной, а у нее же, по предположению теоремы, существует конечный предел. Следовательно $ f^{\prime}(A)\ne 0 $. При переходе в равенстве $$ x_j= x_{j-1}-\frac{f(x_{j-1})}{f'(x_{j-1})} $$ к пределу при $ j\to + \infty $, равенство должно сохраниться: $$ A= A- \frac{f(A)}{f'(A)} \quad \Rightarrow \quad \frac{f(A)}{f'(A)}=0 \quad \Rightarrow \quad f(A)=0 \ .$$ ♦

Наша задача теперь заключается в подборе такого стартового (начального) значения $ x_{0} $, чтобы последовательность $ \{x_j\}_{j=1}^{\infty} $ сходилась к определенному корню полинома, например, лежащему на данном интервале $ [a,b] $. Нам потребуется следующий результат из математического анализа.

Теорема 2. Если функция $ F_{}(x) $ и ее производные $ F^{\prime}(x) $ и $ F^{\prime \prime}(x) $ непрерывны в $ ]a,b[ $, то для любых значений $ x_{} $ и $ x_{0} $ из этого интервала будет справедлива формула Тейлора с остаточным членом в форме Лагранжа:

$$ F(x)\equiv F(x_0)+F^{\prime}(x_0)(x-x_0)+ \frac{F^{\prime \prime}(c)}{2!}(x-x_0)^2 $$ где значение $ c_{} $ принадлежит интервалу $ ]x_0,x[ $ при $ x>x_0 $ или $ ]x,x_0[ $ при $ x<x_0 $.

Теорема 3. Если для $ f(x)\in \mathbb R[x] $ на интервале $ ]a,b[ $ выполнены условия:

а) $ f(a)f(b)<0 $;

б) $ f^{\prime}(x) $ и $ f^{\prime \prime}(x) $ не имеют корней на $ ]a,b[ $;

то при любом выборе $ x_{0} $ таком, что $$ \operatorname{sign} f(x_0) = \operatorname{sign} f^{\prime \prime}(x) $$ последовательность $ \{x_j\}_{j=1}^{\infty} $ монотонно сходится к единственному корню полинома $ f_{}(x) $, лежащему на $ ]a,b[ $.

Доказательство. Существование корня $ \lambda \in ]a,b[ $ гарантировано теоремой Больцано; его единственность на рассматриваемом интервале является следствием предположения б) и теоремы Ролля.

Для определенности, будем предполагать $ f^{\prime}(x)>0 $ и $ f^{\prime \prime}(x)>0 $ на $ ]a,b[ $, иначе говоря, функция возрастает и выпукла вниз; согласно правилу выбора начальной точки $ x_{0} $ мы должны взять ее из условия $ f(x_0)>0 $, т.е. ближе к правому концу интервала. Имеем, следовательно $ x_0>\lambda $. Докажем, что значение $ x_{1} $, вычисляемое по формуле $$ x_1= x_{0}-\frac{f(x_{0})}{f'(x_{0})} \ , $$ будет удовлетворять условиям $ \lambda < x_1 < x_0 $.

Правое из этих неравенств очевидно следует из формулы, определяющей $ x_{1} $: из $ x_{0} $ вычитается положительная величина. Для доказательства неравенства $ x_{1} > \lambda $ запишем для $ f_{}(x) $ формулу Тейлора с остаточным членом в форме Лагранжа: $$ f(x)\equiv f(x_0)+f^{\prime}(x_0)(x-x_0)+ \frac{f^{\prime \prime}(c)}{2!}(x-x_0)^2 \ . $$ Подставим вместо $ x_{} $ значение корня $ \lambda_{} $: $$ 0=f(x_0)+f^{\prime}(x_0)(\lambda-x_0)+ \frac{f^{\prime \prime}(c)}{2!}(\lambda-x_0)^2 \ , $$ перенесем первые два слагаемые в левую часть и поделим получившееся равенство на $ f^{\prime}(x_0) $: $$ \left(x_{0}-\frac{f(x_{0})}{f^{\prime}(x_{0})} \right) - \lambda = \frac{f^{\prime \prime}(c)}{2!\, f^{\prime}(x_{0})}(\lambda-x_0)^2 \ . $$ В левой части получили $ x_1 - \lambda $. По предположению, $ f^{\prime \prime}(c)>0 $ и $ f^{\prime}(x_{0})>0 $, следовательно правая часть неотрицательна. Итак, $ x_1 > \lambda $.

Совершенно аналогично доказывается, что $ \lambda < x_2 < x_1 $ и т.д. Последовательность $ \{x_j\}_{j=1}^{\infty} $ монотонно убывает и ограничена снизу. Такая последовательность всегда сходится, и ее предел должен принадлежать интервалу $ [\lambda, x_0] $. По доказанному в теореме $ 1_{} $ она сходится к какому-то корню полинома $ f(x) $, но тогда она сходится именно к $ \lambda_{} $, поскольку другого корня на $ [a,b] $ у полинома нет. ♦

При выполнении условий теоремы $3$ скорость сходимости последовательности метода Ньютона оценивается неравенством

$$ |x_j-\lambda|\le \frac{M}{2m} |x_{j-1}-\lambda|^2 ; \quad \mbox{здесь} \quad m= \min_{x\in [a,b]} | f^{\prime}(x)|, M= \max_{x\in [a,b]} | f^{\prime \prime}(x)| \, . $$

Пример. Найти положительный корень полинома $ x^5-4\, x -2 $ с точностью до $ 0.001 $.

Решение. На основании правила знаков Декарта делаем вывод, что $ f_{}(x) $ имеет положительный корень и этот корень единствен. Далее, $ f(1)<0,f(2)>0 $ и, на основании теоремы Больцано, этот корень принадлежит интервалу $ ]1,2[ $. Далее, $$f^{\prime}(x)=5\,x^4-4>0, f^{\prime \prime}(x)>0 \quad npu \quad x\in ]1,2[ ,$$ т.е. мы находимся точно в условиях случая, рассмотренного в доказательстве теоремы $ 3_{} $. Запускаем итерационную последовательность, полагая $ x_0=2 $: $$x_1 =x_0-\frac{x_0^5-4\, x_0 -2}{5\, x_0^4 -4}=\frac{65}{38} \approx 1.710526316 \ . $$ Далее, последовательное применение формулы метода Ньютона дает: $$ \begin{array}{lll} x_2 &= x_1- \displaystyle \frac{x_1^5-4\, x_1 -2}{5\, x_1^4 -4} =\frac{2399816418}{1537339039} &\approx 1.561019630 \ , \\ x_3 &= x_2- \displaystyle \frac{x_2^5-4\, x_2 -2}{5\, x_2^4 -4} & \approx 1.521115751 \ , \\ x_4 & & \approx 1.518522614 \ , \\ x_5 & & \approx 1.518512153 \ . \end{array} $$

Ответ. $ \lambda \approx 1.518 $.

Геометрическая интерпретация метода Ньютона заключается в следующем. Для определенности предположим, что $ f^{\prime}(x)>0,\, f^{\prime \prime}(x)>0 $ на $ ]a,b[ $. Возьмем $ x_{0} $ ближе к правому концу указанного интервала, т.е. пусть $ f(x_0)>0 $. Проведем касательную к графику функции $ y=f(x) $ в точке $ (x_0,f(x_0)) $: $$\frac{y-f(x_0)}{x-x_0}=f^{\prime}(x_0) $$ и найдем ее точку пересечения $ (x_1,y_1) $ с осью абсцисс.

Легко вычислить координаты этой точки: $$y_1=0,\ x_1=x_0 - \frac{f(x_0)}{f^{\prime}(x_0)} \ ;$$ иначе говоря, $ x_{1} $ определяется как раз по формуле метода Ньютона. Из рисунка видно (а в теореме $ 3_{} $ строго доказывается), что точка $ x_{1} $ лежит ближе к неизвестному нам значению корня $ \lambda_{} $ полинома $ f_{}(x) $, чем точка $ x_{0} $. Поэтому имеет смысл повторить процедуру: построить касательную к графику в точке $ (x_1,f(x_{1})) $, найти ее пересечение $ (x_{2},y_2) $ с осью абсцисс и т.д.

В конце концов, монотонно убывающая и ограниченная снизу последовательность точек $ x_0,x_1,x_2,\dots $ попадет в сколь угодно малую окрестность $ \lambda_{} $. Эти геометрические соображения обосновывают и другое название метода Ньютона; он также называется методом касательных.

Выбор стартового значения ближе к правому концу интервала обеспечивает монотонное убывание последовательности $ \{x_j\}_{j=1}^{\infty} $ также в случае когда на этом интервале имеют место неравенства $ f^{\prime}(x)<0 $ и $ f^{\prime \prime}(x)<0 $; в двух же оставшихся случаях $$ f^{\prime}(x)<0,\, f^{\prime \prime}(x)>0 \quad u \quad f^{\prime}(x)>0,\, f^{\prime \prime}(x)<0 $$ последовательность будет сходиться к $ \lambda_{} $, монотонно возрастая, если выбрать $ x_{0} $ ближе к левому концу интервала.

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

Это порождает более общую задачу оценки чувствительности корней, т.е. оценки их изменения при некотором возмущении коэффициентов полинома. Обсуждение этой задачи ☞ ЗДЕСЬ.

Методу Ньютона можно дать интерпретацию, отличную от изложенной в пункте МЕТОД КАСАТЕЛЬНЫХ. Если выполнены условия теоремы $ 3 $, то на интервале $ [a,b] $ существует обратная функция к $ y=f(x) $, т.е. функция $ x=\varphi(y) $ такая что $$ f(\varphi(y)) \equiv y \quad \mbox{ или, эквивалентно } \quad \varphi(f(x)) \equiv x \, . $$ Если эту функцию удается построить, то поиск корня уравнения $ f(x)=0 $ на интервале $ [a,b] $ сведется к вычислению значения $ \varphi (0) $.

Проблема состоит в том, что как правило, представить обратную функцию в виде конечной комбинации сравнительно простых функций не представляется возможным даже для полиномиальных $ f(x) $. Но, по крайней мере, для таких функций можно представить обратную функцию в виде ряда Тейлора в окрестности некоторой точки $ x_0 \in [a,b] $: $$ \varphi(y)=x_0+ B_1(y-f(x_0))+B_2(y-f(x_0))^2+ \dots $$ при $$ B_1=\frac{1}{f^{\prime}(x_0)}\ , \ B_2 = - \frac{f^{\prime \prime}(x_0)}{2[f^{\prime}_x(x_0)]^3}\ , B_3=\frac{3\,[f^{\prime \prime}(x_0)]^2- f^{\prime}_x(x_0)f^{\prime \prime \prime}(x_0) }{6[f^{\prime}_x(x_0)]^5}\ , \ \dots $$ Бесконечного количества слагаемых мы не вычислим, но если ограничиться первыми двумя, то получим линейное приближение обратной функции $$ \varphi(y)\approx x_0+ \frac{1}{f^{\prime}(x_0)}(y-f(x_0)) \, $$ из которого получаем приближение корня первого порядка $$ \varphi(0) \approx x_0 - \frac{f(x_0)}{f^{\prime}(x_0)} \ , $$ т.е. в точности формулу первой итерации метода Ньютона.

Если взять три слагаемых разложения, то приближение корня второго порядка получается в виде $$ \varphi(0) \approx x_0 - \frac{f(x_0)}{f^{\prime}(x_0)} - \frac{f^2(x_0)f^{\prime \prime}(x_0)}{2[f^{\prime}(x_0)]^3} \ , $$ и т.д. Посчитаем итерации, задаваемые этой функцией, $$ \left\{ x_{j}= x_{j-1} - \frac{f(x_{j-1})}{f^{\prime}(x_{j-1})} - \frac{f^2(x_{j-1})f^{\prime \prime}(x_{j-1})}{2[f^{\prime}(x_{j-1})]^3} \right\}_{j=1}^{\infty} $$ необходимые для решения примера из пункта МЕТОД НЬЮТОНА.

Пример. Найти корень полинома $ x^5-4\, x -2 $ на интервале $[1,2] $ с точностью до $ 0.001 $.

Решение. При выборе $ x_0 =2 $ требуемая точность достигается за три итерации $$ x_1 = \frac{22255}{13718} \approx 1.622321, \ x_2\approx 1.521381, \ x_3 \approx 1.518512 \, . $$

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

Геометрическая идея, лежащая в основе метода Галлея¹⁾, обобщает идею метода касательных. К графику функции $ y=f(x) $ строится гипербола вида $$ (x-\alpha)(y-\beta)=k \ , $$ имеющая в точке $ (x_0,f(x_0)) $ касание с графиком второго порядка, т.е. значения функции $$ y=\beta+\frac{k}{x-\alpha} \ , $$ а также значения ее первой и второй производных в точке $ x_0 $ совпадают с соответствующими значениями для функции $ f_{}(x) $. В качестве очередного приближения $ x_{1} $ к неизвестному корню $ \lambda_{} $ берется точка пересечения гиперболы с осью абсцисс. $$ \left\{x_j=x_{j-1}- \frac{f(x_{j-1})f^{\prime}(x_{j-1})}{\left[f^{\prime}(x_{j-1})\right]^2-\frac{1}{2}f(x_{j-1})f^{\prime \prime}(x_{j-1})} \right\}_{j=1}^{\infty} \ . $$

Задача. Для заданного натурального числа $ B_{} $ установить является ли оно полным квадратом и в этом случае определить $ \sqrt{B} $.

Следующий результат получается «округлением» итераций метода Ньютона, примененного к уравнению $ x^2-B=0 $.

Теорема. Пусть $ B_0 $ — произвольное целое такое, что $ B_0^2>B $. Последовательность

$$ B_j = \begin{array}{c} \left\lfloor \begin{array}{c} B_{j-1}+ \left\lfloor \displaystyle \frac{B}{B_{j-1}} \right\rfloor_{} \\ \hline 2 \end{array} \right\rfloor \\ \end{array} \quad npu \ \ j\in \{1,2,\dots \ \} \ , $$ монотонно убывая, сойдется за конечное число шагов к значению $ \left\lfloor\sqrt{B} \right\rfloor $, если только число $ B+1 $ не является полным квадратом. Здесь $ \lfloor \ \ \ \rfloor $ означает целую часть числа.

Доказательство ☞ ЗДЕСЬ.

Формально ничто не мешает нам применить последовательность метода Ньютона для поиска мнимых корней полинома $ f_{}(x) $. Можно доказать комплексный аналог теоремы $ 3_{} $ , а также показать сходимость итерационной последовательности к конкретному корню полинома при условии, что стартовое (начальное) значение выбирается достаточно близко к искомому корню. Интересно посмотреть на поведение последовательности уже для самых простых случаев. Пусть, например, $$ f(z)=z^3-1 \, , $$ т.е. наша задача заключается в поиске трех корней кубических из $ 1_{} $: $$1,\quad -\frac{1}{2} + \mathbf i \frac{\sqrt{3}}{2}\ ,\quad -\frac{1}{2} - \mathbf i \frac{\sqrt{3}}{2} \ . $$ Комплексный вариант последовательности метода Ньютона: $$ \left\{z_j = \frac{2\,z_{j-1}^3+1}{3\,z_{j-1}^2} \right\}_{j=1}^{\infty} $$ при задании стартового значения $ z_{0} $ «выведет» нас при $ j\to \infty $ к какому-то значению корня. Итак, вся комплексная плоскость может быть поделена на три «области притяжения» каждого из корней. Раскрасим эти множества в разные цвета. Какова будет граница между этими областями? — Оказывается, эта граница имеет так называемую фрактальную структуру; и каждая граничная точка любой области является также граничной для двух других областей²⁾.

.

Если начальную точку $ z_0 $ выбрать на этой границе, то последовательность метода Ньютона будет бесконечно долго скакать по ней, не сходясь ни к какому корню. При выборе $ z_0 $ близко к границе, мы, теоретически, должны получить последовательность, сходящуюся к какому-то корню. Однако ошибки округления, накапливающиеся с каждой итерацией, могут снова привести к непредсказуемости ни качества сходимости (к конкретному корню) ни количества итераций, требуемых для достижения заданной точности.

Проблемы сходимости комплексного варианта метода Ньютона, отмеченные в предыдущем пункте, наследуются и обобщением метода Ньютона для задачи решения системы нелинейных уравнений с несколькими неизвестными. Действительно, задача поиска комплексных корней уравнения $ z^3-1=0 $ эквивалентна поиску вещественных решений системы уравнений $$ x^3-3\, xy^2-1=0, \ 3\, x^2y-y^3=0 \, . $$

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

$$ f(x,y)=0, g(x,y)=0 $$ при $ f, g $ — произвольных полиномах с вещественными коэффициентами обсуждается ☞ ЗДЕСЬ

☞ ЗДЕСЬ

[1]. Березин И.С., Жидков Н.П. Методы вычислений. Т.2. М.Физматгиз. 1960

[2]. Uspensky J.V. Theory of Equations. New York. McGraw-Hill. 1948