什么是Newton-Raphson Square Method的时间复杂度？

Question

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

• 维基百科:牛顿的方法

Answer 1

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

使用如上所述的牛顿方法,如果已知良好的初始近似,计算具有n位精度的函数f(x)的根的时间复杂度是O((\ log n)F(n))其中F(n)是计算f(x)/ f'(x)\的成本,具有n位精度.

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

如果可以用可变精度评估f(x),则可以改进算法.由于牛顿方法的"自校正"性质,意味着一旦达到二次收敛阶段它就不受小扰动的影响,只需要在近似有m-的步骤中使用m位精度.数字准确性.因此,第一次迭代的精度可以是x_0精度的两倍,第二次迭代的精度是精度的四倍,依此类推.如果适当选择精度级别,则只有最终迭代需要f(x)/ f'(x)\,才能以完全n位精度进行计算.假设F(n)超线性增长,实际情况就是如此,寻找根的成本因此只有O(F(n)),其常数因子接近于1.