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

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

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

Сделать начальное предположение $x_{0}$ ;
Задать $x_{k+1}={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right)$ ;
Повторять шаг 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)$ . Общая итерационная схема:

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

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

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

{\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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.