Newton-RaphsonGiven a function g : Rn → Rn Newton-Raphson's method attempts to find a zero of g i.e. a point x ∈ Rn such that g (x) = 0.
If f : Rn → R is of class C2 then the function g : Rn → Rn defined by g (x) = grad f (x) is of class C1. The critical points of f correspond to the zeros of g. The Jacobian of g corresponds to the Hessian of f at a critical point. Given an initial point x0 ∈ Rn, Newton-Raphson's method iteratively finds a critical point of f where that critical point may be a local minimum, a local maximum, or a saddle point.
The Newton-Raphson method proceeds as follows:
- Initialization: Choose an initial estimate, x0, for the location of a zero of the predetermined function g : Rn → Rn.
- Determine the Displacement Vector d: Calculate the Jacobian J of g evaluated at, x0, Ji,j = ∂gi ( x0 ) / ∂xj. The displacement d = x - x0 of the approximation to the location of the zero of g satisfies the linear equation Jd = -g.
- Update the estimate for the location of a local minimum: Replace the initial estimate, x0, with x0 + d.
- Check if the stopping criterion is satisfied: The conventional stopping rules are: (1) Stop if || g || < ε for either the max-norm or the l2-norm, and/or (2) Stop if
|| d || < ε for either the max-norm or the l2-norm. If the stopping criterion is not satisfied, then iterate.
- int Newton_Raphson_ndim( void (*f)(double*, double*), void (*df)(double*, double*, double*), int (*Stopping_Rule)(double*, double*, int, int), double *a, double *fa, int n )
This routine uses the Newton-Raphson method to approximately locate a zero of the function f (x). The user-supplied function f (x, fx) has two arguments, the first is the location x where the function is evaluated and the second is the array whose ith component is the ith component of f (x). The user-supplied function df corresponds to the Jacobian of f (x). df (x, fx, dfx) has three arguments, the first is the location x where the function is evaluated, the second is the array whose ith component is the ith component of f (x) which is included to facilitate the evaluation of the Jacobian in the event the Jacobian depends explicitly on the value f (x), and the third argument is the Jacobian n x n matrix whose i,j element is ∂fi / ∂xj evaluated at x. The arguments to the user-supplied stopping_rule are: the displacement vector d between two successive iteratates, the function evaluated at the new estimate f(x), the total number of iterations performed, and n the dimension of x. The user-supplied stopping_rule should return a non-zero, either positive or negative, integer to halt the procedure and return zero to continue iterating, return values -1 and -2 are intrinsic return values used by the Newton-Raphson routine. Upon exiting the function returns either the return of the user-supplied stopping-rule, a -1 indicates that there was not enough dynamic heap memory, -2 indicates that the Jacobian matrix is singular or ill-formed. The value a is set to the current estimate and the argument fa is set to the value of the function evaluated there.
C Source Code
- The file, newton_raphson_ndim.c, contains the version of Newton_Raphson_ndim( ) written in C.