Roots of Nonlinear Functions

Newton-Raphson Method

The Newton-Raphson method is similar to the secant method only instead of estimating a root by the intersection of the x-axis with a secant throught two points on the curve, the estimate is obtained from the intersection of the x-axis and the tangent to the curve at a point. The Newton-Raphson method requires only a single initial estimate, but unlike the other methods it also requires that the user program both the function and its derivative. In the neighborhood of a root of order 1, Newton-Raphson converges quadratically to the root. However, other methods may be superior in terms of the number of function calls because the Newton-Raphson method requires two function calls per iterative step whereas the other methods require only one and often the derivative can be much more complicated than the function itself.

The Newton-Raphson method is an iterative procedure to estimate a root of an equation
f(x) = 0 where the user gives an initial estimate, a tolerance and programs the derivative of the function f(x). The procedure then calculates a new estimate until the distance between the two estimates is less than the preassigned tolerance. If x_i-1 is the current estimate, the new estimate x_i is that point on the x-axis which is the intersection of the x-axis and the tangent to the curve y = f(x) at the point ( x_i-1, f(x_i-1) ). The subsequent estimate then uses the point ( x_i, f(x_i) ).

It is best to avoid using the Newton-Raphson method if there are local extrema near the root and if the root has order > 1. The convergence of the Newton-Raphson method depends on the initial estimate and on the order of the root. For roots with order 1, convergence is quadratic near the root, however Newton-Raphson requires calculating not only the function but also its derivative at each step. For this reason, Newton-Raphson may require fewer steps, but more function calls than other methods.

Function List

• double Newton_Raphson( double (*f)(double), double (*df)(double), double a, double tolerance, int max_iteration_count, int *err)
  
  Find a root of f(x) near a. The procedure terminates when the absolute difference of the return value and the actual root is less than tolerance, where tolerance is a user specified number specifying the desired accuracy of the result. The input argument (*df)(double) is the value of the derivative of f(x) evaluated at the argument. The input argument max_iteration_count allows the user to control the maximum number of iterations to attempt. The method returns an err of 0 if the iteration was successful, -1 if the number of iterations exceeded the maximum allowable number of iterations as specified by the user, and -2 if an attempt was made to divide by zero, which is indicative of a local minimum or a local maximum. Even if the an err return of 0 occurs, it is possible that the result is erroneous, especially if there is a local minimum or local maximum near the root. For this reason, if it is not known whether there is a local extremum in a small neighborhood of the root, the result should be checked for its validity.
  
  

C Source Code

• The file, newton_raphson.c, contains the version of Newton_Raphson( ) written in C.