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

Арифметичним коренем n-го степеня додатного дійсного числа A називається додатний дійсний розв'язок рівняння

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

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

  1. Початкове значення послідовності покласти рівним ;
  2. Задати ;
  3. Повторювати крок 2 до досягнення потрібної точності.

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

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

Для великих значень n даний алгоритм стає менш ефективним, оскільки потребує обчислення на кожному кроці, який, однак, може бути може бути обчислений з допомогою алгоритму швидкого піднесення до степеня.

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

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

  1. Задати початкове наближення  ;
  2. Задати  ;
  3. Повторювати крок 2, доки не буде досягнута необхідна точність.

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

 

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

 

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

 

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

ПосиланняРедагувати

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