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

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

Арифметическим корнем n-ной степени nA положительного действительного числа A называется положительное действительное решение уравнения

x^n = A

(для целого n существует n комплексных решений данного уравнения, если A > 0, но только одно является положительным действительным).

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

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

Частным случаем является итерационная формула Герона для нахождения квадратного корня, которая получается подстановкой n = 2 в шаг 2:

x_{k+1} = \frac{1}{2}\left(x_k + \frac{A}{x_k}\right).

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

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

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

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

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

Задача нахождения корня n-ной степени может быть рассмотрена как нахождение нуля функции

f(x) = x^n - A.

Производная этой функции равна

f^\prime(x) = n x^{n-1}.

Тогда итерационное правило

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]

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

Ссылки

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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Алгоритм нахождения корня n-ной степени" в других словарях:

  • Арифметический корень — n й степени (n > 0) из числа a это такое число b, что bn = a. В поле действительных чисел корень может иметь до двух решений или ни одного, если это корень чётной степени из отрицательного числа. В поле комплексных чисел корень n й степени… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»