| ZERO -- Zeros of Functions and Systems The following table shows performance of Newtons method for the problem f1=x**2-y-2=0 and f2=x*y+1=0 with initial guess -4,4 | x1 | x2 | f1 | f2 | ||inv(jacob)|| | | -4.0000 | 4.0000 | 10.000 | -15.000 | .33333 | | -2.4722 | 1.7778 | 2.3341 | -3.3951 | .48011 | | -1.8176 | .87522 | .42851 | -.59082 | .60279 | | -1.6346 | .63831 | .33506E-01 | -.43366E-01 | .65321 | | -1.6182 | .61819 | .26912E-03 | -.33013E-03 | .65832 |
See also the picture. The solutions of the system occur where the three colors corresponding to the surfaces z=f1(x,y), z=f2(x,y) and z=0 (red , dark blue and light blue) meet. The iterates are represented by vertical bars.   | Single Variable |
 | f77-zero,
C++ version,
C version | f is a function of one real variable (Brent-Decker method), using function values only, zerofinder , needs inclusion by change of sign on interval | | SERVER | server routines for brent.shar (C) | | polyzero | f is a polynomial of one complex variable and has real coefficients (least squares method, interactive/file input, f77/C) | | companion
C-version | f polynomial with real coefficients, QR for eigenvalues of companion matrix | | Aberth
C-version | f is a polynomial with complex coefficients | | Muller
C-version | f is a general function of one complex variable | | ZERO | search for a zero in a given interval | | RPOLY | find all zeroes of a real polynomial (Jenkins-Traub method) f90-version | | Madsen | find all zeroes of a real polynomial, C++ version | | CPOLY | find all zeroes of a complex polynomial (Jenkins-Traub method) f90-version, C++-version | | RROOT | safely enclosing zeroes of a continuous function in an interval | | WINSOLVE | Windows application, 11 methods to find polynomial zeros |
| Multiple Variable |
| box_zeros | f depends on one or more complex variables, zeros sought in box (based on TOMS666) | | HYBRJ | f not too nonlinear, exact Jacobian (Powell's hybrid method) | | HYBRD | not too nonlinear, Powells hybrid method, finite difference Jacobian | | DogLeg | Powell's dogleg method (Matlab) | | Filtrane | part of Galahad, nonlinear constraint solver, filter method, f90 | | PITCON | f not too nonlinear, no good initial guess available, continuation method | | ALCON1 | Continuation method for systems of algebraic equations f(x,tau)=0. Optional computation of turning and (simple) bifurcation points (by Deuflhard and Kunkel) | | ALCON2 | Continuation method for systems of algebraic equations f(x,tau)=0. Optional computation of turning and (simple) bifurcation points (by Deulfhard, Fiedler and Kunkel). Optional automatic construction of complete bifurcation diagrams. | | ALCON_S | Continuation method for systems of algebraic equations f(x,tau)=0. Large and sparse systems. (from elib/codelib, author Klein-Robbenhaar) | | Continuation Toolbox | Includes continuation of limit cycles and codim 1 bifurcations (Matlab) | | codelib/nleq1 | f strongly nonlinear, damped Newtons method | | codelib/nleq1s | damped Newtons method, large and sparse problems, direct linear algebra | | codelib/nleq2 | damped Newtons method, provision for singular Jacobian | | NLEQ-paper | postscript file on above nleq* codes | | PEQN/PEQL | inexact Newton and inverse column update methods, for large/sparse problems | | codelib/giant | damped Newtons method, large and sparse problems, iterative linear algebra | | nnes | zeros sought in box: l<=x<=u, see also users' guide | | DAFNE | differential equations approach with second order system inspired by mechanics | | CHABIS | characteristic bisection method | | EPSILON | Maple-based package for operations on polynomials including solving systems | | HOMPACK | globally convergent continuation method for polynomial systems | | HOMPACK90 | f90 version of HOMPACK | | POLSYS_PLP | more sophisticated version of HOMPACK90 | | PHoM | Polyhedral Homotopy Continuation Method for Polynomial Systems (C++), module CMPS also in Matlab | | TENSOLVE | A Software Package for Solving Systems of Nonlinear Equations and Nonlinear Least-squares Problems Using Tensor Methods f90 version | | toms/795 , PHCPACK | A general-purpose solver for polynomial systems by homotopy continuation | | INTOPT_90 | f90, see under Interval software |
| (Constrained) minimization approach |
Rootfinders based on Newtons method or its modification will run into considerable trouble when presented with a problem where singularities of the Jacobian occur. In this case the use of unconstrained or constrained minimization might help, since there exist minimization methods which are rather robust if the constraints gradients are linearly dependent. To use an unconstrained minimizer, choose e.g. f(x)=||F(X)||^2 (the Euclidean length squared) and minimize this with some code proposed in the unconstrained minimization section. To use a constrained minimizer, choose simply f==0 as an objective function and minimize this under the constraint F(x)=0. The following code works often successfully in this situation:
| |
