Sunday, May 17, 2009

In Praise of Newton-Raphson

The Newton-Raphson technique for finding roots of equation via an iteration process is one of the first numerical techniques taught to students of mathematics. As a technique, it illustrates important features common to many numerical techniques used in mathematics, namely:

A) it is based on a very simple mathematical idea, that is, that extrapolating a value from a curve back to the x axis, by assuming a linear relationship, is a good way to form a more accurate guess for the intercept of the curve with the x axis,

B) after a few manual calculation using the technique, you are eternally grateful to the inventors of the computer (Hail Babbage, Turing, Zuse and friends !)

C) it is very simple to turn the procedure into an automated program,

D) the better the initial guess, the quicker you will arive at the solution and save computational time,

E) the more accurate the solution you desire, the greater the number of iterations,

F) finding a strategy for dealing with rounding errors and storing numbers with the appropriate level of precision between iterations are not trivial problems,

G) without care, it is possible to diverge of the wrong solution or (even worse) even to send the computer off to an unending loop of diverging solutions (i.e. "wrong" over and over and over again), and

H) it really works - there are few curves that it can't deal with but these are relative oddities compared to the great number of curves that the technique solves readily.

As a young engineer, I wrote several programs that used the Newton-Raphson technique to find solutions to the various equations I had formed in my models. Invariably, once I had found a good method for avoiding divergent solutions, the Newton-Raphson routine would find a solution. Like many before me, I found the technique surprisingly powerful , verstaile and useful. Now, students can "play" with the technique using graphical calculators or spreadsheet programs on a lap top. In essense, once you have a "curve", whether it be formed by data or through a known equation, the technique can be used to find solution for particular intercepts (e.g. y = 0) without having an analytical solution - that may not be possible or indeed just beyond your algebraic ability.

No comments:

Post a Comment