**- DSP log - http://www.dsplog.com -**

Newton’s method to find square root, inverse

Posted By __Krishna Sankar__ On December 25, 2011 @ 7:36 pm In __DSP__ | __1 Comment__

Some of us would have used Newton’s method ^{[1]} (also known as Newton-Raphson method) in some form or other. The method has quite a bit of history, starting with the Babylonian way of finding the square root ^{[2]} and later over centuries reaching the present recursive way of finding the solution. In this post, we will describe Newton’s method and apply it to find the square root and the inverse of a number.

We know that the derivative of a function at is the slope of the tangent (red line) at i.e.,

.

Rearranging, the intercept of the tangent at x-axis is,

.

From the figure above, can see that the tangent (red line) intercepts the x-axis at which is closer to the where compared to . Keep on doing this operation recursively, and it converges to the zero of the function OR in another words the root of the function.

In general for iteration, the equation is :

.

Let us, for example try to use this method for finding the square root of D=100. The function to zero out in the Newton’s method frame work is,

, where .

The first derivative is

.

The recursive equation is,

.

**Matlab code snippet**

clear ; close all; D = 100; % number to find the square root x = 1; % initial value for ii = 1:10 fx = x.^2 - D; f1x = 2*x; x = x - fx/f1x; x_v(ii) = x; end x_v' = 50.5000000000000 26.2400990099010 15.0255301199868 10.8404346730269 10.0325785109606 10.0000528956427 10.0000000001399 10.0000000000000 10.0000000000000 10.0000000000000

We can see that the it converges within around 8 iterations. Further, playing around with the initial value,

a) if we start with initial value of x = -1, then we will converge to -10.

b) if we start with initial value of x = 0, then we will not converge

and so on…

Newton’s method can be used to find the inverse of a variable D. One way to write the function to zero out is, but we soon realize that this does not work as we need know in the first place.

Alternatively the function to zero out can be written as,

.

The first derivative is,

.

The equation in the recursive form is,

.

**Matlab code snippet**

clear ; close all; D = .1; % number to find the square root x = [.1:.2:1]; % initial value for ii = 1:10 fx = (1./x) - D; f1x = -1./x.^2; x = x - fx./f1x; x_v(:,ii) = x; end plot(x_v'); legend('0.1', '0.3', '0.5', '0.7', '0.9'); grid on; xlabel('number of iterations'); ylabel('inverse'); title('finding inverse newton''s method');

The following plot shows the convergence of inverse computation to the right value for different values of for this example matlab code snippet.

**Figure : convergence of inverse computation**

To find the minima of a function, we to find where the derivative of the function becomes zero i.e. .

Using Newton’s method, the recursive equation becomes :

.

We have briefly gone through the Newton’s method and its applications to find the roots of a function, inverse, minima etc. However, there are quite a few aspects which we did not go over, like :

a) Impact of the initial value on the convergence of the function

b) Rate of the convergence

c) Error bounds of the converged result

d) Conditions where the convergence does not happen

and so on…

Hoping to discuss those in another post…

Wiki on Newton’s method ^{[1]}

Article printed from DSP log: **http://www.dsplog.com**

URL to article: **http://www.dsplog.com/2011/12/25/newtons-method-square-root-inverse/**

URLs in this post:

[1] Newton’s method: **http://en.wikipedia.org/wiki/Newton**

[2] Babylonian way of finding the square root: **http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method**

[3] click here to SUBSCRIBE : **http://www.feedburner.com/fb/a/emailverifySubmit?feedId=1348583&loc=en_US**

Click here to print.

Copyright © 2007-2012 dspLog.com. All rights reserved. This article may not be reused in any fashion without written permission from http://www.dspLog.com.