A hybrid algorithm for solving sparse nonlinear systems of equations

Authors:
J. E. Dennis and Guang Ye Li

Journal:
Math. Comp. **50** (1988), 155-166

MSC:
Primary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917823-5

MathSciNet review:
917823

Full-text PDF

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 Kantorovich-type analysis and a locally *q*-superlinear 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**, https://doi.org/10.1090/S0025-5718-1965-0198670-6**[2]**C. G. Broyden,*The convergence of an algorithm for solving sparse nonlinear systems*, Math. Comp.**25**(1971), 285–294. MR**0297122**, https://doi.org/10.1090/S0025-5718-1971-0297122-5**[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**, https://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. 117-119.**[5]**J. E. Dennis Jr. and Jorge J. Moré,*Quasi-Newton methods, motivation and theory*, SIAM Rev.**19**(1977), no. 1, 46–89. MR**0445812**, https://doi.org/10.1137/1019005**[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****[7]**Guangye Li,*The Secant/Finite Difference Algorithm for Solving Sparse Nonlinear Systems of Equations*, Technical Report 86-1, 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**, https://doi.org/10.1137/0716044**[9]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****[10]**J. K. Reíd,*Least Squares Solution of Sparse Systems of Non-linear Equations by a Modified Marquardt Algorithm*, Proceedings of the NATO Conf. at Cambridge, July 1972, North-Holland, Amsterdam, pp. 437-445.**[11]**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-1988-0917823-5

Keywords:
Finite difference,
Jacobian,
*q*-superlinear convergence,
Kantorovich type analysis,
sparsity,
nonlinear system of equations

Article copyright:
© Copyright 1988
American Mathematical Society