Меню Закрыть

Формула ньютона для корня

x n = A <displaystyle x^=A>

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

Существует быстросходящийся алгоритм нахождения корня n -ной степени:

  1. Сделать начальное предположение x 0 ; <displaystyle x_<0>;>
  2. Задать x k + 1 = 1 n ( ( n − 1 ) x k + A x k n − 1 ) ; <displaystyle x_=<frac <1>>left(<(n-1)x_+<frac ^>>>
    ight);>
  3. Повторять шаг 2, пока не будет достигнута необходимая точность.

Частным случаем является итерационная формула Герона для нахождения квадратного корня, которая получается подстановкой n = 2 в шаг 2:

x k + 1 = 1 2 ( x k + A x k ) . <displaystyle x_=<frac <1><2>>left(x_+<frac >>
ight).>

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

Для больших значений n данный алгоритм становится менее эффективным, так как требуется вычисление x k n − 1 <displaystyle x_^> на каждом шаге, которое, тем не менее, может быть выполнено с помощью алгоритма быстрого возведения в степень.

Вывод из метода Ньютона [ править | править код ]

Метод Ньютона — это метод нахождения нулей функции f(x) . Общая итерационная схема:

  1. Сделать начальное предположение x 0 ; <displaystyle x_<0>;>
  2. Задать x k + 1 = x k − f ( x k ) f ′ ( x k ) ; <displaystyle x_=x_-<frac )>)>>=> = x k − x k n − A n x k n − 1 = <displaystyle =x_-<frac ^-A>^>>=> = x k + 1 n [ A x k n − 1 − x k ] = <displaystyle =x_+<frac <1>>left[<frac ^>>-x_
    ight]=> = 1 n [ ( n − 1 ) x k + A x k n − 1 ] <displaystyle =<frac <1>>left[<(n-1)x_
    +<frac ^>>>
    ight]> = <displaystyle => x k × ( 1 − ( 1 − ( A x k n ) n ) ) <displaystyle x_
    imes <Bigl (>1-left(<frac <1-left(<frac ^>>
    ight)>
    >
    ight)<Bigr )>>
Читайте также:  Как выбрать приложение для открытия файлов

Статья любезно предоставлена
Copyright © Nikitine Valeri F. 2000

Вариант вычисления квадратного корня (алгоритм Ньютона)

Для вычисления квадратного корня здесь использован известный метод Ньютона. Рассмотрены машинно-зависимый и машинно-независимый варианты. Перед применением алгоритма Ньютона, область определения исходного числа сужается до [0.5,2] (в другом варианте до [1,16]). Второй вариант машинно-независим, но работает дольше.

Скажем сразу, не самый быстрый вариант, но один из самых быстрых. Основная проблема заключается здесь в том, что нет универсального машинного представления чисел с плавающей точкой, поэтому разделение числа на мантиссу и двоичную экспоненту как составляющих его компьютерного представления нельзя записать единым образом. Имено поэтому здесь подключено описание математической библиотеки, из которой, впрочем, используются только frexp() и ldexp(). Конкретная реализация этих функций очень проста, но машинно-зависима. При разделении числа на мантиссу и экспоненту, мантисса оказывается в пределах [0.5,1). Если при этом экспонента нечетная, мантисса умножается на 2, тем самым область определения становится [0.5,2). К мантиссе применяется алгоритм Ньютона с начальным приближением 1, и затем окончательный результат получается с помощью применения ldexp() с половинным значением экспоненты.

Для машинно-независимого варианта выделение экспоненты заменяется серией последовательных делений исходного значения на 16, пока аргумент не станет определяться на интервале [1,16]. Если исходный аргумент был меньше 1, то перед серией делений обращаем его. Алгоритм Ньютона применяется с начальным приближением 2. Окончательный результат получается серией последовательных умножений на 4 и дальнейшим обращением, если аргумент обращался.

Исаак Ньютон разработал метод извлечения квадратного корня, который восходил еще к Герону Александрийскому (около 100 г. н.э.). Метод этот (известный как метод Ньютона) заключается в следующем.

Пусть A1 — первое приближение числа sqrt(X) (в качестве A1 можно брать значения квадратного корня из натурального числа — точного квадрата, не превосходящего х) . На практике можно брать и 1, всеравно будет сходимость. Или рекомендуется взять X/2, так итераций будет меньше.

Читайте также:  Если взломали почтовый аккаунт

Следующее, более точное приближение числа найдется по формуле:

Третье, еще более точное приближение:

Таким образом, (n+1) приближение найдется по формуле:

Можно задавать точность расчета, то есть считать до тех пор, пока предыдущее значение и текущее значение не будут различаться на конкретную величину, например 0.000001.

Рекомендуем к прочтению

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

code

Adblock detector