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

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

x^{n}=A

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

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

Початкове значення послідовності покласти рівним $x_{0}$ ;
Задати $x_{k+1}={\frac {1}{n}}\left[(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}\right]$ ;
Повторювати крок 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). Загальна його ітераційна схема наступна:

Задати початкове наближення $x_{0}$ ;
Задати $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}$ ;
Повторювати крок 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..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.