algorithm - Newton-Raphson Square Method 的时间复杂度是多少？

Question

Newton-Raphson 平方法的时间复杂度是多少？

• Wikipedia: Newton's method

Answer 1

来自 http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity :

Using Newton's method as described above, the time complexity of calculating a root of a function f(x) with n-digit precision, provided that a good initial approximation is known, is O((\log n) F(n)) where F(n) is the cost of calculating f(x)/f'(x)\, with n-digit precision.

但是，根据您的精度要求，您可以做得更好:

If f(x) can be evaluated with variable precision, the algorithm can be improved. Because of the "self-correcting" nature of Newton's method, meaning that it is unaffected by small perturbations once it has reached the stage of quadratic convergence, it is only necessary to use m-digit precision at a step where the approximation has m-digit accuracy. Hence, the first iteration can be performed with a precision twice as high as the accuracy of x_0, the second iteration with a precision four times as high, and so on. If the precision levels are chosen suitably, only the final iteration requires f(x)/f'(x)\, to be evaluated at full n-digit precision. Provided that F(n) grows superlinearly, which is the case in practice, the cost of finding a root is therefore only O(F(n)), with a constant factor close to unity.