Newton's method

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

bigeq-1.png

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

fig19-1.png
bigeq-5.png

We now repeat the process recursively:

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

bigeq-7.png

let us rewrite that equation as

bigeq-8.png

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

bigeq-9.png

The recurrence relation becomes:

bigeq-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