The convergence of an algorithm for solving sparse nonlinear systems
Author:
C. G. Broyden
Journal:
Math. Comp. 25 (1971), 285294
MSC:
Primary 65H10
MathSciNet review:
0297122
Fulltext 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. 19 (1965),
577–593. MR 0198670
(33 #6825), http://dx.doi.org/10.1090/S00255718196501986706
 [2]
C.
G. Broyden, A new method of solving nonlinear simultaneous
equations, Comput. J. 12 (1969/1970), 94–99. MR 0245197
(39 #6509)
 [3]
C.
G. Broyden, The convergence of singlerank
quasiNewton methods, Math. Comp. 24 (1970), 365–382. MR 0279993
(43 #5714), http://dx.doi.org/10.1090/S00255718197002799930
 [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 nonlinear integral
equations, Dokl. Akad. Nauk SSSR 162 (1965),
499–502 (Russian). MR 0178581
(31 #2838)
 [6]
Allen
A. Goldstein, Constructive real analysis, Harper & Row,
Publishers, New YorkLondon, 1967. 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. 87109.
 [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. PAS86, 1967, pp. 14491460.
 [10]
J.
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
(32 #1894)
 [11]
John
M. Bennett, Triangular factors of modified matrices, Numer.
Math. 7 (1965), 217–221. MR 0177503
(31 #1766)
 [12]
J.
E. Dennis Jr., On the convergence of Newtonlike methods,
Numerical methods for nonlinear algebraic equations (Proc. Conf., Univ.
Essex, Colchester, 1969) Gordon and Breach, London, 1970,
pp. 163–181. MR 0353662
(50 #6145)
 [13]
L.
V. Kantorovič and G.
P. Akilov, Funktsionalnyi analiz v normirovannykh
prostranstvakh, Gosudarstv. Izdat. Fis.Mat. Lit., Moscow, 1959
(Russian). MR
0119071 (22 #9837)
 [14]
L.
K. Schubert, Modification of a quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 [1]
 C. G. Broyden, "A class of methods for solving nonlinear simultaneous equations," Math. Comp., v. 19, 1965, pp. 577593. 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. 9499. MR 39 #6509. MR 0245197 (39:6509)
 [3]
 C. G. Broyden, "The convergence of singlerank quasiNewton methods," Math. Comp., v. 24, 1970, pp. 365382. 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. 499502 = Soviet Math. Dokl., v. 3, 1962, pp. 702706. 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. 87109.
 [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. PAS86, 1967, pp. 14491460.
 [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. 217221. MR 31 #1766. MR 0177503 (31:1766)
 [12]
 J. E. Dennis, On Convergence of NewtonLike Methods, Numerical Methods for Nonlinear 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 quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 25, 1970, pp. 2730. MR 0258276 (41:2923)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H10
Retrieve articles in all journals
with MSC:
65H10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197102971225
PII:
S 00255718(1971)02971225
Keywords:
Sparse,
algebraic,
nonlinear,
systems
Article copyright:
© Copyright 1971
American Mathematical Society
