The second degree terminated Taylor expansion (cf. STEP 5) about x0 is
where lies between
Ignoring the remainder term and writing
should be a better estimate of the root than x0. Even better approximations may be obtained by repetition (iteration) of the process, which then becomes
Note that if f is a polynomial, we can use the recursive procedure of STEP 5 to compute
The geometrical interpretation is that each iteration provides the point at which the tangent at the original point cuts the x-axis (see Figure 9). Thus the equation of the tangent at (xn, f (xn)) is
so that (xn+1, 0) corresponds to
We will use the Newton-Raphson method to find the positive root of the equation sinx = x2, correct to 3D.
It will be convenient to use the method of false position to obtain an initial approximation. Tabulating, one finds
With numbers displayed to 4D, we see that there is a root in the interval 0.75 < x < 1 at approximately
Next, we will use the Newton-Raphson method; we have
Consequently, a better approximation is
Repeating this step, we obtain
Since f(x2) = 0.0000, we conclude that the root is 0.877 to 3D.
If we write
the Newton-Raphson iteration expression
may be written
We observed (see STEP 9) that, in general, the iteration method converges when near the root. In the case of Newton-Raphson, we have
so that the criterion for convergence is
i.e., convergence is not as assured as for the bisection method (say).
The second degree terminated Taylor expansion about xn is
where is the error at the n-th iteration and .
Since , we find
But, by the Newton-Raphson formula,
whence the error at the (n + 1)-th iteration is
provided en is sufficiently small. This result states that the error at the n + 1-th iteration is proportional to the square of the error at the nth iteration; hence, if , an answer correct to one decimal place at one iteration should be accurate to two places at the next iteration, four at the next, eight at the next, etc. This quadratic (second-order) convergence outstrips the rate of convergence of the methods of bisection and false position!
In relatively little used computer programs, it may be wise to prefer the methods of bisection or false position, since convergence is virtually assured. However, for hand calculations or for computer routines in constant use, the Newton-Raphson method is usually preferred.
Since , we have the Newton-Raphson iteration formula:
a formula known to the ancient Greeks. Thus, if a = 16 and x0 = 5, we find to 4D x1 = (5 + 3.2)/2 = 4.1, x2 = (4.1 + 3.9022)/2 = 4.0012, and x3 = (4.0012 + 3.9988)/2 = 4.0000.
for finding the k-th root of a.
to compute to 5S the square root of 10, using the initial guess 1.