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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}x_{k+1}&=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\\&=x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}\\&=x_{k}+{\frac {1}{n}}\left[{\frac {A}{x_{k}^{n-1}}}-x_{k}\right]\\&={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right].\end{aligned}}}$

• Atkinson, Kendall E. (1989), An introduction to numerical analysis (2nd ed.), New York: Wiley, ISBN 0471624896.

У этой статьи есть несколько проблем, помогите их исправить: В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (1 сентября 2013) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.