WikiSort.ru - Не сортированное

Арифметическим корнем 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).}$

Существует несколько выводов данного алгоритма. Одно из них рассматривает алгоритм как частный случай метода Ньютона (также известного как метод касательных) для нахождения нулей функции ${\displaystyle f(x)}$ с заданием начального предположения. Хотя метод Ньютона является итерационным, он сходится очень быстро. Метод имеет квадратичную скорость сходимости — это означает, что число верных разрядов в ответе удваивается с каждой итерацией (то есть увеличение точности нахождения ответа с 1 до 64 разрядов требует всего лишь 6 итераций). По этой причине данный алгоритм используют в компьютерах как очень быстрый метод нахождения квадратных корней.

Для больших значений 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})}}=}$

${\displaystyle =x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}=}$

${\displaystyle =x_{k}+{\frac {1}{n}}\left[{\frac {A}{x_{k}^{n-1}}}-x_{k}\right]=}$

${\displaystyle ={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$ ${\displaystyle =}$

${\displaystyle x_{k}\times {\Bigl (}1-\left({\frac {1-\left({\frac {A}{x_{k}^{n}}}\right)}{n}}\right){\Bigr )}}$

Ссылки

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

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.