OPTIMIZATION 347At point [xi,f(xi)], a tangent can be extended to the x axis and the point of intersection of this tangent
and the axis becomes the new guess xi+1 for the root.
Forxi+1 as the root xr, the original relation
becomes
0 = g(xi) + g′(xi)(xr – xi) +^1 / 2 g′′(ξ) (xr – xi)^2Subtracting the Newton-Raphson relation with the
one above, we have
0 = g′(xi)(xr – xi+1) +^1 / 2 g′′(ξ) (xr – xi)^2LettingEi = (xr – xi), the error in the ith step and
Ei+1 = (xr – xi+1), the error in the (i + 1) step, we
have
EggxEi+1 = – [ /^12 ′′( )/ (ξ ′ i)] i^2which near convergence becomes (since both xi and ξ approach xr)
EgxgxEi+1 = – [ /^12 ′′( rr)/ (′ )] i^2 (12.7)that is, near convergence, the error is proportional to the square of the previous error. For this
reason, the Newton-Raphson method is quadratically convergent. However, there is no general
convergence criterion for this method and the convergence depends mainly on the nature of the
function and the location of the initial guess. Moreover, quadratic convergence is an attribute shown
by the method only near the location of the root. For other situations where g′(xi)≈ 0 (local maxima
or minima in the vicinity of the root or a multiple root), the subsequent guess xi+1 may lie far from
the root, anywhere on the x axis. For such reasons, the Newton-Raphson method may diverge.
Example 12.5. We estimate a root of f(x) = x^3 – 2x^2 – x + 2 with the starting guess of x = 10. The
results are
xold xf (x) Error = | x–xold |10.00 6.94 792.00 3.06
6.94 4.93 233.23 2.01
4.93 3.62 68.19 1.31
3.62 2.80 19.62 0.82
2.80 2.32 5.44 0.48
2.32 2.08 1.37 0.24
2.08 2.01 0.26 0.07
2.01 2.00 0.02 0.01
2.00 2.00 0.00 0.00(c) Secant method
A problem in implementing the Newton-Raphson method is the evaluation of the derivative and the
related repercussions. In many cases, it may not be easy to compute the derivative analytically for
which the derivative may be approximated using the backward difference method as
xrf(xi+1)f(xi)xi+2 xi+1 xiFigure 12.7 Newton-Raphson method