什么是牛顿迭代最小二乘法的时间复杂度? [英] what is Newton-Raphson Square Method's time complexity?
问题描述
什么是牛顿迭代最小二乘法的时间复杂度?
What is the time complexity of the Newton-Raphson square method?
推荐答案
从<一个href="http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity">http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity:
使用牛顿方法的描述 以上,时间复杂 计算函数f的根(x)的 用n位precision,条件是 一个良好的初始近似而着称, 为O((\ log n)的F(N)),其中F(n)是 计算函数f(x)/ F'(x)的\,具有成本 正位precision。
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.
不过,这取决于你的precision要求,你可以做的更好:
However, depending on your precision requirements, you can do better:
如果F(X)可以与可变评价 precision,算法可以是 改进。由于 自我纠正牛顿的性质 方法,也就是说,它是不受 小扰动一旦 达到二次阶段 收敛,但是,仅需要 使用m-数位precision在一个步骤,其中 近似具有m位数字 准确性。因此,第一迭代 可以用precision进行 两倍高X_0的准确性, 第二次迭代以precision 四倍高,等等。如果 precision水平是适当的选择, 只有最后一次迭代,需要 函数f(x)/ F'(x)的\,以全评价 正位precision。条件是F(n)的 超线性增长,这是这种情况 找到的在实践中,成本 因此,根只有O(F(N)),具有 常数因子接近于1。
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.
这篇关于什么是牛顿迭代最小二乘法的时间复杂度?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!