4 Oct 2014

Algo #116: Square Root (using Newton Ralpson Method)

Problem Statement: 
        Calculate the square root of a number using Newton Raphson's Method .

Download Source Code
Solution:

Newton Raphson's method is used for finding successive better approximate roots of a functions, at every successive iteration , the result tends towards the root of the function.
               
In this technique we use the logic of approximation by calculating the tangent line of the function f(x), derivative of the function f(x) represents the tangent line to the function curve f(x).

Geometrical Interpretation:
    Let r be a root of f(x), that is f(r) =0. Assume that $f'(r) \neq 0$. Let x1  be a number close to r (which may be obtained by looking at the graph of f(x)). The tangent line to the graph of f(x) at (x1,f(x1)) has x2 as its x-intercept


Fig1: Representing f(x) and f '(x) and r being the root f(r)=0
From the above picture, we see that x2 is getting closer to r.  Successive iterations will lead to results closer to 'r'. x1 was the intial guess which lead to a better result x2.

Now,



here Er represent the percentage error.

Lets calculate the square root of 44.89,
     we will assume out initial guess to be 44.89, using the formula


Now code up our logic for calculating the square root.
float squareRoot(float num)
 {
  float x1 = num,x2=0,temp=num,e=0.001f;
  do 
  {
   x1 = temp;
   x2 = 0.5f * (x1 + num/x1);
   temp=x2;
   
  }while(Math.abs(x2-x1)> e);
  
  System.out.println(num + " ----> " + x2);
  return x2;
 }

Rare Scenarios which might happen when using Newton Raphson Method:

1. If the initial estimate is not close enough to the root, the Newton Method may not converge, or may converge to the wrong root.

2. The successive estimates of the Newton Method may converge to the root too slowly, or may not converge at all.

Please comment and post your suggestions.
Happy Coding !! :)

References:
1. http://www.sosmath.com/calculus/diff/der07/der07.html
2. https://www.math.ubc.ca/~anstee/math104/104newtonmethod.pdf
3. http://www.codecogs.com/eqnedit.php
4. Wiki

2 comments: