Explanation of newton's method example on java

Question

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);
    }

}

The thing is..I understand perfectly well how the program works itself. The problem I have is with the equation f(x) = x^2 - c and how that relates to the code above. Like, why divide it by x so that x(x - c/x)? There seems to be a missing mathematical explanation when it comes to some of these examples. In other words, I'm looking for an explanation from a simple mathematical stand point, NOT coding as so much.

Answer 1

You are given c and you want to solve

t = sqrt(c)

or equivalently,

c = t^2

or then again,

c - t^2 = 0.

I'll call the above equation f(t) = 0 (no mention of c since it is a given constant). Newton method iterates over trial values of t, which I'll label t_i, t_{i+1}, ....

The Taylor expansion to 1st order is:

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

So if you don't quite have f(t_i) = 0, you add a dt_i such that

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

So dt_i = -f(t_i) / f'(t_i), i.e. f(t_i + -f(t_i) / f'(t_i)) is closer to zero than f(t_i).

If you do the derivatives for f(t) = c - t^2, you'll see that the equation in the code t_{i+1} = (c / t_i + t_i) / 2 is just the iterative formula t_{i+1} = t_i + dt_i with the dt_i estimated above.

This is iterative method, so it does not give an exact solution. You need to decide when you want to stop (sufficient precision), otherwise the algorithm would go on forever. That's why you check f(t_i) < threshold instead of the true f(t_i) = 0. In their case they chose a threshold = epsilon * t^2; I think the multiplication by t^2 was used because if you used a fixed constant as a threshold, you might run into numerical accuracy problems (i.e. if you are playing with trillions, you could never get an fixed accuracy of 10^{-10} due to the finite precision of floating point representation.)

Answer 2

Based on the code, the following has already been explained on the Javadoc Comment:

 *  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

Answer 3

Ok, I'll give it a bash (see inline comments):

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);
}

}

Answer 4

ejlab.net jelmar

I believe the above mentioned code is from R.Sedgewick's book 'Introduction to Programming in Java', page 62. What he tries to say in the book is that you can use f(x)=x^2-c as a special case to find the square root of any positive number. So how it works:

Newton's method states X(n+1)=X(n)-(F(X(n))/F'(X(n))). Assume that in F(X)=X^2-C, where C=2 since we are looking for square root of 2 (if you want to find square root of 36 then C=36 etc). Then the first derivative of the function F(X) is F'(X)=2X. Applying the Newton's method we get

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

for X(0)=2 we get 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 and so on...