Newton-Raphson method

This is another post inspired by the New Turing Omnibus, which is a great book, even if its author believes in some very stupid things.

The Newton-Raphson method is a way to find the roots of a polynomial equation. It does not always work, but it is a powerful tool when it does.

Eg., let us say we had y=3x^4+2x^2-x-15, the root of this is the value of x that causes the equation to evaluate to zero.

To do this we can first estimate a root value, evaluate the function, if it is not zero then use as the next guess the point where the tangent to the function at the first guess evaluates to zero. We can compute the tangent from the derivative.

Eg., in the case here f(x) = 3x^4+2x^2-x-15, so f^\prime(x) = 12x^3 + 4x -1.

How to find the point where the tangent evaluates to zero? Well, the formula for a tangent (or any straight line) is of the form y=kx + c and in this case, with our guess x_0 , that means y = f^\prime(x_0)x + c and, at the guessed point f^\prime(x_0)x_0 + c = f(x_0).

Clearly the tangent line is zero when f^\prime(x_0)x = -c and we know that -c = f^\prime(x_0)x_0-f(x_0).

So f^\prime(x_0)x = f^\prime(x_0)x_0 - f(x_0)

Therefore our new guess, x , should be x_0 -\frac{f(x_0)}{f^\prime(x_0)}

If we try the example here, we can start with a guess of 2 – which evaluates to 39 and has a derivative of 103, giving a new guess of 1.62 (to two significant places).

In turn this evaluates to 9.29 and so on…

Update:I tested this out on a spreadsheet and it took just seven iterations to get a root that evaluated to zero at 9 significant places:


3 responses to “Newton-Raphson method”

  1. Under relatively mild assumptions about the smoothness of the function (for one thing, it obviously needs to be at least once differentiable), N-R is locally quadratically convergent. That means that once you get near enough to a root, the error in each solution is bounded by a constant multiple of the square of the previous error. Roughly speaking, once you’re close, you double the number of correct decimal places with each iteration (until either you stop or run out of numerical precision).

    1. Yes, you can see that very clearly on a spreadsheet or a logarithmic plot.

%d bloggers like this: