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

Арифметичним коренем n-го степеня ${\sqrt[{n}]{A}}$ додатного дійсного числа 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 (64 = 2⁶) ітерацій). У зв'язку з цим даний алгоритм використовується в комп'ютерах як дуже швидкий метод знаходження квадратних коренів.

Для великих значень 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)=nx^{n-1}.$

Тоді ітераційне правило:

$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]$

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

Посилання

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