Кириченко В. А.

‍,

Тиморин В. А.

Метод НьютонаКириченко В. А., Тиморин В. А. Метод Ньютона // Квант. — 2025. — № 9. — С. 11‍—‍21.‍‍

Сейчас он изучал извлечение квадратного корня из двух. Он ни разу не видел ничего подобного, и это его восхищало и одновременно тревожило. «Это... это потрясающе», — бормотал он. Процедура поражала как действенностью, так и простотой. Аристомах исходил из обыкновенной дроби, которая представляла собой приближение к корню из двух: $\dfrac75$‍.‍ Затем перевернул дробь, превратив в обратную $\left(\dfrac57\right)$‍‍ и умножил на два $\left(\dfrac{10}7\right)$‍.‍ Полученная дробь была ещё одним приближением к корню; Аристомах полагал, что лучшим результатом будет промежуточная точка между двумя приближениями, и он находил полусумму. Получив результат, повторил процесс. Метод прост: удвоить обратную дробь и найти полусумму. Результат потрясает.

Маркос Чикот. «Убить Пифагора»

Как посчитать число $\bm{\sqrt2}$‍‍ с десятью знаками после запятой без калькулятора

Аристомах — легендарный ученик Пифагора, именно ему приписывают открытие, что корень из двух — это иррациональное число. В рамках древнегреческой терминологии, его результат ближе к геометрии, чем к алгебре. Он открыл, что диагональ квадрата и его сторона несоизмеримы. Это несчастное открытие поставило крест на первоначальной идее Пифагора о том, что миром правят натуральные числа. За такое низвержение основ, согласно легенде, коллеги пифагорейцы подвергли Аристомаха линчеванию. Сюжет получил неожиданную интерпретацию в недавнем историческом детективе Маркоса Чикота «Убить Пифагора». Обязательно прочтите его после того, как вам исполнится 18 лет. Сейчас, впрочем, речь пойдёт не об иррациональности, а о том, как быстро посчитать число $\sqrt2$‍‍ с очень высокой точностью. Речь в эпиграфе как раз об этом.

Начнём с самых очевидных оценок сверху и снизу: $1\lt\sqrt2\lt2$‍.‍ Аристомах у Маркоса Чикота начинал с $\dfrac75$‍,‍ но это не самое очевидное приближение — чтобы его получить, уже нужно что-то посчитать. Основная идея состоит в следующем: если уже получено два приближения, одно сверху и одно снизу, то мы можем взять полусумму и надеяться, что таким образом получится лучшее приближение. Иными словами, если $a\lt\sqrt2\lt b$‍,‍ то следующим приближением будет $\dfrac{a+b}2$‍.‍ Это очередное приближение — обозначим его через $c$‍‍ — приближает корень с одной стороны (либо сверху, либо снизу), но тогда $\dfrac2c$‍‍ является приближением с противоположной стороны. Таким образом, если мы начали с пары чисел $\{a,b\}$‍,‍ приближающих число $\sqrt2$‍‍ с обеих сторон, то следующей парой можно взять $\left\{\dfrac{a+b}2,\dfrac4{a+b}\right\}$‍‍ и это новое приближение, вообще говоря, лучше старого. Haпример, если изначально $ab=2$‍,‍ то мы заменяем числа $a$‍‍ и $b$‍‍ их средним арифметическим и средним гармоническим: оба средних лежат на отрезке $[a;b]$‍,‍ и тем самым получается меньший отрезок $[a',b']$‍,‍ по-прежнему содержащий искомый корень. Кроме того, соотношение $ab=2$‍‍ влечёт $a'b'=2$‍.‍ Улучшение можно итерировать, т. е. повторять тот же самый процесс до тех пор, пока качество приближения не станет удовлетворительным.

Положим $$ a_1=1,\quad b_1=2,\quad a_{n+1}=\dfrac{a_n+b_n}2,\quad b_{n+1}=\dfrac4{a_n+b_n}. $$ Нетрудно подсчитать значения $a_n$‍,‍ $b_n$‍‍ для нескольких первых $n$‍.‍ Это можно проделать даже руками, без калькулятора. Выпишем результаты вычисления в виде таблицы: $$ \def\|{\vphantom{\dfrac{\dfrac00}{\dfrac00}}} \begin{array}{|c|c|c|c|c|c|} \hline \vphantom{\dfrac00}n&1&2&3&4&5\\ \hline \|a_n&1&\dfrac32&\dfrac{17}{12}&\dfrac{577}{408}&\dfrac{665\,857}{470\,832}\\ \hline \|b_n&2&\dfrac43&\dfrac{24}{17}&\dfrac{816}{577}&\dfrac{941\,664}{665\,857}\\ \hline \end{array} $$ Оценка точности полученных приближений основана на том, что корень всегда лежит между $a_n$‍‍ и $b_n$‍‍ — таким образом, величина погрешности оценивается сверху расстоянием между $a_n$‍‍ и $b_n$‍.‍ Исходя из этих соображений, получаем, что уже четвёртое приближение даёт пять верных десятичных знаков, а пятое приближение — все одиннадцать. Вообще, можно показать, что сходимость чрезвычайно быстрая. Число верных десятичных знаков, грубо говоря, удваивается на каждом шаге.

Заметим, что по определению $b_n=\dfrac2{a_n}$‍,‍ и поэтому достаточно рассматривать одну последовательность $a_n$‍.‍ Эту последовательность можно задать рекуррентным соотношением $$ a_1=1,\quad a_{n+1}=\dfrac{a_n}2+\dfrac1{a_n}. $$

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

Пусть мы хотим найти решение $x_0$‍‍ уравнения $f(x)=0$‍‍ и пусть у нас есть начальное приближение $x_1$‍‍ к искомому корню $x_0$‍.‍ Вообще говоря, метод работает только в том случае, если мы достаточно хорошо угадали с начальным приближением. Если функция $f$‍‍ дифференцируемая, то около точки $x_1$‍‍ значение $f(x)$‍‍ может быть записано как $$ f(x)=f(x_1)+f'(x_1)\,(x-x_1)+\ldots, $$ где $f'(x_1)$‍‍ — производная в точке $x_1$‍,‍ а многоточие обозначает члены, малые по сравнению с $x-x_1$‍.‍

Рассмотрим линейную функцию от $x$‍‍ $$ g(x)=f(x_1)+f'(x_1)\,(x-x_1). $$ В курсе математического анализа доказывается, что эта функция лучше всех остальных линейных функций приближает функцию $f$‍‍ в окрестности точки $x_1$‍.‍ Коэффициенты $f(x_1)$‍,‍ $f'(x_1)$‍‍ этой функции — числа, которые зависят от $x_1$‍,‍ но не зависят от $x$‍.‍ Производная $f'(x_1)$‍,‍ таким образом, это угловой коэффициент наилучшего линейного приближения.

Идея метода Ньютона проста, как всё гениальное. Функция $f$‍‍ может быть очень сложной — настолько сложной, что непонятно будет даже, как можно приступить к явному решению уравнения. С другой стороны, любое линейное уравнение нетрудно решить явно, а функцию можно, с некоторой точностью, заменить её линейным приближением. Например, если очередное приближение $x_n$‍‍ уже получено на $n$‍‍-м шаге, то следующим шагом следует заменить нелинейное уравнение $f(x)=0$‍‍ линейным уравнением $$ f(x_n)+f'(x_n)\,(x-x_n)=0. $$ Последнее оказывается достаточно близким к первому, если $x_n$‍‍ близко к $x_0$‍.‍ Решение линейного уравнения обозначим через $x_{n+1}$‍‍ и продолжим процесс по той же схеме. Получим последовательность $x_n$‍,‍ удовлетворяющую рекуррентному соотношению $$ x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}. $$ Обозначим через $N_f$‍‍ функцию, определённую формулой $$ N_f(z)=z-\dfrac{f(z)}{f'(z)}. $$ Эта функция зависит от $f$‍,‍ что и отражено в обозначении; она называется отображением Ньютона для $f$‍.‍ Нахождение приближений к корню уравнения $f(x)=0$‍‍ сводится, благодаря методу Ньютона, к многократному применению одной и той же операции $$ z\mapsto N_f(z). $$ Если функция $f$‍‍ задана простой формулой, то и $N_f$‍‍ не слишком сложна. Скажем, если $f$‍‍ — многочлен, то $N_f$‍‍ — рациональная функция, т. е. отношение двух многочленов. Для функции $f(x)=x^2-2$‍‍ можно проверить, что итерирование отображения $N_f$‍‍ даёт ту самую последовательность приближений к корню из двух, о которой шла речь выше.

Маркос Чикот переоткрыл метод Ньютона и, поразившись его простоте, вложил идею в своих героев — пифагорейцев. Впрочем, он не совсем далёк от исторической достоверности. Частный случай метода Ньютона, применимый к нахождению квадратных корней, был известен Герону, жившему в первом или втором веке нашей эры в Александрии (город в Египте, в то время входивший в пределы Римской империи). Формула Герона для вычисления площади треугольника по его сторонам — самое известное на сегодня, но далеко не единственное достижение этого математика, физика и инженера. Он же изобрёл паровой двигатель и механизм, задействованный в автоматах с газировкой — в Александрии второго века стояли похожие автоматы на входе в храм, и все желающие могли, опустив монетку, получить небольшую порцию святой воды.

Впрочем, есть свидетельства о том, что изложенный метод приближённого нахождения квадратного корня уходит корнями ещё глубже — древневавилонская глиняная табличка YBC 7289 (между 1800 и 1600 до н. э.) содержит значение $\sqrt2$‍,‍ вычисленное с тремя шестидесятеричными знаками после запятой. Это значение могло быть получено методом Ньютона. Недаром этот метод извлечения корней ещё в древности называли «вавилонским».

Почему и как метод работает

Давайте обсудим метод Ньютона более подробно в применении к нахождению квадратного корня с заданной точностью. А именно, мы хотим понять, насколько близко мы подойдём к искомому корню за $n$‍‍ шагов. Будем рассматривать уравнение с левой частью $f(x)=x^2-a$‍‍ для произвольного действительного неотрицательного значения $a$‍.‍ График функции $f(x)$‍‍ — это парабола. Она пересекает ось $x$‍‍ в двух точках или, если $a=0$‍,‍ в одной кратной точке. Метод Ньютона допускает следующее геометрическое описание. Начнём с произвольной точки $x_1$‍.‍ Проведём касательную к графику функции $f(x)$‍‍ в точке $(x_1;f(x_1))$‍‍ (рис. 1). Обозначим через $x_2$‍‍ точку пересечения этой касательной с осью $x$‍‍ и далее повторим ту же самую операцию с $x_2$‍‍ вместо $x_1$‍.‍ В результате описанного итерационного процесса получится последовательность точек $x_1$‍,‍ $x_2$‍,‍ $\ldots$‍,‍ $x_n$‍,‍ $\ldots$‍‍

Если мы начали справа от искомого корня, т. е. с точки $x_1\gt\sqrt a$‍,‍ то последовательность точек $x_n$‍‍ монотонно убывает с ростом $n$‍,‍ что очевидно из геометрического описания метода Ньютона. А если начальная точка $x_1$‍‍ лежала на интервале $(0;\sqrt a)$‍,‍ то сначала мы получим точку $x_2\gt\sqrt a$‍,‍ a потом — монотонно убывающую последовательность $x_2$‍,‍ $x_3$‍,‍ $\ldots$‍‍ Таким образом, во всех случаях, когда начальное значение $x_1$‍‍ выбрано положительным, члены последовательности $x_n$‍‍ располагаются всё ближе и ближе к искомому корню, начиная со второго члена. Хотелось бы более точно оценить расстояние от $x_n$‍‍ до $\sqrt a$‍.‍ С этой целью рассмотрим последовательность $u_n=\dfrac{x_n}{\sqrt a}$‍.‍ Зная, как вычисляется последовательность $x_n$‍,‍ мы можем найти рекуррентное соотношение для $u_n$‍.‍ В самом деле, отображение Ньютона $N_f(z)$‍‍ в данном случае имеет вид $$ N_f(z)=z-\frac{z^2-a}{2z}=\dfrac z2+\dfrac a{2z}, $$ значит, $$ x_{n+1}=\dfrac{x_n}2+\dfrac a{2x_n}. $$ Отсюда получаем, что $u_{n+1}=\dfrac{u_n}2+\dfrac1{2u_n}$‍,‍ т. е. последовательность $u_n$‍‍ получается методом Ньютона для уравнения $x^2-1=0$‍.‍ Это можно, впрочем, увидеть без всяких вычислений. Применим к графику функции $f(x)=x^2-a$‍‍ равномерное сжатие или растяжение во всех направлениях с коэффициентом $a^{-1/2}$‍.‍ График перейдёт при таком преобразовании в график функции $f_1(x)=x^2-1$‍,‍ а геометрическое описание метода Ньютона не изменится: касательные прямые перейдут в касательные прямые.

Итак, достаточно рассмотреть метод Ньютона для $f_1$‍.‍ С точки зрения получения ответа, это неинтересно: мы и так знаем, чему равен $\sqrt1$‍.‍ Но, с другой стороны, характер сходимости метода Ньютона для произвольного значения числа $a$‍‍ не меняется, если положить $a=1$‍.‍

Чтобы явно выписать $u_n$‍‍ в зависимости от $u_1$‍,‍ нам понадобится ещё одна замена. Рассмотрим преобразование $$ h(u)=\dfrac{u-1}{u+1}, $$ которое «отправляет» корни уравнения $f_1=0$‍‍ в ноль и бесконечность: $h(1)=0$‍,‍ $h(-1)=\infty$‍.‍ Положим $v_n=h(u_n)$‍,‍ тогда $$ v_{n+1}=\dfrac{u_n+u_n^{-1}-2}{u_n+u_n^{-1}+2}=\dfrac{(u_n-1)^2}{(u_n+1)^2}= v_n^2. $$ Здесь в первом равенстве мы воспользовались определением $v_{n+1}=h(u_{n+1})$‍,‍ а также рекуррентным соотношением для $u_n$‍;‍ второе равенство получается несложными тождественными преобразованиями формул.

Мы видим, что $v_n$‍‍ удовлетворяет очень простому рекуррентному соотношению $$ v_{n+1}=v_n^2. $$ Зная $v_1$‍,‍ можем теперь легко найти $v_n$‍,‍ в зависимости от $n$‍,‍ а именно, $v_n=v_1^{2^{n-1}}$‍.‍ Возвращаясь к $u_n$‍‍ и $x_n$‍‍ мы получаем такие формулы: $$ u_n=h^{-1}(h(u_1)^{2^{n-1}}),\quad x_n=\sqrt a\,h^{-1}\left(h\left(\dfrac{x_1}{\sqrt a}\right)^{2^{n-1}}\right). $$

Через $h^{-1}$‍‍ здесь обозначено обратное преобразование к преобразованию $h$‍,‍ т. е. преобразование со следующим свойством: если применить сначала $h$‍,‍ а потом $h^{-1}$‍‍ или сначала $h^{-1}$‍,‍ а потом $h$‍,‍ то получится тождественное преобразование.

Разумеется, можно явно выписать формулу для $h^{-1}$‍‍ и получить ещё более явное выражение для $x_n$‍‍ (мы предлагаем читателю это проделать). Впрочем, нетрудно заметить и без всяких вычислений, что ни применение преобразования $h$‍,‍ ни применение равномерного сжатия или растяжения не оказывает существенного влияния на то, насколько быстро последовательные итерации метода Ньютона стремятся к предельному значению. Сначала сформулируем оценку характера и скорости сходимости для $v_n$‍,‍ а потом уже перенесём этот результат на последовательность $x_n$‍.‍

Теорема. Если $|v_1|\lt1$‍,‍ то последовательность $v_n$‍‍ сходится к $0$‍‍ суперэкспоненциально быстро, т. е. быстрее, чем любая геометрическая прогрессия. Если $|v_1|\gt1$‍,‍ то последовательность $v_n$‍‍ убегает на бесконечность суперэкспоненциально быстро. Наконец, если $|v_1|=1$‍,‍ то последовательность $v_n$‍‍ не сходится ни к нулю, ни к бесконечности.

Вот что из этой теоремы получается при переходе от $v_n$‍‍ к $x_n$‍.‍

Следствие. Если $x_1\gt0$‍,‍ то последовательность $x_n$‍‍ сходится к $\sqrt a$‍‍ суперэкспоненциально быстро, а если $x_1\lt0$‍,‍ то последовательность $x_n$‍‍ сходится к $-\sqrt a$‍‍ суперэкспоненциально быстро. И только если $x_1=0$‍,‍ последовательность $x_n$‍‍ не определена (или можно положить $x_2=\infty$‍,‍ и тогда все последующие члены тоже будут равны $\infty$‍).‍

Обратите внимание: единственная начальная точка $x_1$‍,‍ для которой не получается приближённо посчитать корень методом Ньютона, это точка $x_1=0$‍,‍ т. е. точка ровно посередине между двумя корнями. Метод Ньютона, запущенный из этой точки, оказывается в состоянии буриданова осла, т. е. неспособен выбрать, к какому из двух корней сойтись. Сходимость метода Ньютона, если она имеет место, суперэкспоненциальная. Более внимательный анализ формул показывает, что на каждом шаге метода Ньютона число верных десятичных знаков примерно удваивается. Например, если число $v_n$‍‍ приближает число 0 с сотней десятичных знаков, т. е. $v_n$‍‍ записывается как «ноль, запятая, сотня нулей и далее, возможно, какие-то другие цифры», то число $v_{n+1}=v_n^2$‍‍ записывается как «ноль, запятая, две сотни нулей, и далее, возможно, что-то ещё».

Анализ метода Ньютона для квадратных уравнений был проделан Артуром Кэли, английским математиком XIX столетия. С отличием закончив Кембридж, Кэли в течение двадцати лет активно занимался адвокатской практикой и лишь в 42 года получил академическую позицию, что уменьшило его зарплату в разы. Кэли внёс существенный вклад в огромное число математических областей, он написал более 400 научных статей, примерно половина из которых пришлись на тот период его жизни, когда занятия наукой приходилось совмещать с юридической деятельностью.

Число, квадрат которого заканчивается на 987654321

Рассмотрим такую задачу: найти такое натуральное число $k$‍,‍ что в десятичной записи числа $k^2$‍‍ последние 9 цифр суть 987624321. В этой задаче можно угадать ответ, а потом обосновать его из общих соображений, но мы будем действовать более систематически, а рассмотренные нами методы будут работать не только для этого конкретного набора цифр. Рассматриваемая задача из области арифметики, казалось бы, не имеет никакого отношения к теме приближённых вычислений вообще и к методу Ньютона в частности. Однако связь есть, и самая непосредственная. Нужно лишь творчески проинтерпретировать термин «приближение».

Приближение — однокоренное слово со словом «близость». В обычном смысле два числа близки, если в начале их десятичной записи много одинаковых цифр. Нам понадобится нестандартное понимание близости: два натуральных числа декадически близки, если в конце их десятичных разложений имеется много одинаковых цифр, т. е. (что то же самое) если разность двух данных чисел делится на большую степень десятки. Поставленную задачу тогда можно переформулировать так: найти натуральное число $k$‍,‍ квадрат которого декадически близок к числу $b=987654321$‍.‍

Когда мы пытались при помощи метода Ньютона приближённо находить корни уравнения $x^2-a=0$‍,‍ мы фактически занимались такой задачей: найти число $x$‍,‍ квадрат которого близок к $a$‍‍ в обычном смысле. А сейчас мы хотим найти число $k$‍,‍ квадрат которого близок к $b$‍‍ в декадическом смысле. Таким образом, видна аналогия между двумя задачами, и мы можем попытаться найти аналогичное решение арифметической задачи.

Начать нужно с какого-то приближения, например, с такого числа, квадрат которого заканчивается на 1. В нашем случае можно взять $k_1=1$‍.‍ Далее будем искать следующее приближение $k_2$‍‍ так, чтобы $k_1-k_2$‍‍ делилось на 10 и чтобы число $k_2^2$‍‍ оканчивалось на 21. Запишем $k_2$‍‍ как $k_1+10m_1$‍,‍ тогда $$ k_2^2=k_1^2+20k_1m_1+\ldots, $$ где многоточие обозначает члены следующего порядка малости (в декадическом смысле, разумеется!) по сравнению с уже написанными. Сравните эту формулу с разложением $$ f(x)=f(x_1)+f'(x_1)\,(x-x_1). $$ Мы хотим, чтобы $k_2^2$‍‍ было близко к 21 и поэтому потребуем, чтобы выполнялось равенство $k_1^2+20k_1m_1=21$‍‍ по модулю 100, т. е. чтобы разность между левой и правой частями делилась на 100. В нашем случае получается, что $20m_1=20$‍‍ по модулю 100 или $m_1=1$‍‍ по модулю 5. Нам годится, например, $m_1=1$‍.‍ Итак, следующее приближение $k_2=11$‍,‍ и квадрат этого числа действительно заканчивается на 21. Аналогия описанного процесса с методом Ньютона должна бросаться в глаза. Процесс можно продолжить: ищем $k_3$‍‍ в виде $k_2+100m_2$‍,‍ и требуем, чтобы выполнялось равенство $k_2^2+200k_2m_2=321$‍‍ по модулю 1000. Опять годится $m_2=1$‍,‍ и эта ситуация будет повторяться. Через 9 шагов мы найдём приближение $k_9=111111111$‍,‍ квадрат которого заканчивается на $b$‍.‍ Это последнее утверждение нетрудно обосновать и без метода Ньютона.

До решения $k=111111111$‍,‍ конечно, можно было догадаться. Но вот другое решение, полученное методом Ньютона: $k=380642361$‍.‍ Оно основано на том, что в качестве $m_1$‍‍ годится не только 1, но и 6. К сожалению и в отличие от классического метода Ньютона, декадический метод Ньютона не всегда можно продолжить — даже если удалось осуществить первые несколько шагов, может так случиться, что следующего шага сделать нельзя. Потенциальная невозможность продолжения связана с тем, что по модулю 10 не всегда можно делить; например, не получается делить на 2 и на 5, т. е. решать уравнения $2x=b$‍‍ или $5x=b$‍‍ по модулю 10. Это, в свою очередь, связано с тем, что 10 не является простым числом. Ситуация упрощается, если вместо десятичных разложений рассматривать разложения по основанию простого числа $p$‍.‍ Аналогично декадической близости, определяется $p$‍‍-адическая близость. Если в $p$‍‍-адическом методе Ньютона можно сделать самый первый шаг, то осуществимость всех дальнейших шагов гарантирована — это утверждение известно как лемма Гензеля.

Ещё несколько наблюдений

Вернёмся к методу Ньютона над вещественными числами, и даже конкретно к вычислению $\sqrt2$‍.‍ Есть ещё один классический способ посчитать это число — через цепные дроби, т. е. как предел последовательности $$ x_n=1+\dfrac1{2+\dfrac1{2+\dfrac1{\ddots+\dfrac12}}} $$ (в правой части написано $n$‍‍ двоек), которую эквивалентным образом можно задать рекуррентным соотношением $x_{n+1}=1+\dfrac1{1+x_n}$‍‍ с начальным условием $x_0=1$‍.‍ Почему эта последовательность сходится к $\sqrt2$‍‍ и насколько быстро? Это можно понять с помощью той же самой замены $v=\dfrac{x-\sqrt2}{x+\sqrt2}$‍,‍ которая была описана выше. Смысл замены в том, что корни $x=\pm\sqrt2$‍‍ отправляются в $v=0$‍,‍ $\infty$‍,‍ а отображение Ньютона записывается как $v\mapsto v^2$‍.‍ Последовательность $x_n$‍‍ становится последовательностью $v_n$‍,‍ a рекуррентное соотношение на $x_n$‍‍ переписывается следующим образом в терминах $v_n$‍:‍ $$ v_{n+1}=\lambda v_n,\quad v_0=\lambda,\quad\lambda=\dfrac{1-\sqrt2}{1+\sqrt2}, $$ откуда сразу же вытекает, что $v_n=\lambda^{n+1}$‍.‍ Число $\lambda$‍‍ отрицательно и по модулю меньше единицы. Значит, последовательность $v_n$‍‍ сходится к нулю экспоненциально с чередованием знаков — откуда следует, что $x_n$‍‍ стремится к 2 с экспоненциальной скоростью, причём величина $x_n-\sqrt2$‍‍ постоянно меняет знак с увеличением $n$‍‍ нa единицу. Отображение Ньютона в терминах переменной $v$‍‍ действует как возведение в квадрат, а значит, отправляет $v_n$‍‍ в $v_{2n+1}$‍‍ — в самом деле, если $v_n=\lambda^{n+1}$‍,‍ то $v_n^2=\lambda^{2n+2}=v_{2n+1}$‍.‍ Мы можем сделать вывод, возвращаясь к переменной $x$‍,‍ что $N_f(x_n)=x_{2n+1}$‍,‍ т. е. число двоек в цепной дроби удваивается на каждой итерации метода Ньютона. Заметьте: этот вывод было бы сложнее получить непосредственными вычислениями в исходной переменной $x$‍.‍

Теперь обсудим, от чего может зависеть скорость сходимости метода Ньютона. Можно считать без ограничения общности, что искомый корень находится в точке 0. Допустим, что функцию $f$‍‍ можно записать вблизи нуля формулой вида $f(x)=x^k\,g(x)$‍,‍ где $k$‍‍ — положительное число, а $g$‍‍ — функция, для которой $g(0)\ne0$‍.‍ Если $f$‍‍ — многочлен или хотя бы достаточно много раз дифференцируемая функция, то это всегда возможно, причём $k$‍‍ будет целым; мы дальше обсудим, однако, и случаи дробных показателей $k$‍.‍ Будем считать, что производная функции $g$‍‍ существует в окрестности нуля, не считая самой точки 0, и непрерывна в этой проколотой окрестности. Тогда отображение Ньютона можно записать как $$ N_f(x)=x-\dfrac{f(x)}{f'(x)}=x\dfrac{(k-1)\,g(x)+x\,g'(x)}{k\,g(x)+k\,g'(x)}. $$ Если $k=1$‍,‍ то правая часть делится на $x^2$‍,‍ и по этой причине следует ожидать, что $N_f(x)$‍‍ при малых $x$‍‍ будет того же порядка, что $x^2$‍,‍ т. е. сходимость метода Ньютона будет примерно такой же стремительной, как в случае квадратных корней: число верных десятичных знаков будет примерно удваиваться с каждой итерацией. Однако при $k\ne1$‍‍ такой быстрой сходимости уже не будет.

Рассмотрим, например, функцию $f(x)=x^2$‍‍ (рис. 2). Для этой функции получается $N_f(x)=\dfrac x2$‍.‍ При многократном повторении данной операции получается последовательность точек, сходящаяся к нулю, но теперь уже только экспоненциально: для получения каждого следующего десятичного знака требуется 3‍—‍4 итерации.

Вообще, если $g(x)=1$‍,‍ то $N_f(x)=\dfrac{k-1}kx$‍.‍ С ростом $k\gt1$‍‍ коэффициент при $x$‍‍ возрастает, оставаясь в интервале $(0;1)$‍,‍ и стремится к 1 при $k\to\infty$‍.‍ Мораль такова: чем больше k, тем хуже сходится метод Ньютона. Натуральные значения $k\gt1$‍‍ соответствуют кратному корню, т. е. тому случаю, когда несколько корней слились в один. Кратные корни следует рассматривать как вырождения: вероятность того, что у случайным образом выбранной функции обнаружатся кратные корни, равна 0. Таким образом, ухудшение сходимости носит исключительный характер и встречается лишь в вырожденных ситуациях.

Если взять $k=\dfrac13$‍,‍ то это ещё более «страшное» вырождение: функция $f(x)$‍‍ вообще не будет дифференцируема в точке 0. Хотя такого рода особенности иногда возникают в естественных контекстах, скажем, в математических моделях задач естествознания, попадание особенности прямо в искомый корень — слишком невероятное невезение. Но всё же важно рассмотреть такого рода ситуацию в качестве контрпримера. Для функции $f(x)=\sqrt[3]x$‍‍ отображение Ньютона $N_f(x)=-2x$‍‍ вообще не приближает никакое ненулевое начальное значение к искомому корню, а, наоборот, уводит его экспоненциально быстро на бесконечность (рис. 3). Последовательность итераций выглядит как вереница «перелётов» (каждый новый перелёт намного хуже предыдущего).

Над комплексными числами

Исторически комплексные числа появились в связи с необходимостью рассматривать уравнения, которые в вещественных числах никаких решений не имеют. Пример такого уравнения: $x^2+1=0$‍.‍ Никаких вещественных значений величины $x$‍,‍ для которых уравнение бы выполнялось, не существует. Интересно посмотреть, что делает в этом случае метод Ньютона. Метод Ньютона пытается найти корни, но корней нет. В результате получается хаотическая динамика, т. е. последовательности точек, возникающие из применения метода Ньютона, не демонстрируют никаких явных закономерностей, а ведут себя как бы случайным образом.

Обозначив $x^2+1$‍‍ через $f_{-1}(x)$‍,‍ мы сформулируем некоторые свойства отображения Ньютона $N=N_{f_{-1}}$‍.‍

• Можно подобрать такое начальное значение $x_1$‍,‍ для которого рекуррентная последовательность $x_n$‍,‍ заданная соотношением $x_{n+1}=N(x_n)$‍,‍ подходит как угодно близко к любому вещественному числу, т. е. для всякого $a\in\mathbb{R}$‍‍ и для всякого $\eps\gt0$‍‍ найдётся $n$‍‍ со свойством $a-\eps\lt x_n\lt a+\eps$‍.‍
• Для всякого натурального $m\gt0$‍‍ найдётся такое начальное значение $x_1$‍,‍ для которого последовательность $x_n$‍‍ оказывается периодической с периодом $m$‍,‍ т. е. $x_{n+m}=x_n$‍‍ при всех $n\ge1$‍.‍
• Если $x_1$‍‍ известно только с некоторой точностью, то про $x_n$‍‍ при больших $n$‍‍ уже ничего сказать нельзя: любая сколь угодно малая окрестность любой заданной точки $c\in\mathbb{R}$‍‍ отобразится при действии достаточно высокой итерации отображения $N$‍‍ на всю прямую.

Доказательство этих свойств оставим читателю в качестве не очень простого упражнения.

Начиная с этого момента мы переходим от вещественных чисел к комплексным в предположении, что читатель знаком с понятием комплексного числа. Уравнения полезно решать над комплексными числами. Более того, в плоскости комплексных чисел многие вещи упрощаются. Например, вещественные многочлены одной и той же степени могут иметь разное число корней, а некоторые многочлены высокой степени, скажем степени 100, не имеют корней вовсе. Комплексные многочлены всегда имеют корни, и их число (с учётом кратности) всегда равно степени многочлена. Это означает, что при плавном изменении коэффициентов многочлена данной степени его корни могут сливаться (проходить друг через друга), но не могут появляться ниоткуда и не могут бесследно исчезать. Утверждение о том, что многочлен степени $d\gt0$‍‍ всегда имеет хотя бы один корень, называется основной теоремой алгебры. Мы здесь не будем обсуждать доказательство этой глубокой теоремы, но отметим, что утверждение о числе корней с учётом кратности является несложным её следствием.

Чтобы хорошо понять, как работает метод Ньютона, его тоже нужно запустить на плоскости комплексных чисел. Ниже мы опишем, как работает метод Ньютона для решения квадратных уравнений $f(z)=0$‍,‍ т. е. уравнений, левая часть которых имеет вид $f(z)=az^2+bz+c$‍,‍ $a\ne0$‍.‍ Данное описание было получено Артуром Кэли. Хотя никаких доказательств приведено не будет, вдумчивый читатель сможет их восстановить, воспользовавшись идеями раздела «Почему и как метод работает».

У квадратного уравнения два различных корня или один кратный корень. Сначала допустим, что $f$‍‍ имеет корни $\alpha$‍‍ и $\beta$‍‍ (рис. 4). Проведём прямую $l$‍,‍ перпендикулярную отрезку с концами $\alpha$‍,‍ $\beta$‍‍ и делящую этот отрезок пополам. Эта прямая $l$‍‍ разбивает плоскость комплексных чисел на две полуплоскости, одна из которых, $H_\alpha$‍,‍ содержит корень $\alpha$‍,‍ а другая, $H_\beta$‍,‍ содержит корень $\beta$‍.‍ Если начальное приближение выбрано в полуплоскости $H_\alpha$‍,‍ то итерации метода Ньютона сходятся к корню $\alpha$‍‍ суперэкспоненциально быстро. Аналогично для корня $\beta$‍‍ и соответствующей ему полуплоскости. Наконец, если мы начнём на прямой $l$‍,‍ то все итерации метода Ньютона будут лежать в $l\cup\{\infty\}$‍.‍ Более того, динамика на $l\cup\{\infty\}$‍‍ хаотична в том же смысле, в котором хаотична динамика метода Ньютона для $x^2+1=0$‍‍ на $\mathbb{R}\cup\{\infty\}$‍‍ (на самом деле, динамика такая же). Полуплоскости $H_\alpha$‍‍ и $H_\beta$‍‍ называются бассейнами притяжения точек $\alpha$‍‍ и $\beta$‍‍ соответственно относительно динамики отображения Ньютона. Интенсивность цвета на рисунке соответствует скорости сходимости метода Ньютона: чем быстрее сходимость, тем светлее точка. По этой причине точки, близкие к корням, выглядят как почти белые.

Осталось рассмотреть случай $\alpha=\beta$‍.‍ В этом случае для любого конечного начального значения итерации метода Ньютона сходятся к $\alpha$‍.‍ Но сходимость уже не суперэкспоненциальная, а просто экспоненциальная, т. е. как у геометрической прогрессии. Грубо говоря, на каждом следующем шаге расстояние до корня уменьшается в два раза.

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

Кубические уравнения

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

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

В качестве простейшего примера рассмотрим кубический многочлен $f(z)=z^3-1$‍,‍ корни которого — кубические корни из единицы. Эти корни располагаются в вершинах правильного треугольника, вписанного в единичную окружность. У каждого из корней есть свой бассейн притяжения. Сначала подумайте, как могли бы выглядеть эти бассейны. Вот гипотеза, кажущаяся разумной: плоскость делится на три сектора (рис. 5); каждый из этих секторов содержит один из трёх корней и состоит из всех точек плоскости, которые ближе к данному корню, чем к двум другим. Описанные только что секторы и должны быть, предположительно, бассейнами притяжения. Но в действительности всё намного интереснее!

На рисунке 6 бассейны трёх различных корней изображены разными цветами, а именно, красным, жёлтым и синим. Чем быстрее последовательность приближений, начинающаяся с данной точки, сходится к соответствующему корню, тем светлее покрашена данная точка. Как можно увидеть из рисунка, каждый из трёх бассейнов состоит из бесконечного числа областей. Имеются точки внутри областей, т. е. внутри бассейнов притяжения, а ещё есть точки, к которым накапливаются различные бассейны — последнего сорта точки называются точками Жюлиа. Около каждой точки Жюлиа, причём сколь угодно близко к рассматриваемой точке, имеются сколь угодно малые области, лежащие в каждом из трёх бассейнов. На рисунке можно увидеть также некоторые специальные точки Жюлиа, к которым примыкает по 6 компонент, а именно, по 2 компоненты из каждого бассейна.

Множество всех точек Жюлиа называется множеством Жюлиа для данного отображения Ньютона. У отображения Ньютона для квадратного уравнения с двумя различными корнями множество Жюлиа представляет собой прямую. А в случае кубического уравнения множество Жюлиа соответствующего отображения Ньютона — нетривиальный фрактал, т. е. самоподобное множество. Что имеется в виду под самоподобием, нужно было бы уточнить, поскольку это не есть в точности подобие в евклидовом смысле, хотя и близко к последнему.

К сожалению, размер статьи не позволяет нам углубиться в обсуждение этого интересного вопроса. Больше о самоподобии в контексте множеств Жюлиа можно прочесть в статье [3].

Ещё один неожиданный эффект метода Ньютона для кубических уравнений можно увидеть на примере многочлена $f(z)=z^3-2z+2$‍‍ (рис. 7). Соответствующее отображение $N$‍,‍ имеет цикл периода два, состоящий из точек 0 и 1 (точка 1 не попала на рисунок, оставшись, разумеется, справа). Вообще, циклом периода $p$‍‍ называется такой набор точек $z_0$‍,‍ $\ldots$‍,‍ $z_{p-1}$‍,‍ что $N_f(z_i)=z_{i+1}$‍‍ для всех $i=0$‍,‍ $\ldots$‍,‍ $p-2$‍‍ и $N_f(z_{p-1})=z_0$‍‍ — таким образом, отображение $N_f$‍‍ переставляет данные точки как бы по кругу. Все близкие к этому циклу точки приближаются к нему при итерациях отображения $N_f$‍.‍ Таким образом, имеется целая область, состоящая из таких начальных значений, для которых этот метод «вообще не работает», т. е. не сходится ни к одному из корней многочлена $f$‍.‍ И таких областей даже бесконечно много (на рисунке 7 они закрашены чёрным цветом).

С точки зрения вычислительных методов, всё это плохие новости. Когда люди впервые столкнулись с такими эффектами, то решили, что метод Ньютона не является надёжной вычислительной процедурой, поскольку неясно, как выбирать начальное приближение. Реабилитация метода Ньютона заняла несколько десятилетий и потребовала тонких инструментов из голоморфной динамики (вот, например, один из первых прорывов в этом направлении [4]), но всё же, по состоянию на сегодня, метод обрёл новую жизнь — имеются чёткие способы превратить его в эффективный вычислительный инструмент (см. [5]). Читателю, заинтересовавшемуся динамическими аспектами метода Ньютона, возможно, стоит посмотреть видеозапись лекции [6].

Литература

1. Б. Беккер, С. Востоков, Ю. Ионин. 2-адические числа // «Квант», 2008, № 1.
2. А. А. Кириллов. Что такое число?. — M.: МЦНМО, 2019.
3. Н. Долбилин. Множества Жюлиа // «Квант», 2008, № 1.
4. J. Hubbard, D. Schleicher, S. Sutherland. How to find all roots of complex polynomials by Newton's method // Inventions mathematicae, 2001, vol. 146, р. 1‍—‍33.
5. D. Schleicher. On the efficient global dynamics of Newton's method for complex polynomials // Nonlinearity, 2023, vol. 36, n. 2, p. 1349‍—‍1377.
6. D. Schleicher. Complex dynamics: the Mandelbrot set and Newton's Method. On useless and useful Mathematics: Лекция на летней школе «Современная математика», 2010‍.