Monday, December 7, 2015

Faster method than Newton-Raphson

This will be considering a replacement of the Newton-Raphson method for better performance changing:

First recall that the Newton-Raphson method started as a generalization of the Babylonian method for finding square roots... I'll start the same way by showing this method speeds up finding square roots...

Starting with a reasonably close approximation to the square root of N such as the closest perfect square, one can first use this formula where x is the estimate.

For example with an N of 61, we can chose x to be 7 because 7^2=49 is close to 61 and then:

Now recursively use the formula again:

Which is very close to the square root of 61 compare:

After 2 iterations it's already accurate to 9 decimal places! Two iterations of the Newton Raphson method with the same initial conditions only correctly estimates 3. In fact it is better than 3 iterations of Newton-Raphson by a couple of decimal places...There are 7 arithmetical steps per iteration of this method and 5 for Newton-Raphson, so two iterations of this method take 14 arithmetic steps and get a better result than when Newton-Raphson takes 15 arithmetical steps, and Newton-Raphson would need 20 arithmetical steps to improve upon two iterations of this method... I think the difference becomes more marked when extreme accuracy is needed or when just the amount of accuracy that this method gives over Newton-Raphson is needed... And of course when very many of these calculations are needed...

So for another example if f(x) is 2*e^(x)-3 starting with a guess of .5 and doing two iterations we get:

That is very close to the actual root of:
Three iterations of Newton's method only correctly gets 5 decimal places right for more arithmetic...

No comments:

Post a Comment