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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \begin{align} x_{k+1} &= x_k - \frac{f(x_k)}{f'(x_k)} \\ &= x_k - \frac{x_k^n - A}{n x_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{align} }[/math]

Ссылки

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