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

Арифметичним коренем n-го степеня ${\displaystyle {\sqrt[{n}]{A}}}$ додатного дійсного числа A називається додатний дійсний розв'язок рівняння

${\displaystyle x^{n}=A}$

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

Існує алгоритм знаходження кореня n-го степеня, який швидко сходиться:

1. Початкове значення послідовності покласти рівним ${\displaystyle x_{0}}$ (груба оцінка значення кореня);
2. Задати ${\displaystyle x_{k+1}={\frac {1}{n}}\left[(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}\right]}$;
3. Повторювати крок 2 до досягнення потрібної точності.

Частковим випадком є ітераційна формула Герона для знаходження квадратного кореня, яка отримується підстановкою n = 2 в пункт 2:

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

Існує декілька виводів даного алгоритму. Один з них розглядає алгоритм як частковий випадок методу Ньютона (також відомого як метод дотичних) для знаходження нулів функції f(x) з заданням початкового наближення. Хоча метод Ньютона і є ітераційним, він сходиться дуже швидко. Метод має квадратичну швидкість збіжності — це означає, що кількість вірних розрядів у відповіді подвоюється з кожною ітерацією (тобто, для прикладу, збільшення точності знаходження відповіді з 1 до 64 розрядів потребує лише 6 (64 = 2⁶) ітерацій). У зв'язку з цим даний алгоритм використовується в комп'ютерах як дуже швидкий метод знаходження квадратних коренів.

Для великих значень n даний алгоритм стає менш ефективним, оскільки потребує обчислення ${\displaystyle x_{k}^{n-1}}$ на кожному кроці, який, однак, може бути може бути обчислений з допомогою алгоритму швидкого піднесення до степеня.

Виведення з використанням методу Ньютона

Метод Ньютона — це метод знаходження нулів функції f(x). Загальна його ітераційна схема наступна:

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

Задача знаходження кореня n-го степеня може бути розглянута як знаходження нуля функції

${\displaystyle f(x)=x^{n}-A.}$

Похідна цієї функції дорівнює

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

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

${\displaystyle 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 .