Теперь для данного очередного приближения $X_k$ найдём следующее, более точное $X_{k+1}$, исходя из условий:

Пусть уравнение касательной имеет вид $y=ax+b$. Тогда перечисленные условия приводят к уравнениям, в которых неизвестными являются буквы $a$, $b$ и $X_{k+1}$: $$\begin{array}{l}{X_k}^2-A=a{X}_k+b\text{,}\\ a^2+4\left(A+b\right)=0\text{,}\\ a{X}_{k+1}+b=0\text{.}\end{array}$$ Второе уравнение служит условием единственности решения первого, квадратного уравнения — мы приравниваем нулю дискриминант. Из первых двух уравнений, исключая $A+b$, получаем $X_k=\frac{a}{2}$, откуда $b=-{X_k}^2-A$. Подставляя найденные значения $a$ и $b$ в третье уравнение, получим $$X_{k+1}=\frac{1}{2}\left(X_k+\frac{A}{X_k}\right)\text{.}$$

Найденная формула для построения последовательных приближений к квадратному корню из числа $A$ известна ещё с незапамятных времён, задолго до Ньютона. Это формула Герона (да, у Герона есть ещё и такая формула).

Читатели, знакомые с дифференциальным исчислением, могут вывести и общую формулу для построения последовательных приближений к решению уравнения $f\left(x\right)=0$. Составим уравнение касательной в точке $X_k$: $$y-f\left(X_k\right)=f^{\prime }\left(X_k\right)\left(x-X_k\right)\text{.}$$ Условие прохождения касательной через точку $\left(X_{k+1},0\right)$ записывается в виде $$X_{k+1}=X_k-\frac{f\left(X_k\right)}{f^{\prime }\left(X_k\right)}\text{.}$$ Формула Герона находится в полном согласии с этой общей формулой.

По всей видимости, автор формулы Герона получил её вот из каких соображений. Рассмотрим прямоугольник со сторонами $X$ и $\frac{A}{X}$ (его площадь равна $A$). Преобразуем его в другой прямоугольник с той же площадью, заменив сторону $X$ на среднее арифметическое сторон, то есть на $\frac{1}{2}\left(X+\frac{A}{X}\right)$. Похоже, что такое преобразование делает прямоугольник более квадратным, если можно так выразиться.

Главным достоинством метода Ньютона является сверхбыстрое приближение к точному решению уравнения (сверхсходимость). Исследуем это явление на примере формулы Герона. Для этого обозначим как $R_k=X_k-\sqrt{A}$ ошибку, которую даёт $k$-е приближение. Подставив $R_k+\sqrt{A}$ вместо $X_k$ в формулу Герона, получим $$R_{k+1}=\frac{{R_k}^2}{2\left(R_k+\sqrt{A}\right)}\text{.}$$ Выберем в качестве начального приближения $X_0$ число, заведомо большее, чем точное решение $\sqrt{A}$. Это значит, что начальная ошибка $R_0$ положительна. Видно, что в этом случае ошибка на каждом шаге останется положительной, то есть последовательные приближения подкрадываются к решению справа. Тогда, очевидно, верны неравенства $$R_{k+1}<\frac{R_k}{2}\text{,}{R}_{k+1}<\frac{{R_k}^2}{2\sqrt{A}}\text{.}$$ Первое означает, что после каждого шага ошибка уменьшается как минимум вдвое. Это уже неплохо, но пока не выявляет никакого преимущества метода Ньютона перед методом бисекций. Но рано или поздно величина $R_k$ станет меньше, чем $2\sqrt{A}$, после чего из второго неравенства будет следовать $R_{k+1}<{R_k}^2\text{.}$ Тут начинается самое интересное. Получается, что ошибка на каждом шаге, грубо говоря, возводится в квадрат. Если, к примеру, ошибка на данном шаге меньше $\mathrm{0,1}$, то на следующем она будет меньше $\mathrm{0,01}$, затем меньше $\mathrm{0,0001}$, затем меньше $\mathrm{0,00000001}$, и так далее. Всё это означает, что каждое новое приближение содержит как минимум на одну верную двоичную цифру больше, чем предыдущее, но, начиная с некоторого шага, количество верных цифр станет с каждым шагом удваиваться. Вот это уже и есть сверхсходимость.

Удачным выбором начального приближения будет $X_0=\frac{1+A}{2}⩾\sqrt{A}$ (неравенство следует из формулы сокращённого умножения $1-2\sqrt{A}+A={\left(1-\sqrt{A}\right)}^2⩾0$).

Нам удалось доказать сходимость и даже сверхсходимость для метода Ньютона в случае уравнения $x^2-A=0$. В общем случае всё совсем не так гладко, даже если потребовать от функции в левой части уравнения наличия касательной в каждой точке графика (то есть дифференцируемости). Очевидную проблему создают точки, в которых касательная горизонтальна (где производная обращается в нуль). Если же касательная горизонтальна в самом корне уравнения, явления сверхсходимости уже не будет. Характерный пример даёт формула Герона для случая $A=0$: $X_{k+1}=\frac{X_k}{2}$.

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

На самом деле существует взаимосвязь между двумя описанными проблемами, поскольку по теореме Ролля между двумя решениями уравнения $f\left(x\right)=0$ непременно найдётся точка, в которой касательная к графику функции $f\left(x\right)$ горизонтальна.

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

У описанных алгоритмов имеется общая черта: в каждом из них строится некоторая последовательность, в которой каждый следующий элемент получается из предыдущего по одному и тому же правилу, иными словами, рекуррентная последовательность первого порядка. Для метода бисекций это последовательность стягивающихся отрезков, а в случае метода Ньютона — последовательные приближения. Из главы 15. «Десятичные дроби» мы уже знаем, что рекуррентные последовательности, составленные из элементов конечного множества, всегда зацикливаются. Последовательные приближения из метода Ньютона всегда монотонно убывают, и поэтому никак не могут зациклиться (для зацикливания необходимо и достаточно наличие двух равных элементов в последовательности, что полностью исключено при строгой монотонности). Но это и неудивительно, поскольку множество вещественных чисел бесконечно. Точно так же не стоит ожидать зацикливания в методе бисекций, поскольку множество отрезков на вещественной прямой (множество числовых пар) и подавно бесконечно.

Тем не менее при реализации обоих методов на компьютере зацикливание неизбежно. Дело в том, что точное представление вещественного числа в компьютерной памяти невозможно, поскольку числовое значение потребовало бы для хранения бесконечной памяти. Поэтому используется приближённое представление, в котором для числа отводится ограниченное количество бит. Число различных состояний этого битового набора конечно, хоть, может быть, и очень велико. Так что количество компьютерных вещественных чисел конечно; конечно и количество отрезков на вещественной прямой. Вывод, который следует сделать из всех этих наблюдений, таков: любая рекуррентная последовательность, построенная на компьютере, зацикливается.

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

Вместо того, чтобы заранее задавать необходимую точность, по достижении которой алгоритмы должны остановиться, постараемся «выжать» из алгоритмов наилучшую возможную точность (которая, кстати, зависит от типа компьютера, в частности, от количества бит, отведённых для представления вещественных чисел). Остановим алгоритм тогда, когда построенные последовательности достигнут неизбежного цикла.

Для обнаружения циклов прекрасно подойдёт техника, описанная в разделе «Метод Черепахи и Зайца». Для наших целей будет достаточно первого забега Черепахи и Зайца. Как только произойдёт их встреча, программа остановится.

Впрочем, следует заметить, что, применяя метод Ньютона к вычислению квадратного корня, совершенно не обязательно привлекать Черепаху и Зайца. Как мы уже заметили, рекуррентная последовательность приближений, строго монотонная согласно теории, на практике уже не может быть строго монотонной. Иными словами, найдётся такой номер $k$, что $X_{k+1}⩾X_k$. Это значит, что последовательность начинает зацикливаться, и пора остановиться. Наше наблюдение примерно вдвое сокращает вычислительные затраты, если сравнивать с алгоритмом, использующим метод Флойда.