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

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

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

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

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

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

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

<math>

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

Ссылки

• Шаблон:Citation.