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

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.**19**(1965), 577–593. MR**0198670**, https://doi.org/10.1090/S0025-5718-1965-0198670-6**[2]**C. G. Broyden,*A new method of solving nonlinear simultaneous equations*, Comput. J.**12**(1969/1970), 94–99. MR**0245197**, https://doi.org/10.1093/comjnl/12.1.94**[3]**C. G. Broyden,*The convergence of single-rank quasi-Newton methods*, Math. Comp.**24**(1970), 365–382. MR**0279993**, https://doi.org/10.1090/S0025-5718-1970-0279993-0**[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,*The application of the method of the variation of a parameter to the construction of iteration formulae of heightened precision for the determination of numerical solutions of non-linear integral equations*, Dokl. Akad. Nauk SSSR**162**(1965), 499–502 (Russian). MR**0178581****[6]**Allen A. Goldstein,*Constructive real analysis*, Harper & Row, Publishers, New York-London, 1967. MR**0217616****[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**0184422****[11]**John M. Bennett,*Triangular factors of modified matrices*, Numer. Math.**7**(1965), 217–221. MR**0177503**, https://doi.org/10.1007/BF01436076**[12]**J. E. Dennis Jr.,*On the convergence of Newton-like methods*, Numerical methods for nonlinear algebraic equations (Proc. Conf., Univ. Essex, Colchester, 1969) Gordon and Breach, London, 1970, pp. 163–181. MR**0353662****[13]**L. V. Kantorovič and G. P. Akilov,*\cyr Funktsional′nyĭ analiz v normirovannykh prostranstvakh*, Gosudarstv. Izdat. Fis.-Mat. Lit., Moscow, 1959 (Russian). MR**0119071****[14]**L. K. Schubert,*Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian*, Math. Comp.**24**(1970), 27–30. MR**0258276**, https://doi.org/10.1090/S0025-5718-1970-0258276-9

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