When derivatives are not available or are difficult to calculate, the
matrix can be either a
finite-difference approximation to the Jacobian matrix or a matrix generated by Broyden's
method. Approximations based on differences of function values can be obtained by noting
that the ith column of the Jacobian is approximated by
where the difference parameter is a small scalar and is the ith unit vector (the ith
component of
is 1; all other components are zero). The choice of the difference parameter
can be a source of difficulty for many codes, particularly if the problem is highly
nonlinear or if the function is noisy.
Broyden's method updates the matrix at each iterate so that the new
approximation
satisfies the
quasi-Newton equation
Given an initial matrix (often a finite-difference approximation to the Jacobian
matrix), Broyden's method generates subsequent matrices by using the updating formula
where
The remarkable feature of Broyden's method is that it is able to
generate a reasonable approximation to the Jacobian matrix with no additional evaluations
of the function. This feature is partially explained by noting that, because of equation
(1.4), the updated mimics the
behavior of the true Jacobian along the line joining
to
.
The IMSL , MINPACK-1 , and NAG(FORTRAN and NAG(C) codes implement a trust-region method where the approximate Jacobian matrices are usually calculated by Broyden's method. If the algorithm is not making satisfactory progress, the matrix is reset to a finite-difference approximation of the Jacobian and is updated by using (1.5) on subsequent iterations.
Up To:
Systems of Nonlinear Equations .
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Last updated 28 March 1996
