Newton's Method

One of the most widely used methods of solving equations is Newton's method. Like the previous ones, this method is also based on a linear approximation of the function but does so using a tangent to the curve. The figure below gives a graphical description. Starting from a
single initial estimate, x, that is not too far from a root, we move along the tangent to its intersection with the x-axis, and take that as the next approximation. This is continued until either the successive x-values are sufficiently close or the value of the function is sufficiently near zero.
The calculation scheme follows immediately from the right triangle shown in The figure, which has the angle of inclination of the tangent line to the curve at x = xo as one of its acute angles:

Pic:

We continue the calculation scheme by computing

Pic:

Newton's algorithm is widely used because, at least in the near neighborhood of a root, it is more rapidly convergent than any of the methods discussed so far. We show in a later section that the method is quadratically convergent, by which we mean that the error of each step approaches constant K times the square of the error of the previous step. The net result of this is that the number of decimal places of accuracy nearly doubles at each iteration. However, there is the need for two function evaluations at each step, f(xn and f '(xn), and we must obtain the derivative function at the start.

To determine a root off (x) = 0, given xo reasonably close to the root,
Compute f (Xn), f’(Xo).
If (f (Xo) ≠ 0) And (f’(Xo)≠  0) Then
Repeat
Set X1 = X0.
Set Xo = Xo - f(xo)/f'(x0).
Until (|X1 - X0| < tolerance value 1) Or
|f(Xo)  |< tolerance value 2).
End If.

Note: The method may converge to root different from the expected one or diverge if the starting value is not close enough to the root.

When Newton's method is applied to polynomial functions, special techniques facilitate such an application. We consider these in a later section of this chapter. In some cases, Newton's method will not converge. Figure 1.4 illustrates this situation. Starting with Xo, one never reaches the root r because X6 = X1 and we are in an endless loop. Observe also that if we should ever reach the minimum or maximum of the curve, we will fly off to infinity. We will develop the analytical condition for this in a later section and show that Newton's method is quadratically convergent in most cases.