0

http://introcs.cs.princeton.edu/java/13flow/Sqrt.java.html：

public class Sqrt { 
    public static void main(String[] args) { 

        // read in the command-line argument
        double c = Double.parseDouble(args[0]);
        double epsilon = 1e-15;    // relative error tolerance
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        while (Math.abs(t - c/t) > epsilon*t) {
            t = (c/t + t) / 2.0;
        }

        // print out the estimate of the square root of c
        System.out.println(t);
    }

}

问题是..我非常了解程序本身是如何工作的。我遇到的问题是方程 f(x) = x^2 - c 以及它与上面的代码的关系。比如，为什么将它除以 x 使得 x(x - c/x)？当涉及到其中一些示例时，似乎缺少数学解释。换句话说，我正在从简单的数学角度寻找解释，而不是编码那么多。

4

4 回答 4

4

你被给了c，你想解决

t = sqrt(c)

或等效地，

c = t^2

或者再一次，

c - t^2 = 0.

我将调用上面的方程f(t) = 0（没有提及，c因为它是一个给定的常数）。牛顿法对 的试验值进行迭代t，我将对其进行标记t_i, t_{i+1}, ...。

泰勒展开到一阶是：

f(t_i + dt_i) = f(t_i) + dt_i * f'(t_i) + ...

所以如果你没有f(t_i) = 0，你添加一个dt_i这样的

f(t_i + dt_i) nearly = 0 = f(t_i) + dt_i * f'(t_i) + ...

因此dt_i = -f(t_i) / f'(t_i)， ief(t_i + -f(t_i) / f'(t_i))比 更接近于零f(t_i)。

如果你对 进行导数f(t) = c - t^2，你会发现代码中的方程t_{i+1} = (c / t_i + t_i) / 2只是上面估计t_{i+1} = t_i + dt_i的迭代公式。dt_i

这是迭代方法，所以它没有给出精确的解决方案。您需要决定何时停止（足够的精度），否则算法将永远持续下去。这就是为什么你检查f(t_i) < threshold而不是 true f(t_i) = 0。在他们的情况下，他们选择了threshold = epsilon * t^2; 我认为使用了乘法是因为如果您使用固定常数作为阈值，您可能会遇到数值精度问题（即，如果您正在玩数万亿，由于浮点的有限精度t^2，您永远无法获得固定精度10^{-10}表示。）

于 2012-01-23T14:00:00.467 回答
1

基于代码，Javadoc 评论中已经解释了以下内容：

 *  Computes the square root of a nonnegative number c using
 *  Newton's method:
 *     - initialize t = c
 *     - replace t with the average of c/t and t
 *     - repeat until desired accuracy reached
于 2012-01-23T12:52:32.060 回答
1

好的，我会给它一个bash（见内联评论）：

public class Sqrt { 
    public static void main(String[] args) { 

        // read in the command-line argument (i.e. this is the value that we want
        // square root from.)
        double c = Double.parseDouble(args[0]); 

        // Since the the square root of non-squares are irrational, we need some
        // error tolerance.  In other words, if the answer is less than epsilon wrong
        // we'll take it.  
        double epsilon = 1e-15;    // relative error tolerance

        // t is our first guess (c / 2.0 works well too - in fact it tends to be
        // better.)
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        // The condition here is rather elegant and optimized... to see why it works,
        // simply break it up.  The absolute is there to cater for negative values, but
        // for c >= 0:
        //   | c - c/t | > epsilon * t
        //   t * ( t - c / t ) > epsilon
        //   tt - c = > epsilon)
        while (Math.abs(t - c/t) > epsilon*t) {
            // Improve the guess by applying Newton's genius :-)
            // Take the original number, divide by the guess add t and take the
            // average.
            t = ( c / t + t) / 2.0;
        }

    // print out the estimate of the square root of c
    System.out.println(t);
}

}
于 2012-01-23T13:02:14.397 回答
0

ejlab.net 杰尔玛

我相信上面提到的代码来自 R.Sedgewick 的书“Java 编程简介”，第 62 页。他在书中试图说的是，您可以将f(x)=x^2-c其用作特殊情况来查找任何正数的平方根。那么它是如何工作的：

牛顿法规定X(n+1)=X(n)-(F(X(n))/F'(X(n)))。假设在 中F(X)=X^2-C，C=2因为我们正在寻找 2 的平方根（如果你想找到 36 的平方根，那么C=36等等）。那么函数的一阶导数F(X)是F'(X)=2X。应用牛顿法，我们得到

X(n+1)=X(n)-((X^2-C)/(2X))

因为X(0)=2我们得到 n=1, X(1)=2-(2^2-2)/(2*2)> X(1)=1.5; n=2 X(2)=1.5 -(1.5^2-2)/(2*1.5)>X(2)=1.41666667 等等……

于 2013-04-04T22:40:57.897 回答