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

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

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

xn=A

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

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

  1. Початкове значення послідовності покласти рівним x0 (груба оцінка значення кореня);
  2. Задати xk+1=1n[(n−1)xk+Axkn−1];
  3. Повторювати крок 2 до досягнення потрібної точності.

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

xk+1=12(xk+Axk).

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

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

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

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

  1. Задати початкове наближення x0;
  2. Задати xk+1=xk−f(xk)f′(xk);
  3. Повторювати крок 2, доки не буде досягнута необхідна точність.

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

f(x)=xn−A.

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

f′(x)=nxn−1.

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

xk+1=xk−f(xk)f′(xk)=xk−xkn−Anxkn−1=xk+1n[Axkn−1−xk]=1n[(n−1)xk+Axkn−1]

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

Посилання

Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Алгоритм_знаходження_кореня_n-го_степеня&oldid=6078