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

# Сделать начальное предположение <math>x_0;</math>
# Задать <math>x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}</math>;
# Повторять шаг 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 |first=Kendall E. |last=Atkinson |title=An introduction to numerical analysis |location=New York |publisher=Wiley |year=1989 |edition=2nd |isbn=0471624896 }}.

{{rq|refless}}

[[Категория:Численные методы решения уравнений]]
[[Категория:Ряды и последовательности]]
[[Категория:Алгебра]]
[[Категория:Элементарные функции]]
[[Категория:Элементарная алгебра]]