Abstract
This paper presents two algorithms for solving sparse nonlinear systems of equations: the CM-successive column correction algorithm and a modified CM-successive column correction algorithm. Aq-superlinear convergence theorem and anr-convergence order estimate are given for both algorithms. Some numerical results and the detailed comparisons with some previously established algorithms show that the new algorithms have some promise of being very effective in practice.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C.G. Broyden, “A class of methods for solving nonlinear simultaneous equations,”Mathematics of Computation 19 (1965) 577–593.
C.G. Broyden, “The convergence ofan algorithm for solving sparse nonlinear systems,”Mathematics of Computation 25 (1971) 285–294.
C.G. Broyden, J.E. Dennis, Jr. and J.J. Moré, “On the local and superlinear convergence of quasi-Newton methods,”Journal of the Institute of Mathematics and its Application 12 (1973) 223–246.
T.F. Coleman and J.J. Moré, “Estimation of sparse Jacobian and graph coloring problems,”SIAM Journal on Numerical Analysis 20 (1983) 187–209.
A.R. Curtis, M.J.D. Powell and J.K. Reid, “On the estimation of sparse Jacobian matrices,”IMA Journal of Applied Mathematics 13 (1974) 117–119.
J.E. Dennis, Jr. and J.J. Moré, “A characterization of superlinear convergence and its application to quasi-Newton methods,”Mathematics of Computation 28 (1974) 549–560.
J.E. Dennis, Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1983).
Guocheng Feng and Guangye Li, “Column-update quasi-Newton method,”Numerical Mathematics Journal of Chinese Universities 5 (1983) 139–147.
Guangye Li, “The secant/finite difference algorithm for solving sparse nonlinear systems of equations,” Technical Report 86-1, Mathematical Sciences Department, Rice University (Houston, TX, 1986), to appear inSIAM Journal on Numerical Analysis.
E. Marwil, “Convergence results for Schubert's method for solving sparse nonlinear equations,”SIAM Journal on Numerical Analysis 16 (1979) 588–604.
J.J. Moré and M.Y. Cosnard, “Numerical solution of nonlinear equations,”ACM Transactions on Mathematical Software 5 (1979) 64–85.
J.J. Moré, B.S. Garbow and K.E. Hillstrom, “Testing unconstrained optimization software,”ACM Transactions on Mathematical Software 7 (1981) 17–41.
J.M. Ortega and W.C. Rheinboldt,Iterative solution of nonlinear equations in several variables (Academic Press, New York and London, 1970).
E. Polak, “A modified secant method for unconstrained minimization,” Memorandum No. ERLM373, Electronics Research Lab, College of Engineering, University of California (Berkeley, CA, 1973).
M.J.D. Powell and PH.L. Toint, “On the estimation of sparse Hessian matrices,”SIAM Journal on Numerical Analysis 16 (1979) 1060–1074.
J.K. Reid, “Least squares solution of sparse systems of non-linear equations by a modified Marquardt algorithm,”Proceedings of the NATO Conference at Cambridge (North Holland, Amsterdam, 1972) pp. 437–445.
H.H. Rosenbrock, “An automatic method for finding the greatest or least value of a function,”Computer Journal 3 (1960) 175–184.
L.K. Schubert, “Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian,”Mathematics of Computation 24 (1970) 27–30.
E. Spedicato, “Computational experience with quasi-Newton algorithms for minimization problems of moderately large size,” Report CISE-N-175, Segrate (Milano, 1975).
Author information
Authors and Affiliations
Additional information
This research was partially supported by contracts and grants: DOE DE-AS05-82ER1-13016, AFOSR 85-0243 at Rice University, Houston, U.S.A. and Natural Sciences and Engineering Research Council of Canada grant A-8639.
Rights and permissions
About this article
Cite this article
Li, G. Successive column correction algorithms for solving sparse nonlinear systems of equations. Mathematical Programming 43, 187–207 (1989). https://doi.org/10.1007/BF01582289
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582289