2

我从http://blog.shay.co/newtons-method/中提取了这段代码：

//a - the number to square root
//times - the number of iterations
public double Sqrt(double a, int times)
{
    if (a < 0)
        throw new Exception("Can not sqrt a negative number");
    double x = 1;
    while (times-- > 0)
        x = x / 2 + a / (2 * x);
    return x;
}

如果存在一个数字的迭代次数，那么一个好的经验法则是什么？ （例如，“使用 n/2 次迭代”。）

4

2 回答 2

5

如果存在一个数字的迭代次数，那么一个好的经验法则是什么？

牛顿法具有二次收敛性，即。在算法的每一步，答案中有效数字的数量都会翻倍。因此，该算法及时计算平方根，精度高达 D 位O(log D)。因此，循环中的迭代次数将取决于预期的准确性。因此，要对结果的准确性进行细粒度控制，您可以在代码中添加一个检查，当估计值不在误差范围之外时返回答案。

public double Sqrt(double a){
    if (a < 0)
        throw new Exception("Can not sqrt a negative number");
    double error = 0.00001;
    double x = 1;
    while (true){
        double val = x*x;
        if(abs(val-a) <= error)
             return x;
        x = x / 2 + a / (2 * x);
    }
}
于 2014-04-26T06:40:42.783 回答
0

如果您希望通过固定迭代次数保证相对精度，则通过除以a4 来准备迭代，直到结果介于 1/2 和 2 之间。或者如果从小于 1 的值开始乘以。记住除法次数，自从

sqrt(a)=2^k*sqrt(4^(-k)*a)

需要将结果乘以相同数量的因子 2。然后减少的平方根的相对误差a将下降

3*(1/6)^(2^m)

迭代之后m，或者更快，根据

(x[m]-sqrt(a))/(x[m]+sqrt(a)) = ((1-sqrt(a))/(1+sqrt(a)))^(2^m)

通过使用浮点指数的访问函数，frexp以及ldexp在 C 数学库中，Java 中的 Double 类中的类似方法，您可以最快地提取和操作所需的 4 和 2 的幂。

于 2014-04-27T08:02:06.923 回答