Newton's method

Given a function f, we want to find its roots. Namely, the values of x such that:

eq-1.png

We choose an arbitrary initial value eq-2.png and from it we calculate a new value eq-3.png which is the point where the tangent of f, at eq-2.png, passes through the eq-4.png axis:

fig19-1.png
eq-5.png

We now repeat the process recursively:

eq-6.png

In an interval where the function is continuous and increasing, that sequence will approach the nearest root on the left of the starting value. If the function is continuous and decreasing, the sequence will approach the nearest root on the right.

Example

Compute the square root of 5, using Newton's method.

The number we want to compute is:

eq-7.png

let us rewrite that equation as

eq-8.png

Thus, our problem is equivalent to finding the roots of the function

eq-9.png

The recurrence relation becomes:

eq-10.png

Using Maxima (http://maxima.sourceforge.net), and an initial value of 1, we can find the first terms in the sequence: 

x : 1;
for i thru 10 do
  (x: float((x + 5/x)/2), print(x));

The sequence seems to converge rather fast: 

3.0
2.333333333333334
2.238095238095238
2.236068895643363
2.236067977499978
2.23606797749979
2.23606797749979
2.23606797749979
2.23606797749979
2.23606797749979