Метод Ньютона для извлечения корня

Вначале использовал бисекцию, но решил перейти на метод ньютона, ибо он вроде быстрее, но...

Может я совсем не понял его, но методом Ньютона получается не корень, а какой-то бред.
Ну вот например нужен корень 5ой степени из 32:
f(x_i)/f'(x_i) будет (x^(1/n))/((x^(1/n))')=n*x, значит равно 5x
Начальное приближение пусть будет 1
Тогда выходит что x_i+1=1-5*1=-4
x_i+2=-4+20=16
x_i+3=16-80=64
и вот что-то мы всё отдаляемся и отдаляемся от корня (и получается что этим методом находится только один корень??, это как вообще?)

Вот и как нам тогда выбирать это приближение и понять что пора прекратить (ибо каждый раз возводить в степень не вариант, ибо это будет не лучше бисекции, которая даёт результат невероятно долго)? Да и как вообще пользоваться этим методом?

Сссылка на мою основную проблему, где есть код и условие: Алгоритм быстрого извлечения корня (длинная арифметика)

Основывался на этом: http://www.e-maxx-ru.1gb.ru/algo/roots_newton

0

Сообщение от Clagron каждый раз возводить в степень не вариант, ибо это будет не лучше бисекции, которая даёт результат невероятно долго

На самом деле если воспользоваться правильной итерационной формулой и хорошим начальным приближением, то метод Ньютона всё-равно будет заметно быстрее бисекции, несмотря на необходимость возведения в степень. Просто для больших чисел количество итераций может уменьшиться на один или несколько порядков, по сравнению с бисекцией.

Добавлено через 43 минуты
Ну и чтобы всё в одном месте попробую описать метод Ньютона применительно к нахождению корня n-й степени.
Итак, задача состоит в том, чтобы вычислить x как корень n-й степени из числа a:



Эту задачу можно сформулировать как поиск решения следующего уравнения:



Метод Ньютона позволяет найти решение уравнения



поэтому наше уравнение можно переписать как



откуда



Поиск решения по методу Ньютона заключается в многократном применении итерационной формулы



В общем случае эта последовательность может и не сходиться к решению, но для нашей задачи этот метод работает очень неплохо. После подстановки в итерационную формулу нашей функции и её производной и несложных преобразований получаем



Осталось выбрать начальное приближение, с которого начинать поиск. Для данной задачи, если a > 1, то выгоднее начинать поиск с числа несколько большего, чем истинное решение, нежели с несколько меньшего. Поэтому я предлагаю следующий метод, который несложно реализовать программно.
В качестве начального приближения возьмём минимальную степень двойки, которая при возведении в степень n будет больше заданного числа.



То есть начинаем с x₀ = 1 и умножаем его на 2 до тех пор, пока x₀ⁿ не станет больше или равнымa.

1