Systems of nonlinear equations arise as constraints in optimization problems, but also arise, for example, when differential and integral equations are discretized. In solving a system of nonlinear equations, we seek a vector such that f(x)=0 where x is an n-dimensional --- of n variables. Most algorithms in this section are closely related to algorithms for unconstrained optimization and nonlinear least squares. Indeed, algorithms for systems of nonlinear equations usually proceed by seeking a local minimizer to the problem

for some norm , usually the 2-norm. This strategy is reasonable, since any solution of the nonlinear equations is a global solution of the minimization problem.

Newton's method, modified and enhanced, forms the basis for most of the software used to solve systems of nonlinear equations. Given an iterate, Newton's method computes f(x) and its Jacobian matrix, finds a step by solving the system of linear equations

and then sets .

Most of the computational cost of Newton's method is associated with two operations: evaluation of the function and the Jacobian matrix, and the solution of the linear system (1.1). Since the Jacobian is

the computation of the ith column requires the partial derivative of f with respect to the ith variable, while the solution of the linear system (1.1) requires order operations when the Jacobian is dense.

Convergence of Newton's method is guaranteed if the starting is sufficiently close to the solution and the Jacobian at the solution is nonsingular. Under these conditions the rate of convergence is quadratic; that is,

for some positive constant . This rapid local convergence is the main advantage of Newton's method. The disadvantages include the need to calculate the Jacobian matrix and the lack of guaranteed global convergence; that is, convergence from remote starting points.

The following software attempts to overcome these two disadvantages of Newton's method by allowing approximations to be used in place of the exact Jacobian matrix and by using two basic strategies-trust region and line search-to improve global convergence behavior:

GAUSS , IMSL , LANCELOT , MATLAB , MINPACK-1 , NAG(FORTRAN) , NAG(C) , NITSOL , and OPTIMA .

• Trust Region and Line-search Methods .
• Truncated Newton Method .
• Broyden's Method .
• Tensor Methods .
• Homotopy Methods .

Up To:

Uncontrained Optimization.

[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]

Updated 28 March 1996