具有指定精度的牛顿法

Question

我正在尝试用 Java 编写一个函数来计算数字的 n 次方根。我正在使用牛顿法。但是，用户应该能够指定他们想要的精度位数。这是我遇到麻烦的部分，因为我的答案通常不完全正确。相关代码在这里：http://pastebin.com/d3rdpLW8。我如何修复此代码，使其始终给出至少 p 位精度的答案？ （无需做不必要的工作）

import java.util.Random;

public final class Compute {

    private Compute() {
    }

    public static void main(String[] args) {
        Random rand = new Random(1230);
        for (int i = 0; i < 500000; i++) {
            double k = rand.nextDouble()/100;
            int n = (int)(rand.nextDouble() * 20) + 1;
            int p = (int)(rand.nextDouble() * 10) + 1;
            double math = n == 0 ? 1d : Math.pow(k, 1d / n);
            double compute = Compute.root(n, k, p);
            if(!String.format("%."+p+"f", math).equals(String.format("%."+p+"f", compute))) {
                System.out.println(String.format("%."+p+"f", math));
                System.out.println(String.format("%."+p+"f", compute));
                System.out.println(math + " " + compute + " " + p);
            }
        }
    }

    /**
     * Returns the n-th root of a positive double k, accurate to p decimal
     * digits.
     * 
     * @param n
     *            the degree of the root.
     * @param k
     *            the number to be rooted.
     * @param p
     *            the decimal digit precision.
     * @return the n-th root of k
     */
    public static double root(int n, double k, int p) {     
        double epsilon = pow(0.1, p+2);
        double approx = estimate_root(n, k);
        double approx_prev;

        do {
            approx_prev = approx;
            // f(x) / f'(x) = (x^n - k) / (n * x^(n-1)) = (x - k/x^(n-1)) / n
            approx -= (approx - k / pow(approx, n-1)) / n;
        } while (abs(approx - approx_prev) > epsilon);
        return approx;
    }

    private static double pow(double x, int y) {
        if (y == 0)
            return 1d;
        if (y == 1)
            return x;
        double k = pow(x * x, y >> 1);
        return (y & 1) == 0 ? k : k * x;
    }

    private static double abs(double x) {
        return Double.longBitsToDouble((Double.doubleToLongBits(x) << 1) >>> 1);
    }

    private static double estimate_root(int n, double k) {
        // Extract the exponent from k.
        long exp = (Double.doubleToLongBits(k) & 0x7ff0000000000000L);
        // Format the exponent properly.
        int D = (int) ((exp >> 52) - 1023);
        // Calculate and return 2^(D/n).
        return Double.longBitsToDouble((D / n + 1023L) << 52);
    }
}

Answer 1

如果您想要 4 位小数的精度，只需迭代直到更新小于 0.0001。

也就是说，如果您想要 n 位精度，请将 epsilon 设置为 Math.pow(10, -n)。

Answer 2

我们回想一下牛顿法的误差分析是怎么说的。基本上，它为我们提供了第 n 次迭代的误差作为第 n-1 次迭代误差的函数。

那么，我们如何判断误差是否小于k呢？我们不能，除非我们知道 e(0) 处的错误。如果我们知道 e(0) 处的错误，我们就可以用它来找到正确的答案。

你能做的就是说“e(0) <= m”。然后您可以找到 n 使得 e(n) <= k 为您想要的 k。然而，这需要知道半径中 f'' 的最大值，这（通常）与求 x 截距一样困难。

您要检查的是误差变化是否小于 k，这是一种完全可以接受的方法。但它不会检查误差是否小于 k。正如 Axel 和其他人所指出的，还有许多其他根近似算法，其中一些会产生更容易的错误分析，如果您确实想要这个，您应该使用其中之一。

Answer 3

您的代码中有错误。您的 pow() 方法的最后一行应为
返回 (y & 1) == 1 ? k : k * x;
而不是
return (y & 1) == 0 ? k：k*x；