Алгоритм нахождения корня n-ной степени

Арифметическим корнем $n$-ной степени $\sqrt[n]{A}$ положительного действительного числа $A$ называется положительное действительное решение уравнения $x^n=A$ (для целого $n$ существует $n$ комплексных решений данного уравнения, если $A>0$, но только одно является положительным действительным).

Существует быстросходящийся алгоритм нахождения корня $n$-ной степени:

1. Сделать начальное предположение $x_0$;
2. Задать $x_{k+1}=\frac{1}{n}\left((n-1)x_k+\frac{A}{x_k^{n-1}}\right)$;
3. Повторять шаг 2, пока не будет достигнута необходимая точность.

Частным случаем является итерационная формула Герона для нахождения квадратного корня, которая получается подстановкой $n=2$ в шаг 2: $x_{k+1}=(x_k+A/x_k)/2$.

Существует несколько выводов данного алгоритма. Одно из них рассматривает алгоритм как частный случай метода Ньютона (также известного как метод касательных) для нахождения нулей функции $f(x)$ с заданием начального предположения. Хотя метод Ньютона является итерационным, он сходится очень быстро. Метод имеет квадратичную скорость сходимости — это означает, что число верных разрядов в ответе удваивается с каждой итерацией (то есть увеличение точности нахождения ответа с 1 до 64 разрядов требует всего лишь 6 итераций, но не стоит забывать о машинной точности). По этой причине данный алгоритм используют в компьютерах как очень быстрый метод нахождения квадратных корней.

Для больших значений $n$ данный алгоритм становится менее эффективным, так как требуется вычисление $x_k^{n-1}$ на каждом шаге, которое, тем не менее, может быть выполнено с помощью алгоритма быстрого возведения в степень.

Вывод из метода Ньютона

Метод Ньютона — это метод нахождения нулей функции $f(x)$. Общая итерационная схема:

1. Сделать начальное предположение $x_0;$
2. Задать $x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$;
3. Повторять шаг 2, пока не будет достигнута необходимая точность.

Задача нахождения корня $n$-ой степени может быть рассмотрена как нахождение нуля функции $f(x)=x^n-A$, производная которой равна $f^{\prime }(x)=n{x}^{n-1}$.

Тогда второй шаг метода Ньютона примет вид

$\begin{array}{cc}{x}_{k+1}& =x_k-\frac{f(x_k)}{f^{\prime }(x_k)}\\ & =x_k-\frac{x_k^n-A}{n{x}_k^{n-1}}\\ & =x_k+\frac{1}{n}[\frac{A}{x_k^{n-1}}-x_k]\\ & =\frac{1}{n}\left[(n-1)x_k+\frac{A}{x_k^{n-1}}\right].\end{array}$

Ссылки

• Шаблон:Citation.