Direct secant updates of matrix factorizations

Authors:
J. E. Dennis and Earl S. Marwil

Journal:
Math. Comp. **38** (1982), 459-474

MSC:
Primary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-1982-0645663-8

MathSciNet review:
645663

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents a new context for using the sparse Broyden update method to solve systems of nonlinear equations. The setting for this work is that a Newton-like algorithm is assumed to be available which incorporates a workable strategy for improving poor initial guesses and providing a satisfactory Jacobian matrix approximation whenever required. The total cost of obtaining each Jacobian matrix, or the cost of factoring it to solve for the Newton step, is assumed to be sufficiently high to make it attractive to keep the same Jacobian approximation for several steps. This paper suggests the extremely convenient and apparently effective technique of applying the sparse Broyden update directly to the matrix factors in the iterations between reevaluations in the hope that fewer fresh factorizations will be required. The strategy is shown to be locally and *q*-superlinearly convergent, and some encouraging numerical results are presented.

**[1]**K. W. Brodlie, A. R. Gourlay, and J. Greenstadt,*Rank-one and rank-two corrections to positive definite matrices expressed in product form*, J. Inst. Math. Appl.**11**(1973), 73–82. MR**0331770****[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]**A. K. Cline, C. B. Moler, G. W. Stewart, and J. H. Wilkinson,*An estimate for the condition number of a matrix*, SIAM J. Numer. Anal.**16**(1979), no. 2, 368–375. MR**526498**, https://doi.org/10.1137/0716029**[4]**A. R. Curtis, M. J. D. Powell & J. K. Reid, "On the estimation of sparse Jacobian matrices,"*J. Inst. Math. Appl.*, v. 13, 1974, pp 117-119.**[5]**J. E. Dennis Jr.,*A brief introduction to quasi-Newton methods*, Numerical analysis (Proc. Sympos. Appl. Math., Atlanta, Ga., 1978), Proc. Sympos. Appl. Math., XXII, Amer. Math. Soc., Providence, R.I., 1978, pp. 19–52. MR**533049****[6]**J. E. Dennis Jr. and Jorge J. Moré,*A characterization of superlinear convergence and its application to quasi-Newton methods*, Math. Comp.**28**(1974), 549–560. MR**0343581**, https://doi.org/10.1090/S0025-5718-1974-0343581-1**[7]**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**[8]**J. E. Dennis Jr. and Homer F. Walker,*Convergence theorems for least-change secant update methods*, SIAM J. Numer. Anal.**18**(1981), no. 6, 949–987. MR**638993**, https://doi.org/10.1137/0718067**[9]**J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart,*LINPACK User's Guide, SIAM*, Philadelphia, Pa., 1979.**[10]**I. S. Duff, "A survey of sparse matrix research,"*Proc. IEEE*, v. 65, 1977, pp. 500-535.**[11]**A. M. Erisman and J. K. Reid,*Monitoring the stability of the triangular factorization of a sparse matrix*, Numer. Math.**22**(1973/74), 183–186. MR**0345395**, https://doi.org/10.1007/BF01436966**[12]**P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders,*Methods for modifying matrix factorizations*, Math. Comp.**28**(1974), 505–535. MR**0343558**, https://doi.org/10.1090/S0025-5718-1974-0343558-6**[13]**A. Hindmarsh, private communication, 1978.**[14]**A. Lucia, Thesis, Dept. of Chem. Engr., University of Connecticut, Storrs, 1980.**[15]**J. J. Moré, B. Garbow & K. Hillstrom,*User Guide for MINPACK*-1, Report ANL-80-74, Argonne National Laboratories, 1980.**[16]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****[17]**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**[18]**C. Van Loan, private communication, 1978.**[19]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[20]**M. Wheeler & T. Potempa, private communication, 1980.

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-1982-0645663-8

Article copyright:
© Copyright 1982
American Mathematical Society