A hybrid algorithm for solving sparse nonlinear systems of equations
Authors:
J. E. Dennis and Guang Ye Li
Journal:
Math. Comp. 50 (1988), 155166
MSC:
Primary 65H10
MathSciNet review:
917823
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: This paper presents a hybrid algorithm for solving sparse nonlinear systems of equations. The algorithm is based on dividing the columns of the Jacobian into two parts and using different algorithms on each part. The hybrid algorithm incorporates advantages of both component algorithms by exploiting the special structure of the Jacobian to obtain a good approximation to the Jacobian, using as little effort as possible. A Kantorovichtype analysis and a locally qsuperlinear convergence result for this algorithm are given.
 [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, The convergence of an algorithm for
solving sparse nonlinear systems, Math.
Comp. 25 (1971),
285–294. MR 0297122
(45 #6180), http://dx.doi.org/10.1090/S00255718197102971225
 [3]
Thomas
F. Coleman and Jorge
J. Moré, Estimation of sparse Jacobian matrices and graph
coloring problems, SIAM J. Numer. Anal. 20 (1983),
no. 1, 187–209. MR 687376
(84f:05043), http://dx.doi.org/10.1137/0720013
 [4]
A. R. Curtis, M. J. D. Powell & J. K. Reíd, "On the estimation of sparse Jacobian matrices," J. Inst. Math. Appl., v. 13, 1974, pp. 117119.
 [5]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [6]
John
E. Dennis Jr. and Robert
B. Schnabel, Numerical methods for unconstrained optimization and
nonlinear equations, Prentice Hall Series in Computational
Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
(85j:65001)
 [7]
Guangye Li, The Secant/Finite Difference Algorithm for Solving Sparse Nonlinear Systems of Equations, Technical Report 861, Math Sciences Dept., Rice Univ., 1986.
 [8]
Earl
Marwil, Convergence results for Schubert’s method for solving
sparse nonlinear equations, SIAM J. Numer. Anal. 16
(1979), no. 4, 588–604. MR 537273
(80i:65057), http://dx.doi.org/10.1137/0716044
 [9]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [10]
J. K. Reíd, Least Squares Solution of Sparse Systems of Nonlinear Equations by a Modified Marquardt Algorithm, Proceedings of the NATO Conf. at Cambridge, July 1972, NorthHolland, Amsterdam, pp. 437445.
 [11]
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 0198670 (33:6825)
 [2]
 C. G. Broyden, "The convergence of an algorithm for solving sparse nonlinear systems," Math. Comp., v. 25, 1971, pp. 285294. MR 0297122 (45:6180)
 [3]
 T. F. Coleman & J. J. Moré, "Estimation of sparse Jacobian matrices and graph coloring problems," SIAM J. Numer. Anal., v. 20, 1983, pp. 187209. MR 687376 (84f:05043)
 [4]
 A. R. Curtis, M. J. D. Powell & J. K. Reíd, "On the estimation of sparse Jacobian matrices," J. Inst. Math. Appl., v. 13, 1974, pp. 117119.
 [5]
 J. E. Dennis, Jr. & J. J. Moré, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [6]
 J. E. Dennis, Jr. & R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, PrenticeHall, Englewood Cliffs, N. J., 1983. MR 702023 (85j:65001)
 [7]
 Guangye Li, The Secant/Finite Difference Algorithm for Solving Sparse Nonlinear Systems of Equations, Technical Report 861, Math Sciences Dept., Rice Univ., 1986.
 [8]
 E. Marwil, "Convergence results for Schubert's method for solving sparse nonlinear equations," SIAM J. Numer. Anal., v. 16, 1979, pp. 588604. MR 537273 (80i:65057)
 [9]
 J. M. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
 [10]
 J. K. Reíd, Least Squares Solution of Sparse Systems of Nonlinear Equations by a Modified Marquardt Algorithm, Proceedings of the NATO Conf. at Cambridge, July 1972, NorthHolland, Amsterdam, pp. 437445.
 [11]
 L. K. Schubert, "Modification of a quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 24, 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/S00255718198809178235
PII:
S 00255718(1988)09178235
Keywords:
Finite difference,
Jacobian,
qsuperlinear convergence,
Kantorovich type analysis,
sparsity,
nonlinear system of equations
Article copyright:
© Copyright 1988
American Mathematical Society
