Newton-Raphson Method (see ws1)

The Newton-Raphson method is similar to the secant method, but can be argued on a more theoretical basis. Let us assume that is sufficiently smooth on the interval , i.e. that its first and second derivative are continuous functions on . Let be an approximation to the root , such that is small and . Then the Taylor series about is given by

> f(x)=taylor(f(x),x=q,2);

so that at , we find

> 0=subs(x=p,taylor(f(x),x=q,2));

Assuming that the approximation is close to the root, we can ignore the higher order terms in the series expansion and calculate as the solution of

> eq:=f(q)+D(f)(q)*(p-q)=0;

or,

> p:=solve(eq,p);

> p:=collect(%,q);

This leads to the following algorithm:

>

Step 1: obtain an approximation, .

Step 2: calculate the next approximation as

.

Step 3: If then is the root, otherwise, if then is the required approximation to the root, else repeat step 2.

>

This is illustrated in the following example:

> f:=x->cos(x)-0.4;

> epsilon:=10.^(-7);x[0]:=0.5;x[1]:=x[0]-(f(x[0])/D(f)(x[0]));

> for i from 1 by 1 to 10 while abs((x[i]-x[i-1])/x[i]) > epsilon do x[i+1]:=x[i]-(f(x[i])/D(f)(x[i])); od;

> abs((x[5]-x[4])/x[5]);

Notice the construction which allows us to stop the loop as soon as the required accuracy is obtained. But remember that when this accuracy is not obtained after the maximum number of steps, the final value is not yet as accurate as we demanded! Nevertheless, it is wise to restrict the maximum number of times a loop should be executed when working on a computer.

Grapically, the Newton-Raphson Method corresponds to finding the tangent line to the graph of at the estimated value of the root. The next estimate is then the zero of this tangent line. This is illustrated in the following picture:

>

The Newton-Raphson Method converges very rapidly and is one of the more popular methods. However, the method can not be applied when on of the approximations , has . In this case, the tangent line is horizontal and will not have an intersection with the -axis.

There are also more special cases in which the Newton-Raphson Method may fail to produce a converging sequence of approximations.