## 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:

 1.42483