The convergence of an algorithm for solving sparse nonlinear systems

Author:
C. G. Broyden

Journal:
Math. Comp. **25** (1971), 285-294

MSC:
Primary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-1971-0297122-5

MathSciNet review:
0297122

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new algorithm for solving systems of nonlinear equations where the Jacobian is known to be sparse is shown to converge locally if a sufficiently good initial estimate of the solution is available and if the Jacobian satisfies a Lipschitz condition. The results of numerical experiments are quoted in which systems of up to 600 equations have been solved by the method.

**[1]**C. G. Broyden, "A class of methods for solving nonlinear simultaneous equations,"*Math. Comp.*, v. 19, 1965, pp. 577-593. MR**33**#6825. MR**0198670 (33:6825)****[2]**C. G. Broyden, "A new method of solving nonlinear simultaneous equations,"*Comput. J.*, v. 12, 1969/70, pp. 94-99. MR**39**#6509. MR**0245197 (39:6509)****[3]**C. G. Broyden, "The convergence of single-rank quasi-Newton methods,"*Math. Comp.*, v. 24, 1970, pp. 365-382. MR**0279993 (43:5714)****[4]**A. Chang,*Applications of Sparse Matrix Methods in Electric Power Systems Analysis*, Proc. Sympos. on Sparse Matrices and Their Applications (IBM Watson Research Center, 1968), RA 1 #11707, Watson Research Center, Yorktown Heights, New York, 1969.**[5]**D. F. Davidenko, "An application of the method of variation of parameters to the construction of iterative formulas of increased accuracy for numerical solutions of nonlinear equations,"*Dokl. Akad. Nauk SSSR*, v. 162, 1962, pp. 499-502 =*Soviet Math. Dokl.*, v. 3, 1962, pp. 702-706. MR**31**#2838. MR**0178581 (31:2838)****[6]**A. A. Goldstein,*Constructive Real Analysis*, Harper & Row, New York, 1967. MR**36**#705. MR**0217616 (36:705)****[7]**F. G. Gustavson, W. Liniger & R. Willoughby, "Symbolic generation of an optimal Crout algorithm for sparse systems of linear equations,"*J. Assoc. Comput. Mach.*, v. 17, 1970, pp. 87-109.**[8]**R. P. Tewarson,*The Gaussian Elimination and Sparse Systems*, Proc. Sympos. on Sparse Matrices and Their Applications (IBM Watson Research Center, 1968), Watson Research Center, Yorktown Heights, New York, 1968.**[9]**W. F. Tinney & C. E. Hart, "Power flow solutions by Newton's method,"*IEEE Trans.*, v. PAS-86, 1967, pp. 1449-1460.**[10]**J. H. Wilkinson,*The Algebraic Eigenvalue Problem*, Clarendon Press, Oxford, 1965. MR**32**#1894. MR**0184422 (32:1894)****[11]**J. M. Bennett, "Triangular factors of modified matrices,"*Numer. Math.*, v. 7, 1965, pp. 217-221. MR**31**#1766. MR**0177503 (31:1766)****[12]**J. E. Dennis,*On Convergence of Newton-Like Methods*, Numerical Methods for Non-linear Algebraic Equations edited by P. Rabinowitz, Gordon & Breach, London, 1970. MR**0353662 (50:6145)****[13]**L. V. Kantorovič & G. P. Akilov,*Functional Analysis in Normed Spaces*, Fitzmatgiz, Moscow, 1959; English transl., Internat. Series of Monographs in Pure and Appl. Math., vol. 46, Macmillan, New York, 1964. MR**22**#9837; MR**35**#4699. MR**0119071 (22:9837)****[14]**L. K. Schubert, "Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian,"*Math. Comp.*, v. 25, 1970, pp. 27-30. MR**0258276 (41:2923)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65H10

Retrieve articles in all journals with MSC: 65H10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1971-0297122-5

Keywords:
Sparse,
algebraic,
nonlinear,
systems

Article copyright:
© Copyright 1971
American Mathematical Society